# All possible topological orderings of a graph

TopologicalSort[] returns one of many unique orderings.

From wikipedia:

if a topological sort does not form a Hamiltonian path, the DAG will have two or more valid topological orderings, for in this case it is always possible to form a second valid ordering by swapping two consecutive vertices that are not connected by an edge to each other.

It should be simple, but how do you know how many possible orderings there are? Also, grouping and swapping feels kind of awkward, whats the preferred method?

-
I added the combinatorics tag because it seems appropriate. –  Mr.Wizard Sep 15 '13 at 21:50
Don't know if there exists a built in way, perhaps you can adapt this algorithm: comjnl.oxfordjournals.org/content/24/1/83.abstract (link to pdf to the right) –  ssch Sep 15 '13 at 22:08
Thanks, that worked nicely. github.com/dbasden/python-digraphtools/tree/master/digraphtools has a python implementation of it too: Topsort.py. –  Neal Alexander Sep 16 '13 at 2:50

## 1 Answer

(* Revision: 0.0.2 *)
TopologicalSortAll[g_] :=

Module[{topoSort, order, rules, edges, indices, len, incidenceMatrix, results},

(* Yaakov L.Varol and Doron Rotem,
* An Algorithm to Generate All Topological Sorting Arrangements.
* Computer J.,24 (1981) pp.83-84.
*)

topoSort[n_, pinput_, m_] := Module[{loc, p, i, k, k1, objk, objk1},
p   = pinput;
loc = Range[1, Length[pinput]];
i   = 1;

Sow[p];

While[i < n,
k     = loc[[i]];
k1    = k + 1;
objk  = p[[k]];
objk1 = p[[k1]];

If[ m[[i, objk1]] == 1,
p[[i ;; k]] = RotateRight[p[[i ;; k]]];
loc[[i]]    = i;
i          += 1,

(*else: swap*)
p[[k]]   = objk1;
p[[k1]]  = objk;
loc[[i]] = k1;
i        = 1;
Sow[p];
]
]
];

order   = TopologicalSort[g];
len     = Length[order];
indices = Range[len + 1];
rules   = Thread[Append[order, Undefined] ->  indices];
edges   = EdgeList[g] /. rules;

incidenceMatrix = SparseArray[edges /. (α_ \[DirectedEdge] β_ ) -> ({α , β} -> 1)];
incidenceMatrix = ArrayFlatten@{{incidenceMatrix, List /@ 1}};

results = Reap[topoSort[len, indices, incidenceMatrix]];
(#[[;; -2]] & /@ Flatten[results[[2]], 1]) /. (Reverse /@ rules)
]

-
This algorithm gives an error when run for g1 = Graph[{A [DirectedEdge] B, A [DirectedEdge] S, A [DirectedEdge] R, C [DirectedEdge] T, C [DirectedEdge] B, C [DirectedEdge] D, S [DirectedEdge] T}] –  dark blue Nov 2 '14 at 17:26