mercredi 28 juin 2017

Get all possible topological sort of a graph

As showed bellow I am getting depth topological sort using boost library. However for my optimization problem I have to consider all topological possibilities. How to do it?

//store topological order
deque<vertex_t> topologicalSorted;

//perform topological sort
if (topologicalSort(graph, topologicalSorted)) {
    cout << "The graph is directed acyclic!" << endl;
    cout << "Topological order: ";
    for (int i = 0; i < topologicalSorted.size(); i++) {
        cout << graph[topologicalSorted.at(i)].label << " ";
    }
    cout << endl;
}

//try to perform topo sort and return true if the graph is a dag
bool topologicalSort(const graph_t &graph, deque<vertex_t> &topologicalSorted) {
    try {
        boost::topological_sort(graph, front_inserter(topologicalSorted));
    } catch (boost::not_a_dag &) {
        cout << "not a dag" << endl;
        return false;
    }
    return true;
}

Aucun commentaire:

Enregistrer un commentaire