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);
ListDigraph::Node s = gr.addNode();
ListDigraph::Node t = gr.addNode();
label[s] = '>';
label[t] = '<';
ListDigraph::Node prevU = s, prevV = s;
for (int i = 0; i < K; i++) {
ListDigraph::Node u = gr.addNode();
ListDigraph::Node v = gr.addNode();
label[u] = (char)('a' + i);
label[v] = (char)('A' + i);
gr.addArc(prevU, u);
gr.addArc(prevV, v);
prevU = u;
prevV = v;
}
gr.addArc(prevU, t);
gr.addArc(prevV, t);
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
