@samisthesam/

Cycle detection in a directed graph

ES6

No description

fork
loading

This Plugin Crashed!

Error: Error: must not create an existing file {"type":"CREATE_FILE","wid":"0.20638032934121364","path":"main.js","file":{"path":"main.js","content":{"asEncoding":{"base64":"CmZ1bmN0aW9uIEdyYXBoKCkgewogIHRoaXMuYWRqTGlzdCA9IHt9Cn0KCkdyYXBoLnByb3RvdHlwZS5hZGRWZXJ0ZXggPSBmdW5jdGlvbih2ZXJ0ZXgpIHsKICB0aGlzLmFkakxpc3RbdmVydGV4XSA9IFtdCn0KCkdyYXBoLnByb3RvdHlwZS5hZGRFZGdlID0gZnVuY3Rpb24odmVydGV4MSx2ZXJ0ZXgyKSB7CiAgdGhpcy5hZGpMaXN0W3ZlcnRleDFdLnB1c2godmVydGV4MikKfQoKR3JhcGgucHJvdG90eXBlLmRmcyA9IGZ1bmN0aW9uKCkgewogIGNvbnN0IG5vZGVzID0gT2JqZWN0LmtleXModGhpcy5hZGpMaXN0KQogIGNvbnN0IHZpc2l0ZWQgPSB7fQogIGZvciAobGV0IGkgPSAwOyBpIDwgbm9kZXMubGVuZ3RoOyBpKyspIHsKICAgIGNvbnN0IG5vZGUgPSBub2Rlc1tpXQogICAgdGhpcy5fZGZzVXRpbChub2RlLCB2aXNpdGVkKQogIH0KfQogIApHcmFwaC5wcm90b3R5cGUuX2Rmc1V0aWwgPSBmdW5jdGlvbih2ZXJ0ZXgsIHZpc2l0ZWQpIHsKICBpZiAoIXZpc2l0ZWRbdmVydGV4XSl7ICAKICAgIHZpc2l0ZWRbdmVydGV4XSA9IHRydWUKICAgIGNvbnNvbGUubG9nKHZlcnRleCwgdmlzaXRlZCkKICAgIGNvbnN0IG5laWdoYm9ycyA9IHRoaXMuYWRqTGlzdFt2ZXJ0ZXhdCiAgICBmb3IgKGxldCBpID0gMDsgaSA8IG5laWdoYm9ycy5sZW5ndGg7IGkrKykgewogICAgICBjb25zdCBuZWlnaGJvciA9IG5laWdoYm9yc1tpXSAKICAgICAgICB0aGlzLl9kZnNVdGlsKG5laWdoYm9yLCB2aXNpdGVkKQogICAgfQogIH0KfQoKR3JhcGgucHJvdG90eXBlLmRldGVjdEN5Y2xlID0gZnVuY3Rpb24oKSB7CiAgY29uc3QgZ3JhcGhOb2RlcyA9IE9iamVjdC5rZXlzKHRoaXMuYWRqTGlzdCk7CiAgY29uc3QgdmlzaXRlZCA9IHt9OwogIGNvbnN0IHJlY1N0YWNrID0ge307CiAgCiAgZm9yIChsZXQgaSA9IDA7IGkgPCBncmFwaE5vZGVzLmxlbmd0aDsgaSsrKSB7CiAgICBjb25zdCBub2RlID0gZ3JhcGhOb2Rlc1tpXQogICAgaWYgKHRoaXMuX2RldGVjdEN5Y2xlVXRpbChub2RlLCB2aXNpdGVkICwgcmVjU3RhY2spKSAKICAgICAgcmV0dXJuICd0aGVyZSBpcyBhIGN5Y2xlJwogIH0KICByZXR1cm4gJ25vIGN5Y2xlIScKfQoKR3JhcGgucHJvdG90eXBlLl9kZXRlY3RDeWNsZVV0aWwgPSBmdW5jdGlvbih2ZXJ0ZXgsIHZpc2l0ZWQsIHJlY1N0YWNrKSB7CiAgaWYoIXZpc2l0ZWRbdmVydGV4XSl7CiAgICB2aXNpdGVkW3ZlcnRleF0gPSB0cnVlOwogICAgcmVjU3RhY2tbdmVydGV4XSA9IHRydWU7CiAgICBjb25zdCBub2RlTmVpZ2hib3JzID0gdGhpcy5hZGpMaXN0W3ZlcnRleF07CiAgICBmb3IobGV0IGkgPSAwOyBpIDwgbm9kZU5laWdoYm9ycy5sZW5ndGg7IGkrKyl7CiAgICAgIGNvbnN0IGN1cnJlbnROb2RlID0gbm9kZU5laWdoYm9yc1tpXTsKCSAgY29uc29sZS5sb2coJ3BhcmVudCcsIHZlcnRleCwgJ0NoaWxkJywgY3VycmVudE5vZGUpOwogICAgICBpZighdmlzaXRlZFtjdXJyZW50Tm9kZV0gJiYgdGhpcy5fZGV0ZWN0Q3ljbGVVdGlsKGN1cnJlbnROb2RlLHZpc2l0ZWQsIHJlY1N0YWNrKSl7CiAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgIH0gZWxzZSBpZiAocmVjU3RhY2tbY3VycmVudE5vZGVdKXsKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgfQogICAgfQogIH0KICByZWNTdGFja1t2ZXJ0ZXhdID0gZmFsc2U7CiAgcmV0dXJuIGZhbHNlOwp9CgoKY29uc3QgZ3JhcGggPSBuZXcgR3JhcGgoKQoKZ3JhcGguYWRkVmVydGV4KCdBJykKZ3JhcGguYWRkVmVydGV4KCdCJykKZ3JhcGguYWRkVmVydGV4KCdDJykKZ3JhcGguYWRkVmVydGV4KCdEJykKZ3JhcGguYWRkVmVydGV4KCdFJykKCmdyYXBoLmFkZEVkZ2UoJ0EnLCAnQicpCmdyYXBoLmFkZEVkZ2UoJ0QnLCAnRScpCmdyYXBoLmFkZEVkZ2UoJ0MnLCAnRScpCmdyYXBoLmFkZEVkZ2UoJ0EnLCAnRCcpCmdyYXBoLmFkZEVkZ2UoJ0EnLCAnQycpCmdyYXBoLmFkZEVkZ2UoJ0UnLCAnQicpCmdyYXBoLmFkZEVkZ2UoJ0QnLCAnQicpCmdyYXBoLmFkZEVkZ2UoJ0UnLCAnQScpCg=="},"asBuffer":null},"loaded":true}}
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