[Boost-users] [BGL] Problem with counting paths/custom dfs_visitor

From: Pete Donnell (p.donnell_at_[hidden])
Date: 2005-03-29 09:23:10

Hi,

I hope you will forgive me for asking a rather simple question. I have 
been having a lot of trouble writing a visitor for use in depth first 
search.

The algorithm I'm attempting to write is supposed to count the number of 
different paths between two vertices on a directed graph. The graph may 
or may not contain cycles, and of course walks that contain cycles are 
not counted as paths. The way I've approached the problem is to induce a 
subgraph on the source and sink vertices, by copying the graph and then 
removing any vertices that do not lie on a path between the source and 
sink. My plan then is to do a depth first search on the induced 
subgraph, using a custom visitor that counts the number of forward or 
cross edges, which I think will be a count of the number of paths 
between the source and sink. To be honest, I haven't thought too hard 
about whether this is algorithmically correct, as the main problem is 
with the visitor. If I figure out to write custom visitors then it 
shouldn't be too hard to write other algorithms.

As things stand, the function to induce a subgraph is working fine 
(although I am not using the Boost subgraph, mainly because it isn't 
documented in the book and so I didn't become aware of its existence 
until after I'd written the code). Incidentally, this function is useful 
in itself, which is why I have used it. I'm aware that it's not a very 
efficient way of solving the problem. The code I've written for the 
visitor to call on the path counting algorithm currently goes like this 
(I have slightly modified it a lot of times to try and get it to work):

template<typename OutputIterator> class EnumeratorVisitor : public 
boost::dfs_visitor<OutputIterator>
{
private :
     long unsigned int pathCount;

public :
     EnumeratorVisitor() : boost::default_dfs_visitor(), pathCount(1) {}
     EnumeratorVisitor(OutputIterator out) : 
boost::dfs_visitor<OutputIterator> (out), pathCount (1) {}

     long unsigned int getPathCount() const
     {
         return pathCount;
     }

     template <typename Graph, typename Edge>
     void forward_or_cross_edge(const Edge& e, const Graph& g)
     {
         ++pathCount;
     }
};

The code where I use it looks like this:

template<typename Graph>
long unsigned int enumeratePaths(const Graph& graph,
                  const typename 
boost::graph_traits<Graph>::vertex_descriptor& startNode,[BGL] problem with
                  const typename 
boost::graph_traits<Graph>::vertex_descriptor& endNode)
{
     typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
     std::vector<Edge> forwardOrCrossEdges;    // vector used to store 
the forward or cross edges

     Graph* tempGraph = generateSubGraph(graph, startNode, endNode); // 
this function induces a subgraph as previously mentioned

     typedef boost::color_traits<boost::default_color_type> Colour;
     std::vector<boost::default_color_type> 
colourMap(boost::num_vertices(*tempGraph), Colour::white());

     EnumeratorVisitor<typename std::back_insert_iterator<typename 
std::vector<Edge> > > edgeInserter(std::back_inserter(forwardOrCrossEdges));
     depth_first_visit(graph, startNode, edgeInserter,
                 boost::make_iterator_property_map(colourMap.begin(),
                     boost::get(boost::vertex_index, *tempGraph))    );

     return edgeInserter.getPathCount();
}

I'm sure there are obvious errors in there to those who know what 
they're doing, but I've been looking at this problem for over a month 
now without success, so it's got to that stage where I don't really know 
what's going on anymore. I've hunted through the book, online code and 
so on, but I can't figure it out. It gives about three pages of template 
errors at the moment! There have been other minor variants, but all of 
them have given errors of some kind.

If anyone can point out what I'm doing wrong, I'd greatly appreciate it. 
If more information is needed, I'll happily provide it. By the way, I'm 
sure that this problem of path counting has been approached before, it 
anyone has any insights to offer, I'd also appreciate that!

Many thanks for your time,

Pete