9
$\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 are there? Also, grouping and swapping feels kind of awkward, what’s the preferred method?

$\endgroup$
3

2 Answers 2

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$
1
  • $\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, 2014 at 17:26
4
$\begingroup$

Hope this helps. Main idea: find vertices with 0 in-degree.

A version for large graphs is at the end.

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"]

Update: A (perhaps) 100x faster version which avoids graph manipulations:

allTopSorts2[g_ /; DirectedGraphQ[g] && AcyclicGraphQ[g]] :=
 With[{vlist = VertexList[g]},
  With[{vcount = Length[vlist]},
   vlist[[Flatten@
      With[{vrange = Range[vcount]},
       With[{elist = 
          EdgeList[g] /. Dispatch[AssociationThread[vlist, vrange]]},
        Nest[Apply[Splice[(nextv \[Function] {
                   {#1, nextv},
                   DeleteCases[#2, nextv, {1}, 1],
                   Select[#3, #[[1]] != nextv &]
                 }) /@ Complement[#2, Last /@ #3]] &, #, {1}] &,
         {{{}, vrange, elist}},
         vcount - 1]]]
     ]]~Partition~vcount]
  ]

Test:

{Mean@Table[ClearSystemCache[]; 
   First[AbsoluteTiming@allTopSorts2[g1]], 1000], allTopSorts2[g1]}

{0.0022313637, {{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}}}

Original answer:

allTopSorts[g_Graph] := With[{vl = VertexList[g]},
  
  On[Assert];
  Assert[DirectedGraphQ[g] && AcyclicGraphQ[g]];
  
  vl[[#]] & /@ Nest[
    Map[delv \[Function] Sequence @@
       (Join[delv, #] & /@
         Select[
          Position[
           VertexInDegree@EdgeDelete[g,
             Alternatives @@ (# \[DirectedEdge] _ &) /@
               vl\[LeftDoubleBracket]delv\[RightDoubleBracket]],
           0],
          ContainsNone@delv])],
    {{}},
    VertexCount@g]]

Test:

{Mean@Table[ClearSystemCache[]; First[AbsoluteTiming@allTopSorts[g1]],
    20], allTopSorts[g1]}

{0.351961935, {{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}}}

Addendum

allTopSorts2 gets frozen in face of large DAGs. So here's a more complete, practical version:

topSorts[g_, All, args___] := topSorts[g, \[Infinity], args];
topSorts[
   g_ /; DirectedGraphQ[g] && AcyclicGraphQ[g],
   Optional[n_ /; n \[Element] PositiveIntegers || n == \[Infinity], 1],
   Optional[shuffle_?BooleanQ, False]
   ] := Module[{stack = CreateDataStructure["Stack"],
    root = CreateDataStructure["FixedArray", 3], i = 0},
   With[{vlist = VertexList[g], vcount = VertexCount[g]},
    With[{vrange = Range[vcount]},
     With[{elist = EdgeList[g] /.
         Dispatch[vlist~AssociationThread~vrange]},
      root["SetPart", 1, {}];
      root["SetPart", 2, vrange];
      root["SetPart", 3, elist];
      stack["Push", root];
      vlist[[
        Flatten[Rest@Reap[NestWhile[
             s \[Function] With[{top = s["Pop"]},
               If[Length[top["Part", 2]] == 1,
                Sow[Normal[top]]; ++i;,
                Scan[Module[{tmp = top["Copy"]},
                    tmp["SetPart", 1, {tmp["Part", 1], #}];
                    tmp["SetPart", 2, 
                     DeleteCases[tmp["Part", 2], #, {1}, 1]];
                    tmp["SetPart", 3, 
                     Select[tmp["Part", 3], e \[Function] e[[1]] != #]];
                    s["Push", tmp];] &,
                  If[shuffle, RandomSample[#], #] &@
                   Complement[top["Part", 2], Last /@ top["Part", 3]]
                  ];
                ]; s],
             stack,
             i < n && ! #["EmptyQ"] &
             ];]]
        ]]~Partition~vcount]]]];

Usage

Some large DAG:

largeDAG = DirectedGraph[RandomGraph[{100, 200}], "Acyclic"]

Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 
 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 
 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 
 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 
 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 
 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 
 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 
 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 
 98, 99, 100}, {SparseArray[Automatic, {100, 
   100}, 0, {1, {{0, 3, 4, 9, 16, 18, 23, 27, 32, 
     35, 38, 41, 45, 49, 54, 59, 64, 67, 68, 70, 
     75, 78, 79, 81, 83, 89, 90, 92, 96, 99, 102, 
     104, 106, 106, 109, 110, 115, 119, 122, 126, 
     128, 130, 132, 135, 136, 138, 142, 144, 145, 
     146, 150, 153, 156, 158, 159, 161, 161, 164, 
     167, 168, 169, 171, 174, 175, 176, 178, 178, 
     181, 182, 183, 185, 185, 185, 186, 187, 188, 
     190, 190, 192, 193, 195, 195, 196, 196, 197, 
     197, 197, 197, 197, 198, 198, 198, 198, 199, 
     199, 200, 200, 200, 200, 200, 200}, {{14}, 
     {19}, {54}, {92}, {11}, {33}, {34}, {37}, 
     {48}, {17}, {21}, {31}, {52}, {82}, {84}, 
     {94}, {19}, {60}, {24}, {30}, {34}, {72}, 
     {100}, {11}, {38}, {52}, {59}, {9}, {83}, 
     {84}, {85}, {91}, {23}, {40}, {55}, {53}, 
     {76}, {84}, {15}, {17}, {23}, {24}, {49}, 
     {79}, {83}, {14}, {23}, {30}, {35}, {32}, 
     {34}, {53}, {69}, {100}, {46}, {47}, {77}, 
     {81}, {84}, {33}, {68}, {77}, {80}, {86}, 
     {48}, {50}, {89}, {28}, {41}, {59}, {26}, 
     {48}, {61}, {76}, {97}, {34}, {45}, {73}, 
     {71}, {38}, {51}, {30}, {40}, {38}, {44}, 
     {47}, {48}, {62}, {80}, {64}, {57}, {83}, 
     {33}, {41}, {71}, {82}, {32}, {59}, {93}, 
     {55}, {75}, {94}, {45}, {58}, {41}, {89}, 
     {42}, {49}, {85}, {42}, {45}, {65}, {75}, 
     {93}, {99}, {39}, {62}, {86}, {93}, {41}, 
     {79}, {100}, {43}, {49}, {55}, {82}, {49}, 
     {92}, {51}, {80}, {50}, {100}, {46}, {60}, 
     {92}, {79}, {50}, {76}, {58}, {71}, {91}, 
     {100}, {62}, {82}, {61}, {59}, {59}, {88}, 
     {96}, {98}, {62}, {73}, {88}, {70}, {72}, 
     {89}, {76}, {79}, {68}, {89}, {90}, {77}, 
     {90}, {98}, {62}, {65}, {79}, {73}, {75}, 
     {74}, {93}, {80}, {81}, {100}, {86}, {100}, 
     {84}, {98}, {74}, {75}, {89}, {85}, {92}, 
     {72}, {100}, {83}, {75}, {92}, {89}, {95}, 
     {88}, {92}, {100}, {88}, {94}, {86}, {99}, 
     {91}, {98}, {98}}}, Pattern}], Null}]

Get a topological sort:

topSorts[largeDAG] (* or *) 
topSorts[largeDAG, 1]

{{87, 78, 67, 66, 63, 56, 36, 29, 27, 57, 25, 44, 22, 20, 97, 26, 64, 
  18, 28, 16, 13, 35, 12, 10, 8, 9, 7, 6, 24, 40, 30, 5, 4, 52, 70, 
  72, 31, 21, 45, 3, 37, 39, 55, 90, 43, 60, 33, 11, 23, 38, 17, 48, 
  61, 93, 74, 75, 15, 77, 47, 82, 86, 46, 71, 58, 65, 84, 99, 2, 1, 
  54, 68, 19, 14, 69, 92, 53, 79, 76, 95, 34, 85, 49, 42, 50, 98, 96, 
  59, 32, 89, 91, 41, 51, 73, 83, 62, 100, 81, 80, 94, 88}}

This is the same as what you'll get with the built-in TopologicalSort (seems that we're using the same algorithm!):

TopologicalSort[largeDAG]

{87, 78, 67, 66, 63, 56, 36, 29, 27, 57, 25, 44, 22, 20, 97, 26, 64, \
18, 28, 16, 13, 35, 12, 10, 8, 9, 7, 6, 24, 40, 30, 5, 4, 52, 70, 72, \
31, 21, 45, 3, 37, 39, 55, 90, 43, 60, 33, 11, 23, 38, 17, 48, 61, \
93, 74, 75, 15, 77, 47, 82, 86, 46, 71, 58, 65, 84, 99, 2, 1, 54, 68, \
19, 14, 69, 92, 53, 79, 76, 95, 34, 85, 49, 42, 50, 98, 96, 59, 32, \
89, 91, 41, 51, 73, 83, 62, 100, 81, 80, 94, 88}

Get a random topological sort:

topSorts[largeDAG, 1, True]

{{2, 56, 4, 36, 67, 7, 3, 25, 20, 27, 10, 8, 11, 52, 63, 29, 18, 12, 
  70, 37, 66, 13, 1, 54, 78, 57, 17, 31, 14, 53, 6, 39, 26, 44, 72, 
  87, 97, 24, 48, 9, 69, 61, 30, 93, 23, 28, 16, 40, 43, 35, 64, 38, 
  68, 55, 33, 22, 74, 32, 5, 15, 21, 77, 45, 76, 89, 60, 46, 58, 95, 
  79, 90, 75, 91, 71, 65, 84, 92, 34, 47, 42, 50, 19, 82, 98, 49, 85, 
  86, 41, 96, 99, 59, 51, 73, 83, 62, 100, 81, 80, 94, 88}}

Get five:

topSorts[largeDAG, 5]

{{87, 78, 67, 66, 63, 56, 36, 29, 27, 57, 25, 44, 22, 20, 97, 26, 64, 
  18, 28, 16, 13, 35, 12, 10, 8, 9, 7, 6, 24, 40, 30, 5, 4, 52, 70, 
  72, 31, 21, 45, 3, 37, 39, 55, 90, 43, 60, 33, 11, 23, 38, 17, 48, 
  61, 93, 74, 75, 15, 77, 47, 82, 86, 46, 71, 58, 65, 84, 99, 2, 1, 
  54, 68, 19, 14, 69, 92, 53, 79, 76, 95, 34, 85, 49, 42, 50, 98, 96, 
  59, 32, 89, 91, 41, 51, 73, 83, 62, 100, 81, 80, 94, 88}, {87, 78, 
  67, 66, 63, 56, 36, 29, 27, 57, 25, 44, 22, 20, 97, 26, 64, 18, 28, 
  16, 13, 35, 12, 10, 8, 9, 7, 6, 24, 40, 30, 5, 4, 52, 70, 72, 31, 
  21, 45, 3, 37, 39, 55, 90, 43, 60, 33, 11, 23, 38, 17, 48, 61, 93, 
  74, 75, 15, 77, 47, 82, 86, 46, 71, 58, 65, 84, 99, 2, 1, 54, 68, 
  19, 14, 69, 92, 53, 79, 76, 95, 34, 85, 49, 42, 50, 98, 96, 59, 32, 
  89, 91, 41, 51, 73, 83, 62, 100, 81, 80, 88, 94}, {87, 78, 67, 66, 
  63, 56, 36, 29, 27, 57, 25, 44, 22, 20, 97, 26, 64, 18, 28, 16, 13, 
  35, 12, 10, 8, 9, 7, 6, 24, 40, 30, 5, 4, 52, 70, 72, 31, 21, 45, 3,
   37, 39, 55, 90, 43, 60, 33, 11, 23, 38, 17, 48, 61, 93, 74, 75, 15,
   77, 47, 82, 86, 46, 71, 58, 65, 84, 99, 2, 1, 54, 68, 19, 14, 69, 
  92, 53, 79, 76, 95, 34, 85, 49, 42, 50, 98, 96, 59, 32, 89, 91, 41, 
  51, 73, 83, 62, 100, 80, 94, 88, 81}, {87, 78, 67, 66, 63, 56, 36, 
  29, 27, 57, 25, 44, 22, 20, 97, 26, 64, 18, 28, 16, 13, 35, 12, 10, 
  8, 9, 7, 6, 24, 40, 30, 5, 4, 52, 70, 72, 31, 21, 45, 3, 37, 39, 55,
   90, 43, 60, 33, 11, 23, 38, 17, 48, 61, 93, 74, 75, 15, 77, 47, 82,
   86, 46, 71, 58, 65, 84, 99, 2, 1, 54, 68, 19, 14, 69, 92, 53, 79, 
  76, 95, 34, 85, 49, 42, 50, 98, 96, 59, 32, 89, 91, 41, 51, 73, 83, 
  62, 100, 80, 94, 81, 88}, {87, 78, 67, 66, 63, 56, 36, 29, 27, 57, 
  25, 44, 22, 20, 97, 26, 64, 18, 28, 16, 13, 35, 12, 10, 8, 9, 7, 6, 
  24, 40, 30, 5, 4, 52, 70, 72, 31, 21, 45, 3, 37, 39, 55, 90, 43, 60,
   33, 11, 23, 38, 17, 48, 61, 93, 74, 75, 15, 77, 47, 82, 86, 46, 71,
   58, 65, 84, 99, 2, 1, 54, 68, 19, 14, 69, 92, 53, 79, 76, 95, 34, 
  85, 49, 42, 50, 98, 96, 59, 32, 89, 91, 41, 51, 73, 83, 62, 100, 80,
   88, 94, 81}}

Get all:

topSorts[largeDAG, All]

(* Seriously? :^) *)

Well, it's still faster than allTopSorts, but slower than allTopSorts2:

{Mean@Table[ClearSystemCache[];
   First[AbsoluteTiming@topSorts[g1, All]], 200], topSorts[g1, All]}

{0.0134898905, {{C, D, A, R, S, T, B}, {C, D, A, R, S, B, T}, {C, D, 
   A, R, B, S, T}, {C, D, A, S, T, R, B}, {C, D, A, S, T, B, R}, {C, 
   D, A, S, R, T, B}, {C, D, A, S, R, B, T}, {C, D, A, S, B, T, 
   R}, {C, D, A, S, B, R, T}, {C, D, A, B, R, S, T}, {C, D, A, B, S, 
   T, R}, {C, D, A, B, S, R, T}, {C, A, D, R, S, T, B}, {C, A, D, R, 
   S, B, T}, {C, A, D, R, B, S, T}, {C, A, D, S, T, R, B}, {C, A, D, 
   S, T, B, R}, {C, A, D, S, R, T, B}, {C, A, D, S, R, B, T}, {C, A, 
   D, S, B, T, R}, {C, A, D, S, B, R, T}, {C, A, D, B, R, S, T}, {C, 
   A, D, B, S, T, R}, {C, A, D, B, S, R, T}, {C, A, R, D, S, T, 
   B}, {C, A, R, D, S, B, T}, {C, A, R, D, B, S, T}, {C, A, R, S, D, 
   T, B}, {C, A, R, S, D, B, T}, {C, A, R, S, T, D, B}, {C, A, R, S, 
   T, B, D}, {C, A, R, S, B, D, T}, {C, A, R, S, B, T, D}, {C, A, R, 
   B, D, S, T}, {C, A, R, B, S, D, T}, {C, A, R, B, S, T, D}, {C, A, 
   S, D, T, R, B}, {C, A, S, D, T, B, R}, {C, A, S, D, R, T, B}, {C, 
   A, S, D, R, B, T}, {C, A, S, D, B, T, R}, {C, A, S, D, B, R, 
   T}, {C, A, S, T, D, R, B}, {C, A, S, T, D, B, R}, {C, A, S, T, R, 
   D, B}, {C, A, S, T, R, B, D}, {C, A, S, T, B, D, R}, {C, A, S, T, 
   B, R, D}, {C, A, S, R, D, T, B}, {C, A, S, R, D, B, T}, {C, A, S, 
   R, T, D, B}, {C, A, S, R, T, B, D}, {C, A, S, R, B, D, T}, {C, A, 
   S, R, B, T, D}, {C, A, S, B, D, T, R}, {C, A, S, B, D, R, T}, {C, 
   A, S, B, T, D, R}, {C, A, S, B, T, R, D}, {C, A, S, B, R, D, 
   T}, {C, A, S, B, R, T, D}, {C, A, B, D, R, S, T}, {C, A, B, D, S, 
   T, R}, {C, A, B, D, S, R, T}, {C, A, B, R, D, S, T}, {C, A, B, R, 
   S, D, T}, {C, A, B, R, S, T, D}, {C, A, B, S, D, T, R}, {C, A, B, 
   S, D, R, T}, {C, A, B, S, T, D, R}, {C, A, B, S, T, R, D}, {C, A, 
   B, S, R, D, T}, {C, A, B, S, R, T, D}, {A, C, D, R, S, T, B}, {A, 
   C, D, R, S, B, T}, {A, C, D, R, B, S, T}, {A, C, D, S, T, R, 
   B}, {A, C, D, S, T, B, R}, {A, C, D, S, R, T, B}, {A, C, D, S, R, 
   B, T}, {A, C, D, S, B, T, R}, {A, C, D, S, B, R, T}, {A, C, D, B, 
   R, S, T}, {A, C, D, B, S, T, R}, {A, C, D, B, S, R, T}, {A, C, R, 
   D, S, T, B}, {A, C, R, D, S, B, T}, {A, C, R, D, B, S, T}, {A, C, 
   R, S, D, T, B}, {A, C, R, S, D, B, T}, {A, C, R, S, T, D, B}, {A, 
   C, R, S, T, B, D}, {A, C, R, S, B, D, T}, {A, C, R, S, B, T, 
   D}, {A, C, R, B, D, S, T}, {A, C, R, B, S, D, T}, {A, C, R, B, S, 
   T, D}, {A, C, S, D, T, R, B}, {A, C, S, D, T, B, R}, {A, C, S, D, 
   R, T, B}, {A, C, S, D, R, B, T}, {A, C, S, D, B, T, R}, {A, C, S, 
   D, B, R, T}, {A, C, S, T, D, R, B}, {A, C, S, T, D, B, R}, {A, C, 
   S, T, R, D, B}, {A, C, S, T, R, B, D}, {A, C, S, T, B, D, R}, {A, 
   C, S, T, B, R, D}, {A, C, S, R, D, T, B}, {A, C, S, R, D, B, 
   T}, {A, C, S, R, T, D, B}, {A, C, S, R, T, B, D}, {A, C, S, R, B, 
   D, T}, {A, C, S, R, B, T, D}, {A, C, S, B, D, T, R}, {A, C, S, B, 
   D, R, T}, {A, C, S, B, T, D, R}, {A, C, S, B, T, R, D}, {A, C, S, 
   B, R, D, T}, {A, C, S, B, R, T, D}, {A, C, B, D, R, S, T}, {A, C, 
   B, D, S, T, R}, {A, C, B, D, S, R, T}, {A, C, B, R, D, S, T}, {A, 
   C, B, R, S, D, T}, {A, C, B, R, S, T, D}, {A, C, B, S, D, T, 
   R}, {A, C, B, S, D, R, T}, {A, C, B, S, T, D, R}, {A, C, B, S, T, 
   R, D}, {A, C, B, S, R, D, T}, {A, C, B, S, R, T, D}, {A, R, C, D, 
   S, T, B}, {A, R, C, D, S, B, T}, {A, R, C, D, B, S, T}, {A, R, C, 
   S, D, T, B}, {A, R, C, S, D, B, T}, {A, R, C, S, T, D, B}, {A, R, 
   C, S, T, B, D}, {A, R, C, S, B, D, T}, {A, R, C, S, B, T, D}, {A, 
   R, C, B, D, S, T}, {A, R, C, B, S, D, T}, {A, R, C, B, S, T, 
   D}, {A, R, S, C, D, T, B}, {A, R, S, C, D, B, T}, {A, R, S, C, T, 
   D, B}, {A, R, S, C, T, B, D}, {A, R, S, C, B, D, T}, {A, R, S, C, 
   B, T, D}, {A, S, C, D, T, R, B}, {A, S, C, D, T, B, R}, {A, S, C, 
   D, R, T, B}, {A, S, C, D, R, B, T}, {A, S, C, D, B, T, R}, {A, S, 
   C, D, B, R, T}, {A, S, C, T, D, R, B}, {A, S, C, T, D, B, R}, {A, 
   S, C, T, R, D, B}, {A, S, C, T, R, B, D}, {A, S, C, T, B, D, 
   R}, {A, S, C, T, B, R, D}, {A, S, C, R, D, T, B}, {A, S, C, R, D, 
   B, T}, {A, S, C, R, T, D, B}, {A, S, C, R, T, B, D}, {A, S, C, R, 
   B, D, T}, {A, S, C, R, B, T, D}, {A, S, C, B, D, T, R}, {A, S, C, 
   B, D, R, T}, {A, S, C, B, T, D, R}, {A, S, C, B, T, R, D}, {A, S, 
   C, B, R, D, T}, {A, S, C, B, R, T, D}, {A, S, R, C, D, T, B}, {A, 
   S, R, C, D, B, T}, {A, S, R, C, T, D, B}, {A, S, R, C, T, B, 
   D}, {A, S, R, C, B, D, T}, {A, S, R, C, B, T, D}}}
$\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.