Strongly Connected Component Algorithm

Question

I have hard time to solve Strongly connected component algorithm. I have done these implementations blow so far but I got an unexpected result.

DFS and add nodes to stack (named var leader in my code) in order to keep depth of each vertices
Reverse graph edges' direction (getReverseGraph())
Second DFS and create Strongly connected component

I have an issue on step 3 and can not detect component properly.

Expected:

[ [ '1', '7', '5' ], ['2', '4'], [ 6, '3' ] ]

Result:

[ [ '1', '7', '5', '2', '4'], [ 6, '3' ] ].

Would anyone give me some advice? Thanks!

function Graph() {
  this.list = {};
}

Graph.prototype.insert = function(newVertex, neighborVertex) {
  if (!this.list[newVertex]) {

    if (neighborVertex) {
      this.list[newVertex] = [neighborVertex];
    } else {
      this.list[newVertex] = [];
    }

  } else {

    // If neighborVertex is not initialized
    if (!this.list[neighborVertex]) {
      this.list[neighborVertex] = [];
    }

    // Add neighborVertex to
    this.list[newVertex].push(neighborVertex);

  }
};

Graph.prototype.addEdge = function(vertexFrom, vertexTo) {
  if (this.list[vertexFrom] || this.list[vertexTo]) {
    throw new Error('Vertex does not exsists')
  }

  this.list[vertexFrom].push(vertexTo);
};

/*
 * DFS
 *
 * @param graph {object}: Takes different graph as optional
 * @param vertex {string|integer}
 * @param cb {function}
 */

Graph.prototype.dfs = function(graph, vertex, cb) {
  // track which node visited
  var visited = {};

  // Take graph as option
  var list = graph ? graph : this.list;

  // get initial nodes
  var currentNodes = list[vertex];

  // Invoke given function for inital node
  cb(vertex);

  // Mark vertex as visited
  visited[vertex] = true;

  // If there is no node to traverse return
  if (currentNodes.length === 0) {
    return;
  }

  var stack = [...currentNodes];

  for (var node of currentNodes) {
    visited[node] = true;
  }

  while (stack.length > 0) {

    // Get a node from stack
    var nextNode = stack.pop();

    // Invoke given function
    cb(nextNode);

    // Mark the vertex as visited
    visited[nextNode] = true;

    // Iterate adjacent nodes
    if (list[nextNode]) {

      // console.log('stack', stack)
      for (var neighbor of list[nextNode]) {

        // If the vertex is not visited, push each nodes to stack
        if (!visited[neighbor]) {
          stack.push(neighbor);
          visited[neighbor] = true;
        }
      }
    }
  }
}

function getReverseGraph(graph) {
  var vertices = Object.keys(graph);
  var reverseEdgeGraph = {};

  for (let vertex of vertices) {
    for (let neighbor of graph[vertex]) {
      if (reverseEdgeGraph[neighbor]) {
        reverseEdgeGraph[neighbor].push(vertex);
      } else {
        reverseEdgeGraph[neighbor] = [vertex];
      }
    }
  }

  return reverseEdgeGraph;
}

Graph.prototype.getStrongComponent = function(vertex) {

  if (vertex && !this.list[vertex]) {
    throw new("No vertex exsits")
  }

  vertex = vertex ? vertex.toString() : Object.keys(this.list)[0].toString();

  /*
  Create Copy of current Adjacency list
  */

  var reverseEdgeGraph = getReverseGraph(this.list);

  /*
  Create Leader
  */

  var leader = []; // stack to keep the depth

  var keys = Object.keys(this.list);

  while (keys.length > 0) {

    var indexOfVertex = keys.indexOf(vertex);
    keys.splice(indexOfVertex, 1);

    this.dfs(null, vertex, function(vertex) {

      // If leader does not have the vertex

      if (leader.indexOf(vertex) < 0) {
        // Get the key (vertex)
        var indexOfVertex = keys.indexOf(vertex);

        // Delete vertex
        keys.splice(indexOfVertex, 1);

        // Add vertex to leader
        leader.unshift(vertex);
      }

    });

    // Move to next key (remaining node)
    vertex = keys[0];
  }


  /**
   *
   * Create SCC
   *
   **/

  var allSCC = [];
  var visited = {};

  while (leader.length > 0) {
    var SCC = [];
    var target = leader.pop();

    if (visited[target]) {
      break;
    }

    this.dfs(reverseEdgeGraph, target, function(vertex) {
      // Create component
      if (!visited[vertex]) {
        visited[vertex] = true;
        SCC.push(vertex);
      }

    });

    if (SCC.length > 0) {
      allSCC.push(SCC);
    }
  }

  return allSCC
}


function test() {
  var graph = new Graph();
  var result = [
    [2, 4],
    [4, 2],
    [7, 5],
    [5, 1],
    [1, 7],
    [1, 5],
    [5, 7],
    [7, 1],
    [6, 3],
    [3, 6],
    [2, 7],
    [1, 6]
  ]
  result.forEach(function(line) {
    // console.log(line)
    graph.insert(line[0], line[1]);
  });

  var result = graph.getStrongComponent().map(function(components) {
    return components.length
  }).sort(function(a, b) {
    return b - a
  });
  console.log('result => ', graph.getStrongComponent(1));
}

