用于计算有向图上非循环路径数量的快速算法

Question

简而言之，我需要一个快速算法来计算简单有向图中有多少条非循环路径。

我所说的“简单”图是指没有自循环或多个边的图。 路径可以从任何节点开始，并且必须以没有传出边的节点结束。如果一条路径中没有边出现两次，则该路径是非循环。

我的图（经验数据集）只有 20-160 个节点，但是，其中一些节点有很多循环，因此会有大量路径，而我的天真的方法对于某些图来说根本不够快我有。

我当前正在做的是使用递归函数沿着所有可能的边缘“下降”，同时跟踪我已经访问过的节点（并避免它们）。迄今为止最快的解决方案是用 C++ 编写的，并在递归函数中使用 std::bitset 参数来跟踪已访问的节点（已访问的节点由位 1 标记）。该程序在示例数据集上运行 1-2 分钟（取决于计算机速度）。对于其他数据集，运行需要一天多的时间，或者显然更长。

示例数据集：http://pastie.org/1763781 （每行都是一个边对）

示例数据集的解决方案（第一个数字是我开始的节点，第二个数字是从该节点开始的路径计数，最后一个数字是总路径计数）： http://pastie.org/1763790

如果您对更好的算法有任何想法，请告诉我复杂。我也对近似解决方案感兴趣（使用某种蒙特卡罗方法估计路径数量）。最终我还想测量平均路径长度。

编辑：也在 MathOverflow 上以相同的标题发布，因为它可能在那里更相关。希望这不违反规则。无法链接，因为网站不允许超过 2 个链接...

Answer 1

看起来这就是#P-完整的。 （参考http://www.maths.uq.edu.au /~kroese/ps/robkro_rev.pdf）。该链接有一个近似值

如果您可以放宽简单路径要求，您也可以使用 Floyd-Warshall 的修改版本或图形指数有效地计算路径数。请参阅所有对图表上的所有路径

Answer 2

正如 spin_plate 所提到的，这个问题是 #P-complete 所以开始寻找你的近似值:)。我真的很喜欢这个问题的#P-完整性证明，所以我认为分享它会很好：

设 N 为图中的路径数（从 s 开始）和 p_k是长度k的路径数。我们有：

N = p_1 + p_2 + ... + p_n

现在通过将每条边更改为一对平行边来构建第二个图。对于长度为 k 的每条路径，现在将有 k^2 条路径，因此：

N_2 = p_1*2 + p_2*4 + ... + p_n*(2^n)

重复此过程，但使用 i 条边而不是 2, up n，将为我们提供一个线性系统（带有范德蒙矩阵），使我们能够找到 p_1, ..., p_n。

N_i = p_1*i + p_2*(i^2) + ...

因此，查找图中的路径数量与查找特定长度的路径数量一样困难。特别是，p_n 是哈密顿路径的数量（从 s 开始），这是一个真正的 #P 完全问题。

---

我还没有做过数学计算，我也猜测类似的过程应该能够证明仅计算平均长度也很困难。

---

注意：大多数时候讨论这个问题的路径都是从单边开始并在任何地方停止。这与您的问题相反，但您应该通过反转所有边缘来等效。

Answer 3

问题陈述的重要性

目前尚不清楚正在计算什么。

1. 起始节点集是至少有一个出边的所有节点，还是有特定的起始节点标准？
2. 结束节点集是具有零个出边的所有节点的集合，还是可以具有至少一个入边的任何节点作为可能的结束节点？

定义你的问题，以免出现歧义。

估计

当为随机构建的有向图设计时，估计可能会出现几个数量级的偏差，并且该图在其构造上在统计上非常倾斜或系统化。这是所有估计过程的典型特征，但在图表中尤其明显，因为它们具有指数模式复杂性潜力。

两个优化点

对于大多数处理器架构，std::bitset 模型将比 bool 值慢，因为指令集机制会在特定位偏移处测试位。当内存占用而不是速度是关键因素时，位集更有用。

