Boost logo

Boost Users :

From: Elisha Berns (e.berns_at_[hidden])
Date: 2005-07-07 18:25:08

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?



> 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
> > 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
> > But sometimes it isn't because there can be small cycles(?) inside
> > 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
> > 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
> to filter out any back edges.
> Doug
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]

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