Re: [Boost-users] BGL: Average path distance implementation

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-07-22 12:02:57

On Jul 21, 2005, at 9:46 AM, P.Saffrey wrote:

> I am writing a graph application using BGL where a key component is 
> cycle
> detection. I need to know how long a cycle is. I can use breadth first
> search, but that gives me the shortest path. What I want is the average
> path length.

Interesting. Enumerating all of the paths in a graph can get very, very 
expensive, but you might be able to count them efficiently. I don't 
have an algorithm in mind at the moment, so...

> I have an idea for an algorithm for this: basically do a breadth first
> search, disallowing any edge if it's been used before in this path and
> then take the mean of all the complete paths from the node to itself.
> Can anybody give me some clues as to how I can implement this? I would
> prefer to use the pucker event visitor approach, but I'm not sure 
> whether
> I can use this to alter the search process. I'll need to cull a path 
> from
> the search if it encounters a node with no outgoing edges that haven't
> been used already. I'm also not sure how to collect all the path 
> lengths
> at the end.

There are three ways you can alter the search process. Which ones you 
choose depends on your algorithm:

   1) Make the visitor change the color map. For instance, you could 
write an "examine_edge" function in the visitor that sets the target of 
the edge to gray or black, so that it won't enter the queue.

   2) Replace the queue: If you want to visit vertices in a different 
order (or even trick BFS into visiting the same vertex twice!) you can 
supply your own queue, which can order vertices however it wants. 
Dijkstra's algorithm does this.

   3) Use a filtered_graph: If you need to filter out arbitrary edges or 
vertices, you can use the filtered_graph adaptor to do so. This sounds 
like the best fit for your application.

        Doug