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

Reply via email to