Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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: (link to pdf to the right) – ssch Sep 15 '13 at 22:08
Thanks, that worked nicely. has a python implementation of it too: – Neal Alexander Sep 16 '13 at 2:50
up vote 7 down vote accepted
(* 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;


    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;

  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)
share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.