Problem Statement:
Implement SCCs of a directed Graph , to show strongly connected components in the given 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:
Implementation:
Full Source Code: Link
Now lets give the Step wise implementation:
1. Transposing the Graph:
2. Filling the Stack using DFS :
3. Reset the visit status of vertices
4. Empty Stack and Call DFS on each item for Original Graph
5. The subroutine which will call all the above steps
Thanks for giving your precious time to read this post, Please comment and post suggestion if any.
Happy Coding !! :)
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)
S.No

Step

Complexity

1.

Reverse Graph(Transpose)

O(E)

2.

1^{st} DFS on G^{Reverse}
to fill Stack

O(V+E)

3.

Reset Visit Status of Vertices

O(V)

4.

2^{nd} 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 postorder 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 !! :)
Smaller exhibits, including tables, kiosks plus some portable
ReplyDeleteand modular inline displays, are therapeutic for companies that desire a highquality exhibit with consistent brand presentation at budgetfriendly 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
There continues to be great surge in market research which has become the sole
ReplyDeleteguiding 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
Some birds, for instance will take part in singing displays that mirror the motions with the grass display
ReplyDeletelike 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
Some birds, by way of example will take part in singing displays that mirror the motions from
ReplyDeletethe 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
With just a little browsing, you'll find it's easy to
ReplyDeletelocate 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 website  custom trade show exhibit company
There has been great boost in market research and that has become the sole guiding factor for
ReplyDeleteall 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
These make it possible to hold 50% more importance than a standard
ReplyDeleteslatwall. 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
This post gives clear ide in support of the new users of blogging, that genuinely how to ddo blogging.
ReplyDeleteFeel free to visit my homepage; Las Vegas Washer Repairman
Hmm is anyone else hazving problemks with thhe pictuires onn thius blog
ReplyDeleteloading? I'm trying too figure out if its a problem on my end or iff it's the blog.
Any feedback would be greatly appreciated.
Review my website :: Las Vegas Refrigerator Service
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
ReplyDeleteguess its ok to use a few of your ideas!!
My webpage  Las Vegas Washer Service
Hi mates, its enormous article on the topic of educationand entirely explained, keep it up all the time.
ReplyDeleteFeel free to visit my website  private jets for sale uk
It's amazing in favor of me to have a website, which is beneficial in support of my knowledge.
ReplyDeletethanks admin
Here is my web blog: jet charter cost
I go to see each day some web sites and blogs to read posts, but this webpage provides feature based content.
ReplyDeletemy page ... cost of private jets
Way cool! Some extremely valid points! I appreciate you writing this writeup
ReplyDeleteplus the rest of the site is also really good.
Here is my web page: cost of private jets
Hey this is kind of of off topic but I was wanting to know if blogs use WYSIWYG editors or if you have
ReplyDeleteto 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