SCC aka Kosaraju's Algorithm

Problem Statement:
        Implement SCCs of a directed Graph , to show strongly connected components in the given Graph

Fig: Directed Graph

 

Fig: SCC of the given directed graph

Solution : 

SCCs: All the vertices in a group of cluster from where each node is reachable from every other node.

Formal Definition: vertex 'v' and 'w' are strongly connected if there exists a directed path from 'v' to 'w' and also directed path from 'w' to 'v'.

Properties of SCCs:
1. Equivalence Relation :
         If 'v' is strongly connected to 'w', then 'w' is strongly connected to 'v'.
2. Transitive Property: 
    If  'v' is strongly connected to 'w' and 'w' is strongly connected to 'y' , then 'v' is strongly connected to 'y'.

Now lets us give a try to find out the Strongly Connected components :
Try 1: If we start from 11 , the reachable nodes will be 11, 9 , 8 , 10
Try 2: If we start from vertex 7 , the reachable nodes will be 4, 5 , 6 , 7 , 8 , 9 , 10
Try 3: If we start from vertex 1 , the whole graph is reachable.

Thus reachability of graph is dependent on the starting vertex. Thus this approach is not correct.

The solution for this problem was invented by S.Rao Kosaraju who was an Indian.

About Kosaraju :
             Sambasiva Rao Kosaraju is a professor of Computer Science at Johns Hopkins University
He was born in India, and he did his bachelors in Engineering from Andhra University, and Masters from IIT Kharagpur, and is a PhD from University of Pennsylvania.

History of Invention of Kosaraju Algorithm (1978) :
          Kosharaju had to go to the class to teach DFS(Tarjan's Algorithm) and forgot his notes , during the lecture he was trying to figure what DFS algorithm does , during which he accidently discovered this algorithm.


Real Life based Application of SCCs: 
1. Probably Facebook   recommends Friends using SCC.
2. LinkedIn shows 1st or 2nd or 3rd Connection using the concept of SCC.

Kosaraju's Algorithm:
1. Given a directed graph G , and stack S of size equal to number of vertices.
2. While S does not contain all the vertices, perform step 3.
3. Start DFS at any random vertex, Each time a DFS finishes for a vertex 'v' , push it onto the stack,
   this will fill the stack with least finishing time at the bottom and with maximum finish time closer  to top of stack. In simple words we are putting reverse post order of the graph in the stack.

4. Obtain Transpose of the given directed Graph.
          Transpose of Graph: Graph with the direction of every edge reversed.
5. While Stack S is not empty, perform step 6.
6. Pop the top element of stack and perform DFS on the transposed graph, for every item poped  from the stack and the vertices visited from poped item are strongly connected.


Note: SCC for a direct graph and its Transpose Graph(the same graph with the direction of every edge reversed) has exactly the same SCC as the original graph, because of the Transitive Property.

 Time Complexity:  O (V+E)

           The above complexity is obtained from following steps:

S.No	Step	Complexity
1.	Reverse Graph(Transpose)	O(E)
2.	1st DFS on GReverse to fill Stack	O(V+E)
3.	Reset Visit Status of Vertices	O(V)
4.	2nd DFS on Original Graph using filled Stack	O(V+E)

Implementation: 

Full Source Code: Link

Now lets give the Step wise implementation:

1. Transposing the Graph:
     

 -  //=============Reversing of Graph Starts================== //
 /**
  * Transpose given Graph, ie. reverse all the edges
  * @param g
  */
 private void transpose(SCC g){

  Set<Map.Entry<Integer, Boolean>> set=vistedStatus.entrySet(); 
  Iterator<Map.Entry<Integer, Boolean>> iterator=set.iterator();
  
  while(iterator.hasNext())
  {
   Map.Entry<Integer,Boolean> node= iterator.next();
   int vertex=node.getKey();
   List<Integer> list=adjList.get(vertex);

   if(list!=null)
   {
    int size=list.size();
    for(int i=0;i <size; ++i)
    {
     int adjNode=list.get(i);
     g.addReverseEdge(vertex,adjNode);
    }
   }
  }
 }
 
 /**
  * Adding reverse edge compared to original graph, 
  * edge(dest-->src)
  */
 private void addReverseEdge(int src, int dest) {
  List<Integer> list=reverseAdjList.get(dest);
  
  if(list==null) 
   list=new ArrayList<Integer>();
  
  list.add(src);
  reverseAdjList.put(dest,list);
 }

 //=============Reversing of Graph Ends================== //
                       -

2. Filling the Stack using DFS : 

 -  /**
  * Fill the stack to form reverse post-order using DFS
  * @param vertex
  */
 private void fillOrderStackDFS(int vertex){

  vistedStatus.put(vertex, true);
  List<Integer> list=reverseAdjList.get(vertex);

  if(list!=null){
   int size=list.size();
   
   for(int i=0;i<size;i++){
    int adjNode= list.get(i);
    boolean isVisited = vistedStatus.get(adjNode);
    
    if(!isVisited)
     fillOrderStackDFS(adjNode);
   }
  }
  stack.push(vertex); //Push the vertex when all connecting links processed
 }                       -

3.  Reset the visit status of vertices

 -  /**
  * Reset Visit Status of all vertices
  */
 private void resetVisitStatus(){
  for (Map.Entry<Integer, Boolean> entry : vistedStatus.entrySet()) 
      entry.setValue(false);
 }                        -

4. Empty Stack and Call DFS on each item for Original Graph

 -//2nd DFS on Original Graph
  while(!stack.isEmpty()){
  
   int poped=stack.pop();
   if(!vistedStatus.get(poped))
   {
    System.out.println("===========================");
    dfsUtil(poped);
    System.out.println();
   }
  }                          -

5. The subroutine which will call all the above steps

 - /*=========Computes SCC Starts===================*/
 /**
  * Computes SCC, performs Kosaraju's Steps
  */
 private void computeSCC(SCC g){
  
  //Step1: Reverse Graph
  //Transpose Graph
  transpose(g);
  
  Set<Map.Entry<Integer,Boolean>> set= vistedStatus.entrySet();
  Iterator<Map.Entry<Integer, Boolean>> it= set.iterator();
  
  //Step 2 : Fill Stack
   //1st DFS on Reversed Graph
  //Calcating Reverse Post order
  while(it.hasNext()){
   Map.Entry<Integer, Boolean> entry=it.next();
   int vertex= entry.getKey();
   boolean isVisited= entry.getValue();
   if(!isVisited){
    fillOrderStackDFS(vertex);
   }
  }
  
  //Reset Visit Status
  resetVisitStatus();
  
  
  System.out.println("SCCs of Digraph: ");
  
  //Step 3: Run DFS using the Stack
  //2nd DFS on Original Graph
  while(!stack.isEmpty()){
  
   int poped=stack.pop();
   if(!vistedStatus.get(poped))
   {
    System.out.println("===========================");
    dfsUtil(poped);
    System.out.println();
   }
  }
  System.out.println("===========================");
 }
 //=========Computes SCC Ends===================//     -

Thanks for giving your precious time to read this post, Please comment and post suggestion if any.
Happy Coding !! :)