5 Nov 2013

SCC aka Kosaraju's Algorithm

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

SCC
Fig: Directed Graph

 
SCC
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 !! :)

15 comments:

  1. Smaller exhibits, including tables, kiosks plus some portable
    and modular inline displays, are therapeutic for companies that desire a high-quality exhibit with consistent brand presentation at budget-friendly prices.
    Becoming an incredible designer requires that you think like one and have all of the tools that one would use.
    This is caused by a number of elements which feature strongly during these
    LED signs.

    My homepage :: fabric trade show display for sale

    ReplyDelete
  2. There continues to be great surge in market research which has become the sole
    guiding factor for every one of the ways of advertising. If your unit is just not modular, contact the
    business before you make any structural changes. Luckily, new
    lead retrieval technology can address all of these problems.


    My webpage - inexpensive trade show display tables

    ReplyDelete
  3. Some birds, for instance will take part in singing displays that mirror the motions with the grass display
    like the Cutthroat finch. There could be instances in which you can use spotlighting to spotlight your product.
    This includes, brochures, flyers, business cards, order forms,
    price sheets and press kits.

    my web site :: cheap trade show stand

    ReplyDelete
  4. Some birds, by way of example will take part in singing displays that mirror the motions from
    the grass display much like the Cutthroat finch. Step 2- Identify
    your target market: what their ages are group, gender,
    profession etc. Three popular raffle drum trends that you've probably affecting action are fabricated from either
    steel, clear acrylic, or another form of plastic referred to as PETG.


    my web page - Display System

    ReplyDelete
  5. With just a little browsing, you'll find it's easy to
    locate wire mesh displays that can work well with your specific POP location as well as hold the belongings you need
    to display. If your unit is just not modular, contact the organization before you make any structural
    changes. In short, it's crucial for organizations to
    be sure they deliver enough exciting details to pique the crowd's interest without
    crossing the line into the dreaded information overload
    territory.

    Here is my web-site - custom trade show exhibit company

    ReplyDelete
  6. There has been great boost in market research and that has become the sole guiding factor for
    all of the ways of advertising. Or you might simply have facts about
    a related field that your target audience would find interesting.
    Three popular raffle drum trends you have probably seen in action are fabricated from either steel, clear acrylic,
    or any other form of plastic called PETG.

    my web site - display trade show booth company

    ReplyDelete
  7. These make it possible to hold 50% more importance than a standard
    slatwall. Best custom display - The fabric may be molded to adjust to into any design or shape
    of any display, so that it is the ideal choice to make a customized display.
    Three popular raffle drum trends that you have probably affecting action are fabricated
    from either steel, clear acrylic, and other form of plastic generally known as PETG.


    Also visit my blog post; discount trade show backdrops

    ReplyDelete
  8. This post gives clear ide in support of the new users of blogging, that genuinely how to ddo blogging.



    Feel free to visit my homepage; Las Vegas Washer Repairman

    ReplyDelete
  9. Hmm is anyone else hazving problemks with thhe pictuires onn thius blog
    loading? I'm trying too figure out if its a problem on my end or iff it's the blog.
    Any feed-back would be greatly appreciated.

    Review my web-site :: Las Vegas Refrigerator Service

    ReplyDelete
  10. Hi, i think that i noticed you visited my weblog thus i came to go back the prefer?.I'm attempting to find issues to enhance my site!I
    guess its ok to use a few of your ideas!!

    My webpage - Las Vegas Washer Service

    ReplyDelete
  11. Hi mates, its enormous article on the topic of educationand entirely explained, keep it up all the time.


    Feel free to visit my website - private jets for sale uk

    ReplyDelete
  12. It's amazing in favor of me to have a website, which is beneficial in support of my knowledge.
    thanks admin

    Here is my web blog: jet charter cost

    ReplyDelete
  13. I go to see each day some web sites and blogs to read posts, but this webpage provides feature based content.


    my page ... cost of private jets

    ReplyDelete
  14. Way cool! Some extremely valid points! I appreciate you writing this write-up
    plus the rest of the site is also really good.

    Here is my web page: cost of private jets

    ReplyDelete
  15. Hey this is kind of of off topic but I was wanting to know if blogs use WYSIWYG editors or if you have
    to manually code with HTML. I'm starting a blog soon but have no coding skills so I wanted to get guidance from someone with experience.
    Any help would be greatly appreciated!

    my web blog boost website traffic

    ReplyDelete