Re: [Boost-users] BGL:"topological_sort" on the output of "strong_components"

From: Vladimir Prus (ghost_at_[hidden])
Date: 2006-04-24 03:14:13

John Krajewski wrote:

> For my app (a physics simulator), I need to find the order to process sets
> of nodes in such a way that no node is processed before any node that it
> has a directed edge to, and all strongly connected nodes are processed in
> a set together (this is for determining the order to test stacked
> objects).
> 
> So basically, I want to detect all strongly connected components, then
> create a directed graph from that and perform a topological sort.  Then,
> when I process that sorted list of strongly connected components, I'll
> need to get the list of original nodes that are in each component.
> 
> My first inclination to solve this is to just create a second graph from
> the output of the strongly_connected_components algorithm, and then
> topological_sort that.  But perhaps there is some clever way to avoid that
> extra expense?

Hi John,
I don't think there's any other way. You can take a look at
transitive_closure.hpp that does presively that -- topoligical sort of
SCCs.

- Volodya