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

From: Matan Nassau (matan.nassau_at_[hidden])
Date: 2008-02-22 20:18:09

Thank you very much for your prompt reply, Stephen.

On Fri, Feb 22, 2008 at 12:51, Stephen Nuchia wrote:
> For any significant-sized input the number of orderings will be too
> large to do anything useful with.

At the moment my input consists of about 32 vertices, although I'd
like not to count on it to remain this way.  I can probably assume the
number of nodes will remain in the order of magnitude of hundreds or
less.

I'm talking about a schedule generating program for an undergraduate
student.  It generates a schedule for a semester for a student, given
some constraints (time of day, courses done already and so on) and the
course dependency (this course must not be taken before that one and
so on).  I would very much like to support other complexities such as
some courses may be taken while a certain dependent is being taken,
while others must be taken before any of their dependents may be
taken.  But I leave such complexities as worries for future versions.
For the time being, all I want is to be able to generate all the
different schedules (i.e., all various topo sorts).  Indeed, something
like std::next_permutation() would make a lot of sense.  It would be
fast and flexible.  My next task would then be to find an algorithm to
quickly estimate the number of different orderings. :)

> 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.

I don't follow.  Can I change the ordering of vertices without ruining
the graph's integrity?  How?  Would this affect the toposort output?

> Create a comparability matrix and use it to
> prune the permutation tree, perhaps? N^2 bits doesn't sound
> prohibitive.

I don't follow...

> 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.

That is the reason for my query on my OP in the first place.  I don't
quite understand how manipulate the input vertices of the
depth_first_search().  For what I understand, depth_first_search()
works on a set of start vertices (which have no incoming edges), and
for each of these the algorith dives in to the depth of the vertex's
tree.  Permuting the order of these vertices would give me advance me
a lot, but I don't know how to do that.

> 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 :-)

I personally think the topological_sort() algorithm begs for an
algorithm that would allow iterating over all unique orderings.  As I
stated above, I think something of the sort of std::next_permutation()
would make a lot of sense, especially because graph algorithms, and
finding all different toposorts in particular, tend to be expensive
operations.  Simply asking for one ordering at a time gives a lot of
flexibility to the user with the added benefit of efficiency and
integration with the STL's way of doing things.

-- 
Matan