Re: [Boost-users] BGL Question/Advice which algorithm to use

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?

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 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
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users