Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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
1  
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 1

up vote 6 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;

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

Your Answer

 
discard

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.