6
$\begingroup$

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?

$\endgroup$
7
$\begingroup$
(* 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)
  ]
$\endgroup$
  • $\begingroup$ 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}] $\endgroup$ – dark blue Nov 2 '14 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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