[Boost-users] All orderings of boost::graph::topological_sort()

From: Matan Nassau (matan.nassau_at_[hidden])
Date: 2008-02-22 05:38:31

Hello,

In implementing a dependency graph subsystem, one of the tasks is
figuring out all the possible ways of traversing the graph with
respect to the dependencies.  boost::graph::topological_sort() looks
like a reasonable place to start;  however, topological_sort() only
gives /one/ linear ordering, not all possible orderings.

I digged into the code and found that the algorithm is in fact a call
to depth_first_search with a custom visitor.  The 0-in-degree vertices
are not mentioned in the algorithm, and I suspect manipulating the
order of these vertices would be a good start in generating different
orderings.  I also digged into the depth_first_search() code, but
there too it doesn't seem to be straightforward to change the order in
which those start-nodes are visited.  I am also aware that even if I
would find a way to change the order in which the 0-in-degree vertices
are visited it will still not give me all the various orderings;  I
think that repeating the procedure with a bredth_first_search() will
give me yet more different orderings, and with I'll have all the
different orderings.

I may have missed something obvious but I really don't know how to
tackle the problem of generating various orderings.  Any advice,
please?

Thank you!

-- 
Matan