如何找到从根开始的所有连通顶点，但按照从最内层到最外层的顺序？

Question

假设我有如下数据：

test_df_4 <- data.frame(inner_obj= c(1, 3, 2, 6, 5),
                        outer_obj = c(3, 4, 1, 7, 6))

我看到有两个单独的对象，第一个由：

1, 2, 3, 4

组成，第二个由：

5, 6, 7

组成。我的理解是，

2

进入

1

，然后

1

进入

3

，最后

3

进入

4

。对于第二个对象，它是：

5

进入

6

，

6

进入

7

。就我而言，这些是彼此嵌套的代码块，因此要计算

4

，我需要从

2

开始，然后是

1

，然后是

3

，然后是

4

。对于第二个对象：我需要从

5

开始，然后是

6

，然后是

7

。

我想获得一个具有此顺序的列表 - 对于第一个对象，它应该是

2, 1, 3, 4

，对于第二个对象：

5, 6, 7

。

我知道如何找到起点（根）：

root <- igraph::degree(igraph::graph_from_data_frame(test_df_4), mode = "in")
  root <- as.integer(names(root)[which(root == 0)])

但是我仍然有一个问题，我应该使用什么函数来获得所需的订单。我更喜欢使用

igraph

包。

预期输出：

list(c(2, 1, 3, 4),
     c(5, 6, 7))

或类似的东西，即区分单独的对象/图形的顺序和可能性是最重要的。

Answer 1

您可以将根节点输入

igraph::all_simple_paths

并为每个根选择最长的：

library(igraph)

g <- graph_from_data_frame(test_df_4)

result <- lapply(which(degree(g, mode = "in") == 0), function(x) {
  V(g)$name[unname(unlist(tail(all_simple_paths(g, x), 1)))] |>
    as.integer()
}) |> unname()

这给出了

result
#> [[1]]
#> [1] 2 1 3 4
#> 
#> [[2]]
#> [1] 5 6 7