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