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

From: Stephen Nuchia (snuchia_at_[hidden])
Date: 2008-02-22 12:51:20

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

For any significant-sized input the number of orderings will be too
large to do anything useful with.  For an input small enough that the
set of feasible orderings will fit in memory I would simply generate all
permutations and screen for feasibility rather than attempting to create
an enumeration algorithm.  Create a comparability matrix and use it to
prune the permutation tree, perhaps?  N^2 bits doesn't sound
prohibitive.

This has probably been studied but I'm at work so I'll speculate.  For
larger inputs with many constraints it may be worthwhile to create an
enumeration algorithm.

For purposes of empirical testing of build-ordering systems it might be
sufficient to go into the algorithm and randomize the selection
processes whenever it makes arbitrary choices.  This may or may not be
easily achieved by randomly pre-sorting the input, depending on the
internals of the algorithm.  If the sort is stable that will work.

An efficient feasible ordering enumerator for arbitrary finite partial
ordered sets would have to have a recursive structure because there can
be arbitrarily complex subgraphs with mutually incomparable nodes,
nested to arbitrary depth.

Another point regarding applications: if you are interested in testing
build orders (as I very much am, that's what I'm doing manually right
now) you can't just convert the partial order to a total order
arbitrarily because modern build systems exploit incomparables in the
partial order to parallelize build steps.  If you impose an arbitrary
order on the incomparables you serialize the build artificially, which
prevents testing for parallel-step interaction.

If there is enough interest to justify adding an efficient deterministic
enumerator for poset orders I'll write one.  Graph-theoretical
algorithms are a fun way to spend the weekend :-)