Boost图库中两个节点之间的所有路径

I need to find all simple (non-cyclic) paths between two nodes in a graph. I understand how to achieve this with a modified Breadth-First-Search, and so was looking at the BFS in Boost, but I can't see how I could alter the steps of the algorithm, only the visitor.

我需要在图中的两个节点之间找到所有简单(非循环)路径。我理解如何通过改进的广度优先搜索来实现这一点,因此在Boost中查看BFS,但我看不出如何改变算法的步骤,只有访问者。

Before I go ahead and write a new algorithm from scratch, is there a way to achieve this in BGL by using an existing algo, with or without a custom visitor?

在我从头开始编写新算法之前,有没有办法通过使用现有的算法在BGL中实现这一点,无论是否有自定义访问者?

1 个解决方案

#1

We need to know a little more about your graph probably. I had a "similar" problem.

我们需要更多地了解您的图表。我有一个“类似”的问题。

This may not be exactly what you are looking for, but it is similar. This is a DFS visitor I used on a directed graph with a root to count the number of paths from the start node to all other (reachable) nodes.

这可能不是您正在寻找的,但它是相似的。这是我在带有根的有向图上使用的DFS访问者,用于计算从起始节点到所有其他(可到达)节点的路径数。

This works because my graph is a DAG that is rooted. I have to reverse the graph first so that my start node is actually a sink node. The source node then becomes the root of the DAG. If I wanted the actual paths I might add a stack that tells the path history. Boost图库中两个节点之间的所有路径

这是有效的,因为我的图是一个根植的DAG。我必须首先反转图形,以便我的起始节点实际上是一个汇聚节点。然后,源节点成为DAG的根。如果我想要实际路径,我可能会添加一个告诉路径历史的堆栈。

//depth first search to calculate path number, calculates the number of paths to a target
// conceptually equivalent to a topological sort.
class PathNumDFSVisitor:public boost::default_dfs_visitor{

public:
    PathNumDFSVisitor(boost::unordered_map<std::string,std::size_t>& inMap):pathNumMap(inMap){}

    template < typename Vertex, typename Graph >
    void finish_vertex(Vertex u, const Graph & g)
    {
        std::string term = g[u].termId;

        if(boost::out_degree(u,g) == 0){
            pathNumMap[term] = 1;
        }else{
            pathNumMap[term] = 0;
            //Iterate over the children of the term to add the child annotations
            typename boost::graph_traits< Graph >::out_edge_iterator ei, e_end;
            for(tie(ei, e_end) = boost::out_edges(u, g); ei != e_end; ++ei){

                Vertex v = boost::target(*ei, g);

                std::string childTermId = g[v].termId;
                pathNumMap[term] += pathNumMap[childTermId];
            }
        }
    }

    boost::unordered_map<std::string,std::size_t>& pathNumMap;
};

In the general case though, I would suggest calculating a shortest path and then taking each edge in turn and finding a alternate route from source to target. Now that edge could be two or more edges, which in turn would need to be relaxed and considered for alternate paths. Like Sehe said, it would be a generator, and also it could quickly explode in a general undirected graph. Maybe if we know a little more about your graph constraints we could help more.

但是,在一般情况下,我建议计算一条最短路径,然后依次取每条边并找到从源到目标的备用路径。现在该边缘可以是两条或更多条边,而这又需要放宽并考虑用于替代路径。像Sehe所说,它将是一个发电机,并且它可以在一般的无向图中快速爆炸。也许如果我们对您的图形约束有更多了解,我们可以提供更多帮助。

Maybe adding a maximum path length condition could help constrain the number simple paths you are generating.

也许添加最大路径长度条件可以帮助约束您生成的简单路径数。

Consider this general fully connected graph. Boost图库中两个节点之间的所有路径

考虑这个通用的完全连接图。

We need to calculate all paths between A and B.

我们需要计算A和B之间的所有路径。

So we need all 1 edge paths + all 2 edge paths plus ...

所以我们需要所有1条边路径+所有2条边路径加上......

So we need A - B, one edge.

所以我们需要A - B,一个边缘。

Then all 2 edge paths. A - ? - B, there are 3

然后是所有2条边路径。一个 - ? - B,有3个

Then all 3 edge paths A - ? - ? - B, There are 3 * 2.

然后所有3条边路径A - ? - ? - B,有3 * 2。

And so on with 4 or more edges.

等等有4个或更多边。

You can see as N grows we get up to N-2 * N-3 * N-4 ... and so on. This is a factorial explosion, O(N!).

你可以看到N增长我们达到N-2 * N-3 * N-4 ......等等。这是一个因子爆炸,O(N!)。

These examples illustrate how different topologies can lead to very different algorithms and complexity. To get a straight/helpful answer out of SO give any details that will help.

这些示例说明了不同拓扑如何导致非常不同的算法和复杂性。从SO获得直接/有用的答案给出任何有用的细节。

#1