如何找到“直接”连接的组件？

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

我想这就是你想要的

lapply(
  V(g)[degree(g, mode = "in") == 0],
  function(x) V(g)[!is.infinite(distances(g, x, mode = "out"))]
)

这给

$`1`
+ 5/6 vertices, named, from d7ae5cb:
[1] 1 2 4 3 5

$`6`
+ 2/6 vertices, named, from d7ae5cb:
[1] 6 3

如果希望将结果保存在data.frame中，可以尝试

transform(
  stack(
    lapply(
      V(g)[degree(g, mode = "in") == 0],
      function(x) names(V(g)[!is.infinite(distances(g, x, mode = "out"))])
    )
  ),
  ind = as.integer(factor(ind))
)

这给

  values ind
1      1   1
2      2   1
3      4   1
4      3   1
5      5   1
6      6   2
7      3   2