r - 如何从邻接表中找到循环路径

Question

我有一个有向子图，其中所有节点都在一个循环中(有 21 个节点和约 250 条边)，我想知道节点形成循环的顺序。

我不熟悉图形算法。我想过使用igraph::graph.dfs 函数来处理原图或反向图。并使用返回的 order 或 order.out 作为订单，但没有成功。

子图是用 igraph::clusters 找到的强连通分量

我问了一个similar question但是 graph.get.subisomorphisms.vf2 在我的例子中运行时间太长。

我在想如果我能得到一个这样的有序邻接表，我也许能找到从最长列表开始的循环

但我只能使用 igraph::get.adjlist 获取无序列表，我想知道是否有一种方法可以获取如下所示的有序列表。

找到循环的节点顺序有什么建议吗？

提前致谢!

数据

> dput(adjlist)
structure(list(`26` = c(2, 3, 4, 5, 6, 7, 8, 10, 11, 15, 16, 
18, 19), `2` = c(1, 3, 4, 5, 6, 7, 8, 10, 15, 16, 18), `30` = c(1, 
2, 4, 5, 6, 7, 8, 10, 11, 14, 15, 16, 17, 18, 19, 21), `25` = c(1, 
2, 3, 5, 6, 7, 8, 9, 10, 11, 15, 16, 18, 21), `29` = c(1, 2, 
3, 4, 6, 7, 8, 9, 10, 11, 15, 16, 18, 21), `9` = c(1, 2, 3, 4, 
5, 7, 8, 10, 14, 15, 16, 18, 19), `27` = c(1, 2, 3, 4, 5, 6, 
8, 14, 15, 18), `13` = c(3, 4, 5, 15), `14` = c(1, 2, 3, 4, 5, 
6, 7, 8, 10, 11, 14, 15, 16, 18, 19, 21), `8` = c(1, 2, 3, 4, 
5, 6, 7, 8, 14, 15, 16, 18), `23` = c(1, 2, 3, 4, 5, 6, 7, 8, 
10, 14, 15, 16, 17, 18, 19), `20` = c(1, 2, 3, 4, 5, 6, 7, 8, 
9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21), `19` = c(1, 2, 
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 21), 
    `17` = c(1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 15, 16, 17, 18, 
    21), `12` = c(3, 4, 5, 6, 8), `24` = c(4, 6, 7, 8, 9, 10, 
    11, 15), `21` = c(13, 14), `6` = c(2, 3, 4, 5, 6, 8, 10, 
    15), `28` = c(1, 7, 11, 16), `15` = c(1, 2, 3, 4, 5, 6, 7, 
    8, 9, 10, 11, 14, 15, 16, 17, 18, 19, 21), `11` = c(3, 4, 
    5, 6, 8, 15)), .Names = c("26", "2", "30", "25", "29", "9", 
"27", "13", "14", "8", "23", "20", "19", "17", "12", "24", "21", 
"6", "28", "15", "11"))

Answer 1

只是为了确保正确理解问题:您有一个由强连通分量的顶点导出的有向图的子图。您想要的是一个包含组件所有顶点的循环。两个可能的版本(请参阅 the introductory paragraphs here 以澄清在这方面发展起来的令人困惑的术语):

a) 允许每个顶点在循环中恰好出现一次，即您想要一个简单的循环，其中每个顶点恰好与循环的两条边重合。找到这样一个循环是Hamiltonian Cycle问题，复杂性理论的主要内容，它是 NP 难的；没有人知道对此有有效的算法。

b) 允许顶点与循环的两条以上边相邻，即您希望闭合遍历组件。您可以通过识别连接组件的循环来做到这一点(您应该能够从识别强连接组件的算法中足够容易地提取这些循环)，然后构建一个 Eulerian Cycle您找到的循环的并集，忽略组件中的所有其他边缘。这是可能的，而且实现起来应该相当简单。