algorithm - R 结构中的节数

Question

您好，我在 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)

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

谢谢!!

Answer 1

试试这个:

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')
}