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

An algorithm for generating all topological sorts for a given DAG (aka generating all linear extensions of a partial order) is given in the paper "Generating Linear Extensions Fast" by Pruesse and Ruskey. The algorithm has an amortized running time that is linear in the output (e.g.: if it outputs M topological sorts, it runs in time O(M)).

Note that in general you can't really have anything that has a runtime that's efficient with respect to the size of the input since the size of the output can be exponentially larger than the input. For example, a completely disconnected DAG of N nodes has N! possible topological sorts.

Answer 2

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.

Answer 3

So this approach is flawed! Unsure if it can be salvaged, I'll leave it a little while, if anyone can spot how to fix it, either grab what you can and post a new answer or edit mine.

Specifically, I used the below algorithm on the example from the comment and it will not output the example given, so it is clearly flawed.

---

The way I've learned to do a topological sort is the following:

• Create a list of all the elements with no arrows pointing into it
• Create a dictionary of element -> number, where element here is any element in the original collection that has an arrow into it, and the number is how many elements point to it.
• Create a dictionary of element -> list, where element here is any element in the original collection that has an arrow out of it, and the list is all the elements those arrows point to

In your example, the two dictionaries and the list would be like this:

D1      D2         List
W: 1    V: W, X    V
Y: 1    W: Y, Z
Z: 2    X: Z
X: 1

Then, start a loop where on each iteration you do the following:

• Output all elements of the list, these currently have no arrows pointing into them. Make a temporary copy of the list, and clear the list, preparing it for the following iteration
• Loop through the temporary copy, and find each element (if it exists) in the dictionary that is element -> list
• For each element in those lists, decrement the corresponding number in the element -> number dictionary by 1 (removing 1 arrow). Once a number for an element here reaches 0, add that element to the list (it has no arrows left)
• If the list is non-empty, redo the iteration loop

If you reach this point, and the dictionary with element -> number still has any elements left in it with a number above 0 (if you want to, you can remove the elements as you go in the above iteration once their numbers reach zero to make this part easier), then you have a cycle, since the above loop should not terminate until all arrows have been removed.

For your example, each iteration would output the following:

1. V
2. W, X (2nd iteration output both W and X)
3. Y, Z

If you want to know how I arrived at this solution, simply go through my iteration description step by step using the above dictionaries and list as the starting point.

---

Now, to specifically answer your question, how to output all combinations. The only places where "combinations" comes into play is per iteration. Basically, all the elements that you output in the first step of the iteration (the ones you made a temporary copy of) are considered "equivalent" and any internal ordering between these would have no impact on the topological sort.

So, do this:

• In the first point in the iteration, place those elements into a list, and add that to another list, giving you a list of lists
• This lists of lists will now contain each iteration as one element, and one element will be yet another list with the elements output in that iteration
• Now, combine all permutations of the first list with all the permutations of the second list with all the permutations of the third list, and so on

This means taking this output:

1. V
2. W, X
3. Y, Z

Which gives you 1 * 2 * 2 = 4 permutations in total and you would combine all permutations of the 1st iteration (which is 1) with all the permutations of the 2nd iteration (which is 2, W, X and X, W) with all the permutations of the 3rd iteration (which is 2, Y, Z and Z, Y).

The final list of permutations that are valid topological sorts would be this:

1. V, W, X, Y, Z
2. V, X, W, Y, Z
3. V, W, X, Z, Y
4. V, X, W, Z, Y

---

Here is the example from the comment:

A and B with no in-edges. Both A and B have an edge to C, but only A has an edge to D. Neither C nor D has any out-edges.

Which gives:

A --> C
A --> D
B --> C

Dictionaries and list:

D1     D2        List
C: 2   A: C, D   A
D: 1   B: C      B

Iterations would output:

1. A, B
2. D, C

All permutations (2 * 2 = 4):

1. A, B, D, C
2. A, B, C, D
3. B, A, D, C
4. B, A, C, D