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

From: Pete Donnell (p.donnell_at_[hidden])
Date: 2005-04-11 05:25:38

Pete Donnell wrote:

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

Well, in case anyone's interested, having not received any information 
about how to implement custom visitors I was unable to use the boost dfs 
function. However, the problem was easy to solve using a hand written 
recursive dfs function (although this was, of course, largely missing 
the point of the BGL generic code).