title: Find Deadlock in Graph
body: <p>In a multithreaded environment, it's possible that different processes will need to use the same resource. A <em>wait-for</em> graph represents the different processes as nodes in a directed graph, where an edge from node <code>i</code> to node <code>j</code> means that the node <code>j</code> is using a resource that node <code>i</code> needs to use (and cannot use until node <code>j</code> releases it).</p>
  <p>We are interested in whether or not this digraph has any cycles in it. If it does, it is possible for the system to get into a state where no process can complete.</p>
  <p>We will represent the processes by integers <code>0</code>, ...., <code>n - 1</code>. We represent the edges using a two-dimensional list <code>connections</code>. If <code>j</code> is in the list <code>connections[i]</code>, then there is a directed edge from process <code>i</code> to process <code>j</code>.</p>
  <p>Write a function that returns <code>True</code> if <code>connections</code> describes a graph with a directed cycle, or <code>False</code> otherwise.</p>
  <p>Example</p>
  <ul>
  <li>For <code>connections = [[1], [2], [3, 4], [4], [0]]</code>, the output should be<code>findDeadlock(connections) = true</code>.</li>
  </ul>
  <p>This graph contains a cycle.</p>
  <ul>
  <li>For <code>connections = [[1, 2, 3], [2, 3], [3], []]</code>, the output should be<code>findDeadlock(connections) = false</code>.</li>
  </ul>
  <p>Here is a task.</p>
  <p>Here is my implementation:</p>
  <pre><code>class Node {
        constructor(data) {
          this.data = data;
          this.next = null;
        }
      }
      class LinkedList {
        constructor() {
          this.head = null;
        }
        insertAtHead(data) {
          let temp = new Node(data);
          temp.next = this.head;
          this.head = temp;
          return this;
        }
        getHead() {
          return this.head;
        }
      }
      class Graph {
        constructor(vertices) {
          this.vertices = vertices;
          this.list = [];
          for (let i = 0; i &lt; vertices; i++) {
            let temp = new LinkedList();
            this.list.push(temp);
          }
        }
        addEdge(source, destination) {
          if (source &lt; this.vertices &amp;&amp; destination &lt; this.vertices) {
            this.list[source].insertAtHead(destination);
          }
          return this;
        }
      }
      
      const Colors = {
        WHITE: &quot;white&quot;,
        GRAY: &quot;gray&quot;,
        BLACK: &quot;black&quot;,
      };
      
      Object.freeze(Colors);
      
      const  isDeadlocked = (g) =&gt; {
        let color = [];
        for (let i = 0; i &lt; g.vertices; i++) {
          color[i] = Colors.WHITE;
        }
        for (let i = 0; i &lt; g.vertices; i++) {
          if (color[i] == Colors.WHITE) {
            if (detectCycle(g, i, color)) {
                console.log(true)
              return true;
            }
          }
        }
         console.log(false);
        return false;
      }
      const detectCycle = (g, currentVertex, color) =&gt; {
        color[currentVertex] = Colors.GRAY;
        let neighbor;
        let nextNode = g.list[currentVertex].getHead();
        while (nextNode !== null) {
          neighbor = nextNode.data;
          if (color[neighbor] == Colors.GRAY) {
            return true;
          }
          if (color[neighbor] == Colors.WHITE &amp;&amp; detectCycle(g, neighbor, color)) {
            return true;
          }
        }
        color[currentVertex] = Colors.BLACK;
        return false;
      }
      
      const findDeadlock = (input) =&gt; {
          const g = new Graph(input.length);
          for (let i = 0; i &lt; input.length; i++) {
              for (let j = 0; j &lt; input[i].length; j++) {
                 g.addEdge(i, input[i][j]);
              }
          }
          isDeadlocked(g);
      }
      const connections = [[1, 2, 3], [2, 3], [3], []];
      findDeadlock(connections);
  </code></pre>
  <p>My code fails the second test. Cannot find the reason why. Any help?</p>