Let’s move on to directed graphs. In directed graphs edges have a direction from one vertex to another. Such graphs are also sometimes called as digraphs. A strongly connected graph is a graph in which there is a path from every vertex to every other vertex. A strongly connected component is a subgraph of the graph that satisfies the above property. A graph may not entirely be strongly connected but is composed of several strongly connected components. For eg. in the graph below there are 3 strongly connected components. If you look at strongly connected component ‘1’ containging A,B,C,F and G there exists a path from each one of those vertexes to any of the other vertices in the component.

An algorithmn known as Kosaraju–Sharir algorithm finds strongly connected components in a graph. The steps are described below:

1. Reverse the graph. If there is a edge pointing from A to B in the reversed graph the edge will point from B to A.
2. Traverse the reversed graph and list out the vertices in reverse post-order. Reverse post-order is not the same as pre-order but instead of adding the element to a list like in post order you add the element to a stack.
3. Now pop an element from the stack created in the first step. Do a depth first or breadth first search starting from that element. All the elements visited belong to the same strongly connected component. Remove all these elements from the stack and repeat Step 3 till there are no elements remaining on the stack.

Let’s see how we can implement this in Scala.Here is the link of the github repo where the code is stored.

Graph Reversal

We shall add a simple method to the Graph scala to return a reversed graph

//Reverses the graph
  def reverse():Graph ={
    val gReverse = new Graph()
    for(v <- vertices)
      gReverse.addVertex(v)
    for(e <- edges)
      gReverse.addEdge(new Edge(e.node2,e.node1)) //Reverse the edge
    gReverse
  }

Reverse Post Order

To do the reverse post order we shall use the post order algorithm described in the previous post and the code shall look like this

 

  def reversePostOrder(g: Graph) = fullPostOrderDFS(g, g.vertices.toList).reverse

  def fullPostOrderDFS(g: Graph, unmarkedList: List[Vertex]): List[Vertex] = unmarkedList match {
    case Nil => Nil
    case head :: tail =>
      val markedList = graphTraversal.postOrderDFS(g, unmarkedList.toSet,List(head))
      markedList ::: fullPostOrderDFS(g, unmarkedList diff markedList)
  }

In above code we call the fullPostOrderDFS method from the reversePostOrder method with the graph and the unmarked list of vertices. The first call to postOrderDFS would return a list of vertices traversed. We will append this list to the output of the next call and repeat till there are no vertices left in the unmarkedList. The reversePostOrder simply reverses the list returned by fullPostOrderDFS. For the graph shown in Figure 1 it returns:

A, B, G, C, F, E, D, J, I, H

Compute the Strongly Connected Components

The third and final step is to traverse the original graph in order given by the reverse post order returned by the previous step. All vertices returned by a single traversal belong to the same strongly connected component. Repeat till there are no more vertices remaining in the list.

def stronglyConnectedComponents(g:Graph,vertexOrder:List[Vertex]):List[List[Vertex]] = vertexOrder match {
  case Nil => List()
  case head::tail => val sccList = graphTraversal.preOrderDFS(g,vertexOrder.toSet,List(head))
    sccList::stronglyConnectedComponents(g,vertexOrder diff sccList)
}

In the above code we pass the Graph and the reversePostOrder of the reversed graph as parameters. The first traversal returns the first strongly connected component. We continue till all the strongly connected components are found.

The below line of code will print out the strongly connected components.

println(stronglyConnectedComponents(g,reversePostOrder(g.reverse)).map(_.mkString(",")).mkString("\n"))

In above single line of code we reverse the graph and pass it to the reversePostOrder method that returns the vertices in order they should be traversed to find the strongly connected components. We pass both the graph and the ordered list of vertices to the stronglyConnectedComponents method which returns us a list of list of vertices as specified by the method signature. Each item in the list is a strongly connected component. The map function converts each strongly connected component list into a comma seperated string. The mkString method following that seperate each string representation with new lines. The final output for the graph shown in Figure 1 looks like:

A,F,G,B,C
E,I,J,D
H