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?

| improve this question | | | | |
$\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)
  ]
| improve this answer | | | | |
$\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
2
$\begingroup$

Hope this helps.

AllTopSorts[g_Graph] := With[{vl = VertexList[g]},

  On[Assert];
  Assert[DirectedGraphQ[g] && AcyclicGraphQ[g]];

  vl\[LeftDoubleBracket]#\[RightDoubleBracket] & /@ Nest[
    Map[delv \[Function] Sequence @@
       (Join[delv, #] & /@
         Select[
          Position[
           VertexInDegree@EdgeDelete[g,
             Alternatives @@ (# \[DirectedEdge] _ &) /@
               vl\[LeftDoubleBracket]delv\[RightDoubleBracket]],
           0],
          ContainsNone@delv])],
    {{}},
    VertexCount@g]]

Test graph from @darkblue:

g1 = Graph[{A \[DirectedEdge] B, A \[DirectedEdge] S, 
   A \[DirectedEdge] R, C \[DirectedEdge] T, C \[DirectedEdge] B, 
   C \[DirectedEdge] D, S \[DirectedEdge] T}, VertexLabels -> "Name"]

AllTopSorts[g1] // AbsoluteTiming

Output:

{0.3237702, {{A, S, R, C, B, T, D}, {A, S, R, C, B, D, T}, {A, S, R, 
   C, T, B, D}, {A, S, R, C, T, D, B}, {A, S, R, C, D, B, T}, {A, S, 
   R, C, D, T, B}, {A, S, C, B, R, T, D}, {A, S, C, B, R, D, T}, {A, 
   S, C, B, T, R, D}, {A, S, C, B, T, D, R}, {A, S, C, B, D, R, 
   T}, {A, S, C, B, D, T, R}, {A, S, C, R, B, T, D}, {A, S, C, R, B, 
   D, T}, {A, S, C, R, T, B, D}, {A, S, C, R, T, D, B}, {A, S, C, R, 
   D, B, T}, {A, S, C, R, D, T, B}, {A, S, C, T, B, R, D}, {A, S, C, 
   T, B, D, R}, {A, S, C, T, R, B, D}, {A, S, C, T, R, D, B}, {A, S, 
   C, T, D, B, R}, {A, S, C, T, D, R, B}, {A, S, C, D, B, R, T}, {A, 
   S, C, D, B, T, R}, {A, S, C, D, R, B, T}, {A, S, C, D, R, T, 
   B}, {A, S, C, D, T, B, R}, {A, S, C, D, T, R, B}, {A, R, S, C, B, 
   T, D}, {A, R, S, C, B, D, T}, {A, R, S, C, T, B, D}, {A, R, S, C, 
   T, D, B}, {A, R, S, C, D, B, T}, {A, R, S, C, D, T, B}, {A, R, C, 
   B, S, T, D}, {A, R, C, B, S, D, T}, {A, R, C, B, D, S, T}, {A, R, 
   C, S, B, T, D}, {A, R, C, S, B, D, T}, {A, R, C, S, T, B, D}, {A, 
   R, C, S, T, D, B}, {A, R, C, S, D, B, T}, {A, R, C, S, D, T, 
   B}, {A, R, C, D, B, S, T}, {A, R, C, D, S, B, T}, {A, R, C, D, S, 
   T, B}, {A, C, B, S, R, T, D}, {A, C, B, S, R, D, T}, {A, C, B, S, 
   T, R, D}, {A, C, B, S, T, D, R}, {A, C, B, S, D, R, T}, {A, C, B, 
   S, D, T, R}, {A, C, B, R, S, T, D}, {A, C, B, R, S, D, T}, {A, C, 
   B, R, D, S, T}, {A, C, B, D, S, R, T}, {A, C, B, D, S, T, R}, {A, 
   C, B, D, R, S, T}, {A, C, S, B, R, T, D}, {A, C, S, B, R, D, 
   T}, {A, C, S, B, T, R, D}, {A, C, S, B, T, D, R}, {A, C, S, B, D, 
   R, T}, {A, C, S, B, D, T, R}, {A, C, S, R, B, T, D}, {A, C, S, R, 
   B, D, T}, {A, C, S, R, T, B, D}, {A, C, S, R, T, D, B}, {A, C, S, 
   R, D, B, T}, {A, C, S, R, D, T, B}, {A, C, S, T, B, R, D}, {A, C, 
   S, T, B, D, R}, {A, C, S, T, R, B, D}, {A, C, S, T, R, D, B}, {A, 
   C, S, T, D, B, R}, {A, C, S, T, D, R, B}, {A, C, S, D, B, R, 
   T}, {A, C, S, D, B, T, R}, {A, C, S, D, R, B, T}, {A, C, S, D, R, 
   T, B}, {A, C, S, D, T, B, R}, {A, C, S, D, T, R, B}, {A, C, R, B, 
   S, T, D}, {A, C, R, B, S, D, T}, {A, C, R, B, D, S, T}, {A, C, R, 
   S, B, T, D}, {A, C, R, S, B, D, T}, {A, C, R, S, T, B, D}, {A, C, 
   R, S, T, D, B}, {A, C, R, S, D, B, T}, {A, C, R, S, D, T, B}, {A, 
   C, R, D, B, S, T}, {A, C, R, D, S, B, T}, {A, C, R, D, S, T, 
   B}, {A, C, D, B, S, R, T}, {A, C, D, B, S, T, R}, {A, C, D, B, R, 
   S, T}, {A, C, D, S, B, R, T}, {A, C, D, S, B, T, R}, {A, C, D, S, 
   R, B, T}, {A, C, D, S, R, T, B}, {A, C, D, S, T, B, R}, {A, C, D, 
   S, T, R, B}, {A, C, D, R, B, S, T}, {A, C, D, R, S, B, T}, {A, C, 
   D, R, S, T, B}, {C, A, B, S, R, T, D}, {C, A, B, S, R, D, T}, {C, 
   A, B, S, T, R, D}, {C, A, B, S, T, D, R}, {C, A, B, S, D, R, 
   T}, {C, A, B, S, D, T, R}, {C, A, B, R, S, T, D}, {C, A, B, R, S, 
   D, T}, {C, A, B, R, D, S, T}, {C, A, B, D, S, R, T}, {C, A, B, D, 
   S, T, R}, {C, A, B, D, R, S, T}, {C, A, S, B, R, T, D}, {C, A, S, 
   B, R, D, T}, {C, A, S, B, T, R, D}, {C, A, S, B, T, D, R}, {C, A, 
   S, B, D, R, T}, {C, A, S, B, D, T, R}, {C, A, S, R, B, T, D}, {C, 
   A, S, R, B, D, T}, {C, A, S, R, T, B, D}, {C, A, S, R, T, D, 
   B}, {C, A, S, R, D, B, T}, {C, A, S, R, D, T, B}, {C, A, S, T, B, 
   R, D}, {C, A, S, T, B, D, R}, {C, A, S, T, R, B, D}, {C, A, S, T, 
   R, D, B}, {C, A, S, T, D, B, R}, {C, A, S, T, D, R, B}, {C, A, S, 
   D, B, R, T}, {C, A, S, D, B, T, R}, {C, A, S, D, R, B, T}, {C, A, 
   S, D, R, T, B}, {C, A, S, D, T, B, R}, {C, A, S, D, T, R, B}, {C, 
   A, R, B, S, T, D}, {C, A, R, B, S, D, T}, {C, A, R, B, D, S, 
   T}, {C, A, R, S, B, T, D}, {C, A, R, S, B, D, T}, {C, A, R, S, T, 
   B, D}, {C, A, R, S, T, D, B}, {C, A, R, S, D, B, T}, {C, A, R, S, 
   D, T, B}, {C, A, R, D, B, S, T}, {C, A, R, D, S, B, T}, {C, A, R, 
   D, S, T, B}, {C, A, D, B, S, R, T}, {C, A, D, B, S, T, R}, {C, A, 
   D, B, R, S, T}, {C, A, D, S, B, R, T}, {C, A, D, S, B, T, R}, {C, 
   A, D, S, R, B, T}, {C, A, D, S, R, T, B}, {C, A, D, S, T, B, 
   R}, {C, A, D, S, T, R, B}, {C, A, D, R, B, S, T}, {C, A, D, R, S, 
   B, T}, {C, A, D, R, S, T, B}, {C, D, A, B, S, R, T}, {C, D, A, B, 
   S, T, R}, {C, D, A, B, R, S, T}, {C, D, A, S, B, R, T}, {C, D, A, 
   S, B, T, R}, {C, D, A, S, R, B, T}, {C, D, A, S, R, T, B}, {C, D, 
   A, S, T, B, R}, {C, D, A, S, T, R, B}, {C, D, A, R, B, S, T}, {C, 
   D, A, R, S, B, T}, {C, D, A, R, S, T, B}}}
| improve this answer | | | | |
$\endgroup$

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.