我不懂图论,所以恐怕题的题目不是性质公式化的,所以我会给出一个代码:
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
# find only "direct" paths
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
有了上面的data.frame
,我知道如何找到所有连接的组件,无论它们是如何连接的.但我也希望能够找到上面代码块末尾所示的东西,即"6"不属于组"1",但与"3"相连,这就是为什么我重复"3"-它属于组"1"和"2".
在igraph
或R
中的其他套餐中有这样的功能吗?但我更喜欢igraph
美元.这个过程在图论中有名字吗?因此,我将能够找到更多关于这方面的信息.
EDIT个
感谢大家的帮助.我发现,对于我的用例,我可以使用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)
# get all connected components for specific react_id
igraph::subcomponent(gdf, "r3", "all") |>
names()
#> [1] "r3" "r2" "r6" "r1" "r5" "r4"
# get "simple paths" components
igraph::subcomponent(gdf, "r1", "out") |>
names()
#> [1] "r1" "r2" "r4" "r3" "r5"