CODEWITHSUNDEEP
c++algorithmsortingoutputtopological-sort
sink
sink

Reputation: 23

How to determine if a graph has a non-unique topological sort

I have created a program that organizes a graph by topological sort given an diagram. I identified 3 results:

The output of the first two points is correct, but for the third it's not. For example for the graph with 4 vertices and edges: 1->2; 3->1; 3->4; 4->2, the result I obtained is: 3 1 4 2... wrong! What is known is insufficient to conclude this. Any hints or help is appreciated, thanks in advance.

#include<bits/stdc++.h>
using namespace std;

class Graph{
    int V;
    list<int> *adj;
    public:
        Graph(int V);
        void addEdge(int u, int v);
        void topologicalSort();
};

Graph::Graph(int V){
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int u, int v){
    adj[u].push_back(v);
}

void Graph::topologicalSort(){
    vector<int> in_degree(V, 0);
    for (int u=0; u<V; u++){
        list<int>::iterator itr;
        for (itr = adj[u].begin(); itr != adj[u].end(); itr++)
             in_degree[*itr]++;}
    queue<int> q;
    for (int i = 0; i < V; i++)
        if (in_degree[i] == 0)
            q.push(i);
    int cnt = 0;
    vector <int> top_order;
    while (!q.empty()){
        int u = q.front();
        q.pop();
        top_order.push_back(u);
        list<int>::iterator itr;
        for (itr = adj[u].begin(); itr != adj[u].end(); itr++)
            if (--in_degree[*itr] == 0)
                q.push(*itr);
        cnt++;}
    if (cnt != V){
        cout << "Existing cycle\n";
        return;}
    for (int i=1; i<(int)top_order.size(); i++)
        cout << top_order[i] << " ";
    cout << endl;
}

int main(){
    setbuf(stdout, NULL);
    int N, L, u, v;
    scanf("%d %d", &N, &L);
    Graph g(N+1);
    for (int i=1; i<=L; i++){
        scanf("%d %d", &u, &v);
        g.addEdge(u, v);
    }
    g.topologicalSort();
    return 0;
}

Upvotes: 2

Views: 2959

Answers (2)

Theo H
Theo H

Reputation: 243

In the code given, if you find yourself doing two or more q.push() as a result of one q.pop(), then any resulting sort will not be unique. Checking for this is probably less trouble than checking the resulting DAG for a Hamiltonian path.

This is the same condition as discussed in the comments here: Determine whether a directed graph has a unique topological ordering?

Upvotes: 1

gilleain
gilleain

Reputation: 641

To check that a particular graph has a unique topological sorting, it is apparently enough to check for a Hamiltonian path in the DAG. Quoting wikipedia:

If a topological sort has the property that all pairs of consecutive vertices in the sorted order are connected by edges, then these edges form a directed Hamiltonian path in the DAG. If a Hamiltonian path exists, the topological sort order is unique; no other order respects the edges of the path. Conversely, if a topological sort does not form a Hamiltonian path, the DAG will have two or more valid topological orderings, for in this case it is always possible to form a second valid ordering by swapping two consecutive vertices that are not connected by an edge to each other. Therefore, it is possible to test in linear time whether a unique ordering exists.

So you just need to get the DAG for the first sorting you find and check that it forms a path that visits all the vertices.

Upvotes: 2

Related Questions