Topology Sort

Description:

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

Example:

Note

Idea:

Method 1: (DFS)

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 


 function visit(node n)
    if n has a permanent mark then return
    if n has a temporary mark then stop (not a DAG)
    mark n temporarily
    for each node m with an edge from n to m do
        visit(m)
    mark n permanently
    add n to head of L

Code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

bool visit(int key, const unordered_map<int, unordered_set<int>>& graph, 
                    unordered_map<int, int>& hashMap, vector<int>& sortedElem){
    if(hashMap[key]==2) return true;
    if(hashMap[key]==1) return false;
    hashMap[key]=1;
    auto iter = graph.find(key);
    for(auto elem: iter->second){
        visit(elem, graph, hashMap, sortedElem);
    }
    hashMap[key]=2;
    sortedElem.push_back(key);
    return true;
}

vector<int> topoSort(const unordered_map<int, unordered_set<int>>& graph){
    unordered_map<int, int> hashMap;
    // Mark: 0 unvisited; 1 temporary; 2 permantly
    for(auto elem: graph){
        hashMap[elem.first]=0;
    }

    vector<int> sortedElem;
    for(auto elem: graph){
        if(hashMap[elem.first]==0){
            visit(elem.first, graph, hashMap, sortedElem);
        }
    }

    reverse(sortedElem.begin(), sortedElem.end());
    return sortedElem;
}

int main(){
    unordered_map<int, unordered_set<int>> graph;
    graph[5].insert(0);
    graph[5].insert(2);
    graph[4].insert(0);
    graph[4].insert(1);
    graph[2].insert(3);
    graph[3].insert(1);
    graph[0]=unordered_set<int>();
    graph[1]=unordered_set<int>();

    for(auto elem: topoSort(graph)){
        cout<<elem<<' ';
    }
}