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

From: Johan Oudinet (johan.oudinet_at_[hidden])
Date: 2006-04-24 03:15:09

On 4/23/06, John Krajewski <johnnyk1_at_[hidden]> 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?

You want doing a topological sort, don't you ?
Just use boost/graph/topological_sort.hpp :)

--
Johan