
Boost Users : 
From: Elisha Berns (e.berns_at_[hidden])
Date: 20050707 18:25:08
What test is there to determine whether an edge is a backedge that can
be used inside a filter predicate of the filter_graph?
Thanks,
Elisha
> 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 nary tree, and
> > then
> > build the tree from that vertex recursively finding the outedges 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 selfreferential.
>
> One thing I've done in the past was to run the strong_components
> algorithm first to detect all of the stronglyconnected 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
>
> _______________________________________________
> Boostusers mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net