BGL:"topological_sort" on the output of "strong_components"
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? This will be my first use of BGL/boost so dumbing-down is encouraged :) Thanks, -John gmail.com account: johnnyk1
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
On 4/23/06, John Krajewski
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
participants (3)
-
Johan Oudinet -
John Krajewski -
Vladimir Prus