如何用graph-tool查找指定节点的指定最大长度短周期？

我正在用Python和graph-tool进行图分析，需求是：在图g中找到给定节点node所属的、长度不超过max_length的所有简单周期。

为什么不使用all_circuits？ #

我试过graph_tool.topology.all_circuits，但该方法效率极低：仅34个节点的Zachary空手道俱乐部图，它就会找出1462130个周期，对于超过200万节点的图来说完全无法运行。测试代码及输出如下：

import graph_tool.collection
import graph_tool.topology

g = graph_tool.collection.data["karate"]

print("number of nodes in graph:", g.num_vertices())

print()
print(f"circ_idx	circuit")
circuit_iter = graph_tool.topology.all_circuits(g)
i = 0
for circuit in circuit_iter:
    i += 1
    if i % 152371 == 0:
        print(f"{i}	{circuit}")

print("total number of circuits:", i)

输出：

number of nodes in graph: 34

circ_idx        circuit
152371  [ 0  3  1 13  2 28 31 25 24 27 33 29 23 32  8]
304742  [ 0  7  1 30 32 23 33 27 24 25 31 28  2  3 12]
457113  [ 0  8 30  1 19 33 18 32 29 23 25 24 31]
609484  [ 0  8 33 27 24 25 23 29 32  2  3]
761855  [ 0 13  1  7  3  2 32 31 25 23 33 19]
914226  [ 0 17  1  7  3  2 32 31 24 27 23 29 33 30  8]
1066597 [ 0 19 33 27 24 25 23 29 32 30  1  3]
1218968 [ 0 31 24 27 23 29 26 33 22 32  2  3 12]
1371339 [ 0 31 32 23 25 24 27 33 13  3  2  1 30  8]
total number of circuits: 1462130

尝试graph-tool的BFS工具失败 #

我认为最优方案是从node出发做广度优先搜索（BFS），找到该节点所属的短周期，达到max_length时停止搜索。但尝试graph_tool.search.bfs_iterator和graph_tool.search.bfs_search后，发现它们无法检测周期，测试代码及输出如下：

import graph_tool.collection
import graph_tool.search

g = graph_tool.collection.data["karate"]
print("number of nodes in graph:", g.num_vertices())

print()
print("adjacencies")
for src in range(5):
    neighbors_list = g.get_all_neighbors(src)
    neighbors_list.sort()
    print("   ", src, neighbors_list)
print("    ...")

node = 0

print()
print("graph_tool.search.bfs_iterator")
bfs_iter = graph_tool.search.bfs_iterator(g, node)
for edge in bfs_iter:
    src = g.vertex_index[edge.source()]
    tar = g.vertex_index[edge.target()]
    found = "   ############################## cycle found!!!" if tar == node else "   no cycle found"
    print("   ", src, tar, found)

输出：

number of nodes in graph: 34

adjacencies
    0 [ 1  2  3  4  5  6  7  8 10 11 12 13 17 19 21 31]
    1 [ 0  2  3  7 13 17 19 21 30]
    2 [ 0  1  3  7  8  9 13 27 28 32]
    3 [ 0  1  2  7 12 13]
    4 [ 0  6 10]
    ...

graph_tool.search.bfs_iterator
    0 1    no cycle found
    0 2    no cycle found
    0 3    no cycle found
    0 4    no cycle found
    0 5    no cycle found
    0 6    no cycle found
    0 7    no cycle found
    0 8    no cycle found
    0 10    no cycle found
    0 11    no cycle found
    0 12    no cycle found
    0 13    no cycle found
    0 17    no cycle found
    0 19    no cycle found
    0 21    no cycle found
    0 31    no cycle found
    1 30    no cycle found
    2 9    no cycle found
    2 27    no cycle found
    2 28    no cycle found
    2 32    no cycle found
    5 16    no cycle found
    8 33    no cycle found
    31 24    no cycle found
    31 25    no cycle found
    27 23    no cycle found
    32 14    no cycle found
    32 15    no cycle found
    32 18    no cycle found
    32 20    no cycle found
    32 22    no cycle found
    32 29    no cycle found
    33 26    no cycle found

graph_tool.search.bfs_search结合BFSVisitor是另一种BFS实现方式，但同样无法检测周期（更新：我对该结论存疑）。

提问 #

我是否必须自行实现BFS来进行周期检测？自行用Python实现效率会很低，有没有更好的替代方案？

内容的提问来源于Stack Exchange，提问作者Daniel S.