消除案件或减少通过扣除很重要。例如，如果存在只有一个出边的节点，则可以计算没有该出边的路径数，并将从其指向的节点开始的路径数添加到子图中的路径数。

诉诸集群

问题可以按照起始节点分布在集群上执行。有些问题只需要超级计算即可解决。如果您有 1,000,000 个起始节点和 10 个处理器，则可以在每个处理器上放置 100,000 个起始节点案例。上述案例的消除和减少应在分发案例之前完成。

典型的深度优先递归以及如何优化它

这是一个小程序，提供基本的深度优先、从任何节点到任何节点的非循环遍历，可以更改、放置在循环中或分布式。如果最大数据集大小已知，则可以使用以大小作为参数的模板将该列表放入静态本机数组中，从而减少迭代和索引时间。

#include <iostream>
#include <list>

class DirectedGraph {

    private:
        int miNodes;
        std::list<int> * mnpEdges;
        bool * mpVisitedFlags;

    private:
        void initAlreadyVisited() {
            for (int i = 0; i < miNodes; ++ i)
                mpVisitedFlags[i] = false;
        }

        void recurse(int iCurrent, int iDestination,
               int path[], int index,
               std::list<std::list<int> *> * pnai) {

            mpVisitedFlags[iCurrent] = true;
            path[index ++] = iCurrent;

            if (iCurrent == iDestination) {
                auto pni = new std::list<int>;
                for (int i = 0; i < index; ++ i)
                    pni->push_back(path[i]);
                pnai->push_back(pni);

            } else {
                auto it = mnpEdges[iCurrent].begin();
                auto itBeyond = mnpEdges[iCurrent].end();
                while (it != itBeyond) {
                    if (! mpVisitedFlags[* it])
                        recurse(* it, iDestination,
                                path, index, pnai);
                    ++ it;
                }
            }

            -- index;
            mpVisitedFlags[iCurrent] = false;
        } 

    public:
        DirectedGraph(int iNodes) {
            miNodes = iNodes;
            mnpEdges = new std::list<int>[iNodes];
            mpVisitedFlags = new bool[iNodes];
        }

        ~DirectedGraph() {
            delete mpVisitedFlags;
        }

        void addEdge(int u, int v) {
            mnpEdges[u].push_back(v);
        }

        std::list<std::list<int> *> * findPaths(int iStart,
                int iDestination) {
            initAlreadyVisited();
            auto path = new int[miNodes];
            auto pnpi = new std::list<std::list<int> *>();
            recurse(iStart, iDestination, path, 0, pnpi);
            delete path;
            return pnpi;
        }
};

int main() {

    DirectedGraph dg(5);

    dg.addEdge(0, 1);
    dg.addEdge(0, 2);
    dg.addEdge(0, 3);
    dg.addEdge(1, 3);
    dg.addEdge(1, 4);
    dg.addEdge(2, 0);
    dg.addEdge(2, 1);
    dg.addEdge(4, 1);
    dg.addEdge(4, 3);

    int startingNode = 0;
    int destinationNode = 1;

    auto pnai = dg.findPaths(startingNode, destinationNode);

    std::cout
            << "Unique paths from "
            << startingNode
            << " to "
            << destinationNode
            << std::endl
            << std::endl;

    bool bFirst;
    std::list<int> * pi;
    auto it = pnai->begin();
    auto itBeyond = pnai->end();
    std::list<int>::iterator itInner;
    std::list<int>::iterator itInnerBeyond;
    while (it != itBeyond) {
        bFirst = true;
        pi = * it ++;
        itInner = pi->begin();
        itInnerBeyond = pi->end();
        while (itInner != itInnerBeyond) {
            if (bFirst)
                bFirst = false;
            else
                std::cout << ' ';
            std::cout << (* itInner ++);
        }
        std::cout << std::endl;
        delete pi;
    }

    delete pnai;

    return 0;
}