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. Doug