All paths between two nodes in Boost Graph Library

Question

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.

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?

Answer 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.

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.

//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.

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

Consider this general fully connected graph.

We need to calculate all paths between A and B.

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

So we need A - B, one edge.

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

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

And so on with 4 or more edges.

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!).

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.