igraph:给定顶点列表，找到最小的连通子图 [英] igraph: given a list of vertices, find the smallest connected subgraph

问题描述

我有以下问题:我有一个相对较大的图，并且希望在给定一组顶点的情况下提取一个相连的子图，这些顶点可能不直接相连.示例:

I have the following problem: I have a relatively large graph and would like to extract a connected subgraph given a set of vertices, which might not be directly connected. Example:

library(igraph)
Test <- graph(c("a", "b", "a", "c", "a", "d", "b", "e", "b", "f", 
              "c", "g", "c", "h", "d", "i"))
plot(Test, layout=layout_as_tree)

现在我想提取包含(例如)顶点"e" ，"c" 和"g" .在igraph套件中，有没有简单的方法可以做到这一点?感谢您的任何建议！

now I would like to extract the (smallest) subgraph that contains e.g. vertices "e", "c" and "g". Is there an easy way to do that in the igraph package? thanks for any suggestions!

干杯，乔

推荐答案

知道了！使用igraph很容易:

Got it! It's easy with igraph:

subnodes <- c("e", "c", "g")
needNodes <- character()
## loop through all nodes and calculate the path to each other node
for(i in 1:(length(subnodes)-1)){
    paths <- shortest_paths(Test, from=subnodes[i], 
                           to=subnodes[(i+1):length(subnodes)],
                           mode="all")
    needNodes <- unique(c(needNodes, unlist(lapply(paths$vpath, names))))
}
## subset the graph
subGr <- induced_subgraph(Test, vids=needNodes)
## looks good:
plot(subGr, layout=layout_as_tree)

感谢漂亮的igraph包！

Thanks for the nice igraph package!

干杯，乔

这篇关于igraph:给定顶点列表，找到最小的连通子图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！