[Boost-users] BGL Question/Advice which algorithm to use

From: Elisha Berns (e.berns_at_[hidden])
Date: 2005-07-06 18:12:33

Hi,

This is a request for some advice/recommendations regarding which
algorithm(s) to use with Boost.Graph to solve a graph sorting problem
for graphs that are *almost, but not quite* DAGs.  If anybody has some
insight into this type of situation help will be greatly appreciated.

Ideally I do a topological sort to find the most dependent vertex (if
that makes sense) which then becomes the root of an n-ary tree, and then
build the tree from that vertex recursively finding the out-edges of
child vertices.  All that works provided the graph is actually a DAG.
But sometimes it isn't because there can be small cycles(?) inside the
graph where one vertex refers to its parent's parent's vertex.  So
everything in the graph can be suitable for a DAG except for this small
set of vertices that becomes self-referential.

This small set of vertices, while not expendable, is certainly never
going to contain the desired vertex to create a root, for various
reasons.  So during the search phase they can be safely ignored, at
least that's a fairly safe operating assumption as of now.

I still need to find the most dependent vertex, and I can't use
topological sort here, so what algorithm can I use?  Or if I still need
to use topological sort here, would I clone the graph object and remove
this set of vertices to create a DAG for the sake of the sort?

Many thanks,

Elisha Berns
e.berns_at_[hidden]
tel. (310) 556 - 8332
fax (310) 556 - 2839