All possible topological orderings of a graph
(* 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)
]
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}}}