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
What test is there to determine whether an edge is a back-edge that can be used inside a filter predicate of the filter_graph? Thanks, Elisha 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
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users