如何在igraph中查找‘直接’连通分量?相关图论术语与实现
问题描述
我对图论不太了解,担心问题标题表述不够准确,所以附上代码说明需求:
library(magrittr) library(igraph) df <- data.frame(from = c(1, 1, 2, 2, 6), to = c(2, 4, 3, 5, 3)) graph_from_data_frame(df) %>% components() %>% membership() %>% stack() #> values ind #> 1 1 1 #> 2 1 2 #> 3 1 6 #> 4 1 4 #> 5 1 3 #> 6 1 5
上述代码会找出所有连通分量,但我想要的是类似下面的结果:仅考虑“直接”有向路径,让顶点6不属于组1,只和3连通,因此顶点3会重复出现,同时属于组1和组2:
data.frame(values = c(1, 1, 2, 1, 1, 1, 2), ind = c(1, 2, 6, 4, 3, 5, 3)) #> values ind #> 1 1 1 #> 2 1 2 #> 3 2 6 #> 4 1 4 #> 5 1 3 #> 6 1 5 #> 7 2 3
我想知道:
- igraph或R的其他包中有没有实现该功能的函数?优先使用igraph。
- 这个操作在图论中有没有对应的术语?方便我查找更多相关资料。
解决方案(自我补充)
感谢帮助,我发现可以用igraph::subcomponent()满足需求(之前没在igraph::component()的帮助页底部找到这个函数)。因为我每次只需针对单个指定顶点查找分量,且该函数能区分两种场景:
- 获取指定顶点的无向连通分量(所有可达的顶点,不区分方向)
- 获取有向路径子分量(仅考虑从指定顶点出发的有向可达顶点,对应我之前说的“简单路径”分量)
示例代码如下:
df <- data.frame(react_id = c("r1", "r1", "r2", "r2", "r6"), depends_on = c("r2", "r4", "r3", "r5", "r3")) gdf <- igraph::graph_from_data_frame(df) # 获取指定react_id的所有无向连通分量 igraph::subcomponent(gdf, "r3", "all") |> names() #> [1] "r3" "r2" "r6" "r1" "r5" "r4" # 获取从r1出发的有向路径子分量 igraph::subcomponent(gdf, "r1", "out") |> names() #> [1] "r1" "r2" "r4" "r3" "r5"
内容的提问来源于stack exchange,提问作者gss
相关产品推荐
相关产品推荐

