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