Boost logo

Boost Users :

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-07-06 22:19:50

Hi Elisha,

On Jul 6, 2005, at 6:12 PM, Elisha Berns wrote:
> 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.

One thing I've done in the past was to run the strong_components
algorithm first to detect all of the strongly-connected components
(SCCs). Then, I built another graph with one vertex for each SCC and,
finally, run the topological sort on this new graph.

However, I think my problem was a little different from yours, because
I expected there to be many fewer SCCs than vertices. Since you
mentioned that you have only a few, small cycles, there are other
options. The first option is to copy most of the topological_sort code
but ignore back edges. Another alternative is to use a filtered_graph<>
to filter out any back edges.


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at