function dfs() {
  var graph = new Graph();
  graph.insert('a', 'b');
  graph.insert('a', 'g');
  graph.insert('b', 'c');
  graph.insert('c', 'd');
  graph.insert('d', 'e');
  graph.insert('e', 'f');
  graph.insert('f', 'd');
  graph.insert('f', 'g');
  graph.insert('g', 'e');
  graph.insert('g', 'a');
  graph.insert('g', 'b');
  graph.insert('g', 'c');
  graph.insert('g', 'd');
  graph.insert('g', 'h');

  graph.dfs(null, 'a', function(v) {
    console.log(v);
  })
}

// dfs();
test(); // should be [ [ '1', '7', '5' ], ['2', '4'], [ 6, '3' ] ]

Can you tell us how did you implement step 3 ? I mean the general idea? Looking through your code is kind of hard to really understand. — Pham Trung

juvian juvian · Accepted Answer · 2018-06-13T15:12:28

You are running the dfs for each node, highly inefficient as you start each dfs with all nodes as unvisited. I added a fourth parameter to your dfs function to keep a single visited object for all the calls. That also avoids repeating nodes in your callback, giving the order you want. Also slightly modified it to be a bit shorter.

With this I refactored both the first dfs traversal and the second one on the reversed graph. Callback is much more cleaner an easier to understand this way, took me a long time to understand what were you doing in your first dfs callback.

Code works now:

function Graph() {
  this.list = {};
}

Graph.prototype.insert = function(newVertex, neighborVertex) {
  if (!this.list[newVertex]) {

    if (neighborVertex) {
      this.list[newVertex] = [neighborVertex];
    } else {
      this.list[newVertex] = [];
    }

  } else {

    // If neighborVertex is not initialized
    if (!this.list[neighborVertex]) {
      this.list[neighborVertex] = [];
    }

    // Add neighborVertex to
    this.list[newVertex].push(neighborVertex);

  }
};

Graph.prototype.addEdge = function(vertexFrom, vertexTo) {
  if (this.list[vertexFrom] || this.list[vertexTo]) {
    throw new Error('Vertex does not exsists')
  }

  this.list[vertexFrom].push(vertexTo);
};

/*
 * DFS
 *
 * @param graph {object}: Takes different graph as optional
 * @param vertex {string|integer}
 * @param cb {function}
 */

Graph.prototype.dfs = function(graph, vertex, cb, visited) {
  // track which node visited
  var visited = visited || {};

  // Take graph as option
  var list = graph ? graph : this.list;

  if (visited[vertex]) return;
  
  // Mark vertex as visited
  visited[vertex] = true;

  var stack = [vertex];

  while (stack.length > 0) {

    // Get a node from stack
    var nextNode = stack.pop();

    // Invoke given function
    cb(nextNode);

    // Iterate adjacent nodes
    if (list[nextNode]) {

      // console.log('stack', stack)
      for (var neighbor of list[nextNode]) {

        // If the vertex is not visited, push each nodes to stack
        if (!visited[neighbor]) {
          stack.push(neighbor);
          visited[neighbor] = true;
        }
      }
    }
  }
}

function getReverseGraph(graph) {
  var vertices = Object.keys(graph);
  var reverseEdgeGraph = {};

  for (let vertex of vertices) {
    for (let neighbor of graph[vertex]) {
      if (reverseEdgeGraph[neighbor]) {
        reverseEdgeGraph[neighbor].push(vertex);
      } else {
        reverseEdgeGraph[neighbor] = [vertex];
      }
    }
  }

  return reverseEdgeGraph;
}

Graph.prototype.getStrongComponent = function(vertex) {

  if (vertex && !this.list[vertex]) {
    throw new("No vertex exsits")
  }

  vertex = vertex ? vertex.toString() : Object.keys(this.list)[0].toString();

  /*
  Create Copy of current Adjacency list
  */

  var reverseEdgeGraph = getReverseGraph(this.list);
  var stack = [];
  var visited = {}
  
  for (var vertex in this.list) {
    this.dfs(null, vertex, function(v) {
      stack.push(v);
    }, visited)
  }
 
  /**
   *
   * Create SCC
   *
   **/
  var allSCC = [];
  visited = {};
  stack.reverse().forEach((vertex) => {
    var SCC = []
    this.dfs(reverseEdgeGraph, vertex, function(v) {
      SCC.push(v);
    }, visited)
    if (SCC.length) allSCC.push(SCC)  
  })
  
  return allSCC
}


function test() {
  var graph = new Graph();
  var result = [
    [2, 4],
    [4, 2],
    [7, 5],
    [5, 1],
    [1, 7],
    [1, 5],
    [5, 7],
    [7, 1],
    [6, 3],
    [3, 6],
    [2, 7],
    [1, 6]
  ]
  result.forEach(function(line) {
    // console.log(line)
    graph.insert(line[0], line[1]);
  });

  console.log('result => ', graph.getStrongComponent(1));
}

// dfs();
test(); // should be [ [ '1', '7', '5' ], ['2', '4'], [ 6, '3' ] ]

Strongly Connected Component Algorithm

1 Answers