repl.it
@samisthesam/

Cycle detection in a directed graph

ES6

No description

fork
loading
main.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
function Graph() {
  this.adjList = {}
}

Graph.prototype.addVertex = function(vertex) {
  this.adjList[vertex] = []
}

Graph.prototype.addEdge = function(vertex1,vertex2) {
  this.adjList[vertex1].push(vertex2)
}

Graph.prototype.dfs = function() {
  const nodes = Object.keys(this.adjList)
  const visited = {}
  for (let i = 0; i < nodes.length; i++) {
    const node = nodes[i]
    this._dfsUtil(node, visited)
  }
}
  
Graph.prototype._dfsUtil = function(vertex, visited) {
  if (!visited[vertex]){  
    visited[vertex] = true
    console.log(vertex, visited)
    const neighbors = this.adjList[vertex]
    for (let i = 0; i < neighbors.length; i++) {
      const neighbor = neighbors[i] 
        this._dfsUtil(neighbor, visited)
    }
  }
}

Graph.prototype.detectCycle = function() {
  const graphNodes = Object.keys(this.adjList);
  const visited = {};
  const recStack = {};
  
  for (let i = 0; i < graphNodes.length; i++) {
    const node = graphNodes[i]
    if (this._detectCycleUtil(node, visited , recStack)) 
      return 'there is a cycle'
  }
  return 'no cycle!'
}

Graph.prototype._detectCycleUtil = function(vertex, visited, recStack) {
  if(!visited[vertex]){
    visited[vertex] = true;
    recStack[vertex] = true;
    const nodeNeighbors = this.adjList[vertex];
    for(let i = 0; i < nodeNeighbors.length; i++){
      const currentNode = nodeNeighbors[i];
	  console.log('parent', vertex, 'Child', currentNode);
      if(!visited[currentNode] && this._detectCycleUtil(currentNode,visited, recStack)){
        return true;
      } else if (recStack[currentNode]){
        return true;
      }
    }
  }
  recStack[vertex] = false;
  return false;
}


const graph = new Graph()

graph.addVertex('A')
graph.addVertex('B')
graph.addVertex('C')
graph.addVertex('D')
graph.addVertex('E')

graph.addEdge('A', 'B')
graph.addEdge('D', 'E')
graph.addEdge('C', 'E')
graph.addEdge('A', 'D')
graph.addEdge('A', 'C')
graph.addEdge('E', 'B')
graph.addEdge('D', 'B')
graph.addEdge('E', 'A')
Babel Compiler v6.4.4 Copyright (c) 2014-2015 Sebastian McKenzie