Topological Sorting of a directed acyclic graph

Question

How would you output all the possible topological sorts for a directed acyclic graph? For example, given a graph where V points to W and X, W points to Y and Z, and X points to Z:

V --> W --> Y
      W --> Z
V --> X --> Z

How do you topologically sort this graph to produce all possible results? I was able to use a breadth-first-search to get V, W, X, Y, Z and a depth-first search to get V, W, Y, Z, X. But wasn't able to output any other sorts.

Answer 1

It might be possible to count the number of orderings faster, but the only way to actually generate all orderings that I can think of is with a full brute-force recursion. (I say "brute force", but this is still much better than the brutest-possible brute force approach of testing every possible permutation :) )

Basically, at every step there is a set S of vertices remaining (i.e. which have not been added to the order yet), and a subset X of these can be safely added in the next step. This subset X is exactly the set of vertices that have no in-edges from vertices in S.

For a given partial solution L consisting of some number of vertices that are already in the order, the set S of remaining vertices, and the set X of vertices in S that have no in-edges from other vertices in S, the call Generate(L, X, S) will generate all valid topological orders beginning with L.

Generate(L, X, S):

• If X is empty:
  • Either L is already a complete solution, in which case it contains all n vertices and S is also empty, or the original graph contains a cycle.
  • If S is empty:
    • Output L as a solution.
  • Otherwise:
    • Report that a cycle exists. (In fact, all vertices in S participate in some cycle, though there may be more than one.)
• Otherwise:
  • For each x in X:
    • Let L' be L with x added to the end.
    • Let X' be X\{x} plus any vertices whose only in-edge among vertices in S came from x.
    • Let S' = S\{x}.
    • Generate(L', X', S')

To kick things off, find the set X of all vertices having no in-edges and call Generate((), X, V). Because every x chosen in the "For each" loop is different, every partial solution L' generated by the iterations of this loop must also be distinct, so no solution is generated more than once by any call to Generate(), including the top-level call.

In practice, forming X' can be done more efficiently than the above pseudocode suggests: When we choose x, we can delete all out-edges from x, but also add them to a temporary list of edges, and by tracking the total number of in-edges for each vertex (e.g. in an array indexed by vertex number) we can efficiently detect which vertices now have 0 in-edges and should thus be added to X'. Then at the end of the loop iteration, all the edges that we deleted can be restored from the temporary list.