如何按循环长度升序迭代简单循环？

Question

我想找到图的所有节点，这些节点处于长度不超过某个给定最大循环长度的简单循环中

max_length

。除此之外，我想制作每个节点所包含的周期数（每个周期长度）的直方图。我试图找出完成此任务的最佳方法。

相关问题：
对于给定的节点，如何找到该节点所属的小循环？是一个相关问题，比这里的这个问题更具体。它们不是重复的。

我使用 python 和 graph-tool 来分析图形，这似乎是一个不错的选择，因为多项测试表明 graph-tool 是世界顶级性能图形库之一，尤其是。对于蟒蛇。我更喜欢使用 python 来做这件事。特别是，其他任务不够快（networkx）或时间复杂度很差（igraph 中的边缘删除），因此无法根据我需要的其他任务进行扩展。

以下是我的方法想法：

想法1：
按循环长度升序迭代图表的所有循环，并记下其中的节点。

想法 1.1。 （跟进想法 1。）：
有函数

graph_tool.topology.all_circuits

，但它似乎不仅仅迭代简单的循环，或者不按照我想要的顺序迭代。我真的不知道它到底是做什么的。我只知道我不能使用它，因为它的时间复杂度与我的图表呈爆炸式增长。例如。对于只有 34 个节点的小型 Zachary's karate Club，它发现了 1462130 个循环。我想分析具有大约 200 万个节点和 400 万条边的图。我尝试运行

graph_tool.topology.all_circuits

来绘制这样的图表，但这样我什至看不到许多我感兴趣的较短周期。我估计，使用这种方法对像我要分析的图这样的图进行循环搜索将运行几年。插图：

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\tcircuit")
circuit_iter = graph_tool.topology.all_circuits(g)
i = 0
for circuit in circuit_iter:
    i += 1
    if i % 152371 == 0:
        print(f"{i}\t{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

想法 1.2。 （跟进想法 1。）：
我自己实施想法 1。可行，但这听起来像是一项艰巨的工作。我不想再发明轮子了。有更好的办法吗？

想法2：
作为想法 1 的替代方案，也可以按照循环长度升序对每个节点迭代包含给定节点的循环。这可以通过从有问题的节点开始的广度优先搜索 (BFS) 来完成。
这样我就可以检查所述周期中节点的成员资格，然后继续到下一个节点。这效率较低，因为我将为同一循环中包含的每个节点重复处理循环，但它仍然会给出合理的总体时间复杂度。
这种方法的一大优点是实现会比想法 1 更容易。

有更好的方法吗？图形工具是否提供了更适合此任务的工具？

Answer 1

这里有一些 C++ 代码，用于构建图中每个节点所属的周期数的直方图。

这使用 PathFinder 图论库中的深度优先搜索循环查找器。 https://github.com/JamesBremner/PathFinder

处理 Zachary 测试数据集需要 4 毫秒才能找到 42 个周期，而构建直方图则需要 2 微秒。

主要代码如下：

void findCycles()
{
    raven::set::cRunWatch aWatcher("findCycles");

    /* find cycles in graph
    using modified depth first search
    in PathFinder graph theory library
    https://github.com/JamesBremner/PathFinder
    */
   
    vCycle = dfs_cycle_finder(gd);

}
void histogram()
{
    raven::set::cRunWatch aWatcher("histogram");

    nodeCycleCount.resize(gd.g.vertexCount());
    for (auto &vc : vCycle)
    {
        for (int v : vc)
        {
            nodeCycleCount[v]++;
        }
    }
}

main(int argc, char *argv[])
{
    raven::set::cRunWatch::Start();

    if (argc != 2)
    {
        std::cout << "Usage\n";
        exit(1);
    }
    read(argv[1]);

    findCycles();

    std::cout << vCycle.size() << " cycles found\n";

    histogram();

    std::cout << "Node\tCycles\n";
    for (int n = 0; n < nodeCycleCount.size(); n++)
    {
        std::cout << gd.g.userName(n) << "\t" << nodeCycleCount[n] << "\n";
    }

    raven::set::cRunWatch::Report();

    return 0;
}

完整的应用程序代码位于https://github.com/JamesBremner/so77686189

这是输出：

42 cycles found
Node    Cycles
3       17
1       21
2       10
4       7
5       2
6       4
7       4
8       3
9       4
10      1
11      2
12      0
13      1
14      6
17      1
18      1
20      3
22      2
26      3
24      5
25      3
28      3
29      2
30      4
27      1
31      5
32      9
33      24
15      1
16      1
19      1
21      1
23      1
34      25
raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
       1        0.0035151       0.0035151       findCycles
       1        2e-06   2e-06   histogram