快速算法指望有向图的无环路径的数量 [英] Fast algorithm for counting the number of acyclic paths on a directed graph

问题描述

总之，我需要一个快算法来计算有多少非循环路径是有一个简单的定向图。

In short, I need a fast algorithm to count how many acyclic paths are there in a simple directed graph.

到简单的图我的意思是一个没有自我循环或多个边缘。 A 路径的可以从任何节点开始，必须结束这种没有出边的节点上。路径是无环的，如果出现两次没有在它的边缘。

By simple graph I mean one without self loops or multiple edges. A path can start from any node and must end on a node that has no outgoing edges. A path is acyclic if no edge occurs twice in it.

我的图表（经验数据集）都只有20-160之间的节点，但是，他们中的一些有很多次在其中，因此也将是一个非常大的数字的路径，我幼稚的做法是根本不够快一些图中的我。

My graphs (empirical datasets) have only between 20-160 nodes, however, some of them have many cycles in them, therefore there will be a very large number of paths, and my naive approach is simply not fast enough for some of the graph I have.

我在做什么现在是降以及使用递归函数的所有可能的边缘，同时跟踪其中的节点我已经访问了（并避免它们）。最快的解决方案，我至今是用C ++编写，并使用递归函数的std :: bitset的参数来跟踪哪些节点已经访问（访问节点的标志是第1位）。该程序在1-2分钟（取决于计算机的速度）样本数据集运行。与其他数据集，它运行，或需要一天以上的时间明显更长的时间。

What I'm doing currently is "descending" along all possible edges using a recursive function, while keeping track of which nodes I have already visited (and avoiding them). The fastest solution I have so far was written in C++, and uses std::bitset argument in the recursive function to keep track of which nodes were already visited (visited nodes are marked by bit 1). This program runs on the sample dataset in 1-2 minutes (depending on computer speed). With other datasets it takes more than a day to run, or apparently much longer.

样本数据集： http://pastie.org/1763781 （每一行是一个边沿对）

The sample dataset: http://pastie.org/1763781 (each line is an edge-pair)

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

Solution for the sample dataset (first number is the node I'm starting from, second number is the path-count starting from that node, last number is the total path count): http://pastie.org/1763790

请让我知道如果你对一个更好的复杂算法的想法。我也有兴趣的近似解（估计路径与一些蒙特卡罗方法的数量）。最后，我也想测量平均路径长度。的

编辑：还贴MathOverflow下相同的标题，因为它可能是更相关的存在。希望这不是违反规则。无法链接的网站将不会允许超过2链接...

also posted on MathOverflow under same title, as it might be more relevant there. Hope this is not against the rules. Can't link as site won't allow more than 2 links ...

推荐答案

这是＃P-完整的，它似乎。 （参见<一个href="http://www.maths.uq.edu.au/~kroese/ps/robkro_rev.pdf">http://www.maths.uq.edu.au/~kroese/ps/robkro_rev.pdf).该链接有一个近似

This is #P-complete, it seems. (ref http://www.maths.uq.edu.au/~kroese/ps/robkro_rev.pdf). The link has an approximation

如果你可以放松的简单路径的要求，可以有效地计算路径用弗洛伊德 - 沃肖尔或图形幂的修改版本，以及数量。请参见全部对所有路径上的图形....

If you can relax the simple path requirement, you can efficiently count the number of paths using a modified version of Floyd-Warshall or graph exponentiation as well. See All pairs all paths on a graph....

这篇关于快速算法指望有向图的无环路径的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！