[Boost-users] BGL: Average path distance implementation

From: P.Saffrey (ucacpgs_at_[hidden])
Date: 2005-07-21 09:46:59

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.

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.

Peter

-- 
P.Saffrey_at_[hidden]		http://www.cs.ucl.ac.uk/staff/P.Saffrey/
Beacon Project			http://www.grid.ucl.ac.uk/biobeacon/