1

嗨,我正在处理 R 中的大量数据,我需要检查一个结构是否由 1 个或多个部分组成。首先我有一个方法向量

wayIds <- [way1, way2, way3, etc..]

然后我有一个矩阵,每个节点的第一个和最后一个节点

endWays
           wayId firstNode lastNode
      [1,]  way1  node1      node2
      [2,]  way2  node4      node8
      [3,]  way3  node5      node1...

两个都很大。所以我需要一种方法来确定结构是否遵循连接方式有一个或多个部分。例如

_|______/ 1 section (all the ways are connected)
_|__   ____/ 2 sections (NOT all the ways are connected)

所以到目前为止,我可以确定所有的开放端(例如分支末端的那些),显然如果我只有两个开放节点,那么解决方案是微不足道的。因此,我需要一种有效的方法来确定所有开放节点是否在不使用循环的情况下相互连接。

谢谢!!

4

1 回答 1

0

尝试这个:

library(igraph)

data <- read.table(text=
'wayId firstNode endNode
way1 node1 node2
way2 node2 node4
way3 node2 node3
way4 node4 node3
way5 node5 node6
way6 node5 node8
way7 node8 node7'
,header=TRUE,sep=' ')

# I reorder the columns before passing the data.frame to the function, 
# because the first 2 columns have to be node from and node to
g <- graph.data.frame(data[,c(2,3,1)],directed=FALSE)

# plot the graph (don't do it if your graph is really big)
plot.igraph(g,vertex.label=V(g)$name,
            vertex.size=30,vertex.label.cex=0.7,
            vertex.shape='square')

subGraphs <- decompose.graph(g,mode='strong')

for(i in 1:length(subGraphs)){
  subGraph <- subGraphs[[i]]

  message(paste('Sub graph:',i))
  # find vertices having just one connected node
  openVertices <- V(subGraph)[sapply(as.vector(V(subGraph)),FUN=function(v){length(E(subGraph)[from(v) | to(v)]) == 1})]

  message(paste('Open vertices:',toString(openVertices$name)))

  # plot the sub-graph (don't do it if your graph is really big)
  plot.igraph(subGraph,vertex.label=V(subGraph)$name,
              vertex.size=30,vertex.label.cex=0.7,
              vertex.shape='square')
}
于 2012-07-25T10:08:54.210 回答