Deadlock Detection

EPI 19.4

Description:

Some processes has dependency. Write a program that takes as input a directed graph and checks if the graph contains a cycle.

Example:

Note

Idea:

还是类似topology sort，DFS的时候记录三个状态，unvisited, visiting, visited. DFS时候如果遇到visting的就是deadlock，返回true，如果遇到visited就是ok。

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){
    if(hashMap[key]==2) return false;
    if(hashMap[key]==1) return true;
    hashMap[key]=1;

    auto iter = graph.find(key);
    for(auto elem: iter->second){
        if(visit(elem, graph, hashMap)){
            return true;
        }
    }
    hashMap[key]=2;
    return false;
}

bool deadlock(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;
    }

    for(auto elem: graph){
        if(hashMap[elem.first]==0){
            if(visit(elem.first, graph, hashMap)){
                return true;
            }
        }
    }
    return false;
}


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>();
    graph[1].insert(0);
    graph[0].insert(3);

    cout<<deadlock(graph)<<endl;
}