# Re: [Lemon-user] all possible topological sorts of a DAG

```Hi John,

```
LEMON does not provide a method for finding all topological orderings. However, it is relatively easy to implement it by combining any topological ordering method and backtracking.

```
```
I wrote a simple implementation that you can try, see the attached code. It builds a DAG, finds all topological orderings and prints them. The algorithm uses Kahn's well-known topological sorting method (https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm) combined with backtracking.
```
```
However, please keep in mind that a DAG may have a huge number of topological orderings. For example, the attached code builds a graph that has 2K+2 nodes and (2K)!/(K!*K!) distinct topological orderings. The attached version uses K=3, for which 20 orderings are found, but it is 184756 for K=10 and about 10^29 for K=50.
```
Anyway, why do you need this?

Best regards,
Péter

```
```Is there a method to get all possible topological sorts of a DAG?

--
John Lagerquist
Chief Engineer
RallyTronics LLC
801-866-5981

_______________________________________________
Lemon-user mailing list
Lemon-user@lemon.cs.elte.hu
http://lemon.cs.elte.hu/mailman/listinfo/lemon-user

```
```#include <iostream>
#include <lemon/list_graph.h>
#include <lemon/connectivity.h>

using namespace lemon;
using namespace std;

class TopologicalOrdering {
private:
const ListDigraph& _gr;
vector<ListDigraph::Node> _order;
ListDigraph::NodeMap<bool> _contains;
ListDigraph::NodeMap<int> _deg;

public:
TopologicalOrdering(const ListDigraph& gr) : _gr(gr), _contains(gr), _deg(gr) {
for (ListDigraph::NodeIt u(gr); u != INVALID; ++u) {
_deg[u] = countInArcs(gr, u);
}
}

bool contains(const ListDigraph::Node& u) const {
return _contains[u];
}

int inArcs(const ListDigraph::Node& u) const {
return _deg[u];
}

const ListDigraph::Node& operator[](int index) const {
return _order[index];
}

void push(const ListDigraph::Node& u) {
_contains[u] = true;
_order.push_back(u);
for (ListDigraph::OutArcIt a(_gr, u); a != INVALID; ++a) {
_deg[_gr.target(a)]--;
}
}

void pop() {
const ListDigraph::Node& u = _order.back();
_order.pop_back();
_contains[u] = false;
for (ListDigraph::OutArcIt a(_gr, u); a != INVALID; ++a) {
_deg[_gr.target(a)]++;
}
}

};

int main() {
// Build a test DAG
const int K = 3;
ListDigraph gr;
ListDigraph::NodeMap<char> label(gr);
label[s] = '>';
label[t] = '<';
ListDigraph::Node prevU = s, prevV = s;
for (int i = 0; i < K; i++) {
label[u] = (char)('a' + i);
label[v] = (char)('A' + i);
prevU = u;
prevV = v;
}
cout << "A DAG is built with " << countNodes(gr) << " nodes and " << countArcs(gr) << " arcs." << endl << endl;

vector<ListDigraph::Node> nodes;
for (ListDigraph::NodeIt u(gr); u != INVALID; ++u) {
nodes.push_back(u);
}

// Print all topological orderings using backtracking
cout << "Topological orderings:" << endl;
int k = 0, n = countNodes(gr), c = 0;
vector<int> x(n, -1);
TopologicalOrdering ordering(gr);
while (k >= 0) {
x[k]++;
if (x[k] == n) {
x[k] = -1;
k--;
ordering.pop();
} else {
ListDigraph::Node u = nodes[x[k]];
bool accept = !ordering.contains(u) && ordering.inArcs(u) == 0;
if (accept) {
ordering.push(u);
if (k == n - 1) {
c++;
for (int i = 0; i < n; i++) {
cout << label[ordering[i]] << ' ';
}
cout << endl;
ordering.pop();
} else {
k++;
}
}
}
}
cout << c << " distinct orderings found." << endl;
}
```
```_______________________________________________
Lemon-user mailing list
Lemon-user@lemon.cs.elte.hu
http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
```