r - 如何找到 "direct"的连通分量？

Question

我不懂图论，所以我担心问题的标题不是属性表述，所以我将显示一个代码:

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。这个过程在图论中有名字吗？这样我就能找到更多关于此的信息。

编辑

谢谢大家的帮助。我发现对于我的用例，我可以使用 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"

Answer 1

类似这样的吗？

suppressPackageStartupMessages(
  library(igraph)
)

df <- data.frame(from = c(1, 1, 2, 2, 6),
                 to = c(2, 4, 3, 5, 3))

g <- df |> graph_from_data_frame()
i <- g |> degree(mode = "out") > 0

lapply(V(g)[i], \(x) all_simple_paths(g, from = x, mode = "out"))
#> $`1`
#> $`1`[[1]]
#> + 2/6 vertices, named, from c3ceef6:
#> [1] 1 2
#> 
#> $`1`[[2]]
#> + 3/6 vertices, named, from c3ceef6:
#> [1] 1 2 3
#> 
#> $`1`[[3]]
#> + 3/6 vertices, named, from c3ceef6:
#> [1] 1 2 5
#> 
#> $`1`[[4]]
#> + 2/6 vertices, named, from c3ceef6:
#> [1] 1 4
#> 
#> 
#> $`2`
#> $`2`[[1]]
#> + 2/6 vertices, named, from c3ceef6:
#> [1] 2 3
#> 
#> $`2`[[2]]
#> + 2/6 vertices, named, from c3ceef6:
#> [1] 2 5
#> 
#> 
#> $`6`
#> $`6`[[1]]
#> + 2/6 vertices, named, from c3ceef6:
#> [1] 6 3

^{由 reprex package 于 2022 年 9 月 4 日创建(v2.0.1)}