473,320 Members | 1,722 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes and contribute your articles to a community of 473,320 developers and data experts.

Implementation of Kosaraju's algo to find Strongly connected components

Last time I gave the mathematical reasoning to prove Dijkstra's algorithm.

This time I am giving a possible implementation for Kosaraju's algorithm which finds the strongly connected components in a directed graph. Short form of "strongly connected components" is SCC

The intent of the program.
==========================
The program finds the number of nodes in the 5 mostly dense strongly connected components in a directed graph. By dense I meant maX number of vertex's in a SCC.
If less than five components, say atmost 3 are found. And suppose the number of nodes in those components is 3,2,1 then result would show as
3
2
1
0
0

Assumption
============
The text file which represents the graph does not contain any isolated node. If it contained the program could be easily modified to consider that.

Explanation
==========
1>The text file represents one directed edge per row.
2> The files in the attached zip need to be extracted in a folder called c:\test. The folder need be created if not there.
3> The Test.txt file must be copied into C:\folder. The folder need be created if not there.
4> command prompt should be opened (cmd)
5> Following commands should be given in exact same order.
>cd\
>cd test
>C:\<javahome>\bin\javac Graph.java
>C:\<javahome>\bin\java -Xss8m -XX:+UseSerialGC Graph

Note
====
1>The program has been compiled and run with java version 1.7.0_13

2>-Xss8m -XX:+UseSerialGC option has been used because if the test.txt represents nodes more than 10000, then without this option there may be stackoverflow error.

3> As the algorithm itself is a bit more complicated, recursive versions of dfs have been used. Reader may implement non-recursive versions

Here is the code:
Graph.java
Expand|Select|Wrap|Line Numbers
  1.  
  2. import java.io.BufferedReader;
  3. import java.io.FileNotFoundException;
  4. import java.io.FileReader;
  5. import java.io.IOException;
  6. import java.util.ArrayList;
  7. import java.util.LinkedList;
  8.  
  9. /**
  10.  * 
  11.  * @author Sankar
  12.  * This talks about directed graph. This class runs Kosaraju's algorithm
  13.  * to find out the connected components and at last gives us 5 mostly 
  14.  * dense Strongly connected components in decreasing order
  15.  * The word dense is defined by the number of nodes here.
  16.  * Answer should appear like 3,3,3,0,0 or something like
  17.  * that. These denotes the number of nodes in SCC
  18.  */
  19. public class Graph {
  20.  
  21.     private static final int SIZE = 9;//Number of nodes in the graph
  22.     private final static String space = " ";    
  23.     /**
  24.      * All node vertexes
  25.      */
  26.     private static Vertex[] allVert = null;
  27.     /**
  28.      * After dfs is carried out in the reversed graph
  29.      */
  30.     private static Vertex[] after1Pass = null;
  31.     /**
  32.      * finishing times
  33.      */
  34.     private static int fTime = -1;
  35.     private static int totCon = 0;
  36.     /**
  37.      * In the main method the array has been initialized with 5 vertexes
  38.      */
  39.     private static LinkedList<Vertex> leaders = new LinkedList<Vertex>();
  40.  
  41.     /**
  42.      * This method creates graph from the file and closes the file.
  43.      */
  44.     public static void createGraph(){
  45.  
  46.  
  47.         allVert = new Vertex[SIZE];//Array created but elements are null
  48.  
  49.  
  50.         BufferedReader br = null;
  51.         String sCurrentLine;
  52.  
  53.         try {
  54.  
  55.             br = new BufferedReader(new FileReader("C:\\folder\\Test.txt"));
  56.                 while ((sCurrentLine = br.readLine()) != null) {
  57.  
  58.  
  59.                     int vertIdx = sCurrentLine.trim().indexOf(space);
  60.                     String ver = sCurrentLine.trim().substring(0, vertIdx);
  61.                     int vrtInt = Integer.parseInt(ver);
  62.  
  63.                     int edgeIdx = sCurrentLine.trim().lastIndexOf(space);
  64.                     String edge = sCurrentLine.trim().substring(edgeIdx+1);
  65.                     int edgeInt = Integer.parseInt(edge);
  66.  
  67.                     if(allVert[vrtInt-1]==null){
  68.                         allVert[vrtInt-1] = new Vertex();
  69.                         allVert[vrtInt-1].setNodeNo(vrtInt-1);
  70.                     }
  71.  
  72.                     if(allVert[edgeInt-1]==null){
  73.                         allVert[edgeInt-1] = new Vertex();
  74.                         allVert[edgeInt-1].setNodeNo(edgeInt-1);
  75.                     }
  76.  
  77.                     Vertex v = allVert[vrtInt-1];
  78.                     Vertex u = allVert[edgeInt-1];
  79.  
  80.                     /**
  81.                      * For the original graph
  82.                      */
  83.                     v.setOriginal(u);
  84.                     /**
  85.                      * For the reversed graph
  86.                      */
  87.                     u.setReverse(v);                    
  88.  
  89.  
  90.                 }                
  91.  
  92.  
  93.  
  94.         }catch (FileNotFoundException e) {
  95.             // TODO Auto-generated catch block
  96.             e.printStackTrace();
  97.         }
  98.         catch (IOException e) {
  99.             // TODO Auto-generated catch block
  100.             e.printStackTrace();
  101.         }finally {
  102.             try {
  103.                 if (br != null)br.close();
  104.             } catch (IOException ex) {
  105.                 ex.printStackTrace();
  106.             }
  107.         } 
  108.         /**
  109.          * For testing of graph creation
  110.          */
  111.  
  112.  
  113.  
  114.     }
  115.  
  116.  
  117.  
  118.     /**
  119.      * 
  120.      * @param v 
  121.      * @param 
  122.      * @return
  123.      * This method runs the dfs algorithm through reversed graph
  124.      */
  125.     private static void dfsReverse(Vertex v){
  126.         v.setExplored(1);
  127.         ArrayList<Vertex> vArr = null;        
  128.         vArr = v.getReverse();    
  129.  
  130.         /**
  131.          * For all edges call dfs
  132.          */        
  133.         for(Vertex s:vArr){
  134.             if(s.getExplored()==0){
  135.                 dfsReverse(s);                
  136.             }
  137.         }        
  138.         fTime++;
  139.  
  140.         //Set the finish time of this node
  141.         v.setFTime(fTime);
  142.  
  143.     }
  144.     /**
  145.      * DFS on the Original graph starting with maX finish time
  146.      * @param v
  147.      */
  148.     private static void dfsOrig(Vertex v){
  149.         v.setExplored(1);
  150.         ArrayList<Vertex> vArr = null;
  151.         /**
  152.          * totCon counts the total number of nodes in this strongly connected component
  153.          */
  154.         totCon++;
  155.         vArr = v.getOriginal();
  156.  
  157.         for(Vertex s:vArr){
  158.             if(s.getExplored()==0){
  159.                 dfsOrig(s);                
  160.             }
  161.         }
  162.     }
  163.  
  164.     /**
  165.      *  DFS Loop
  166.      *  This method runs dfs twice
  167.      *  Once on the reversed graph and then on the original graph
  168.      */
  169.     private static void dfsLoop(){
  170.         for(int i = SIZE-1;i>=0;i--){
  171.             if(allVert[i]!=null){
  172.                 if(allVert[i].getExplored()==0){
  173.                     //Run DFS on the reversed graph
  174.                     dfsReverse(allVert[i]);
  175.                 }
  176.             }
  177.         }
  178.  
  179.         /**
  180.          * This new array Stores Vertexes according to their finishing time
  181.          */
  182.         after1Pass = new Vertex[SIZE];
  183.  
  184.         for(int i = SIZE-1;i>=0;i--){
  185.             if(allVert[i]!=null){
  186.                 Vertex v = allVert[i];
  187.  
  188.                 int newInd = v.getFTime();
  189.                 after1Pass[newInd] = v;
  190.                 v.setExplored(0);
  191.  
  192.             }
  193.         }
  194.  
  195.         /**
  196.          * This array is no more required
  197.          */
  198.         allVert = null;
  199.  
  200.         for(int i = SIZE-1;i>=0;i--){
  201.             if(after1Pass[i]!=null){
  202.                 Vertex v = after1Pass[i];                
  203.                 if(v.getExplored()==0){
  204.  
  205.                     totCon = 0;
  206.                     leaders.add(v);
  207.                     dfsOrig(v);
  208.  
  209.                     /**
  210.                      * After dfs completes, set the number of strongly connected nodes
  211.                      * to this node from where the dfs started
  212.                      */
  213.                     v.setLeaderOf(totCon);
  214.  
  215.                     for(int k=0;k<5;k++){
  216.                         if(leaders.get(k).getLeaderOf()<=totCon){
  217.                             leaders.add(k,v);
  218.                             break;
  219.                         }
  220.                     }
  221.                 }
  222.             }
  223.         }
  224.  
  225.     }
  226.     public static void main(String args[]){
  227.         /**
  228.          * add 5 vertexes
  229.          */
  230.         for(int k=0;k<5;k++){            
  231.             leaders.add(new Vertex());
  232.         }
  233.         createGraph();
  234.         dfsLoop();
  235.         for(int k=0;k<5;k++){
  236.  
  237.             System.out.println(leaders.get(k).getLeaderOf());
  238.         }
  239.     }
  240.  
  241.  
  242. }
  243.  

Vertex.java

Expand|Select|Wrap|Line Numbers
  1. import java.util.ArrayList;
  2.  
  3. /**
  4.  * 
  5.  * @author Sankar
  6.  * This class represents a node/vertex of the graph
  7.  */
  8. public class Vertex {
  9.     /**
  10.      * nodeNo indicates the vertex no
  11.      */
  12.     private int nodeNo = 0;
  13.     private int fTime  = 0;
  14.     private int explored = 0;
  15.     private int leaderOf = 0;
  16.  
  17.  
  18.     private ArrayList<Vertex> original = new ArrayList<Vertex>();
  19.     private ArrayList<Vertex> reverse = new ArrayList<Vertex>();
  20.     public void setNodeNo(int n){
  21.         nodeNo = n;
  22.     }
  23.     public int getNodeNo(){
  24.         return nodeNo;
  25.     }
  26.     public void setFTime(int n){
  27.         fTime = n;
  28.     }
  29.  
  30.     public int getFTime(){
  31.         return fTime;
  32.     }
  33.     public int getExplored() {
  34.         return explored;
  35.     }
  36.     public void setExplored(int explored) {
  37.         this.explored = explored;
  38.     }
  39.     public int getLeaderOf() {
  40.         return leaderOf;
  41.     }
  42.     public void setLeaderOf(int leaderOf) {
  43.         this.leaderOf = leaderOf;
  44.     }
  45.     public ArrayList<Vertex> getOriginal() {
  46.         return original;
  47.     }
  48.     public void setOriginal(Vertex v) {
  49.         this.original.add(v);
  50.     }
  51.     public ArrayList<Vertex> getReverse() {
  52.         return reverse;
  53.     }
  54.     public void setReverse(Vertex v) {
  55.         this.reverse.add(v);
  56.     }
  57.  
  58.  
  59. }
  60.  
test.txt

1 4
2 8
3 6
4 7
5 2
6 9
7 1
8 6
9 7
8 5
9 3
Attached Files
File Type: zip test.zip (2.5 KB, 230 views)
Sep 14 '13 #1
2 6693
Nepomuk
3,112 Expert 2GB
A useful article, but there are a few points I'd like to bring up:
  • If possible one should refrain from making assumptions about the system your code will be running on, especially for articles explaining the basics of algorithms which should work independently of the language used. So, expecting the graph to be in C:\folder\Test.txt is a bad idea. My suggestion would be to pass the path to the createGraph function from the main function and in the main function read it from, say, args[0]. If that's empty you can still use C:\folder\Test.txt as a default.
  • An algorithms article should, in my opinion, focus on explaining the algorithm in question. You have implemented the algorithm in Java and provided the code, yes, but there is a lot of overhead due to the Java language. For example, you catch exceptions, use static fields and use both LinkedLists and ArrayLists. While this may make sense in a Java context, it may confuse people not familiar with Java who just want to understand the algorithm. My suggestion would be to provide the Java code for download but explain the algorithm in the article with pseudocode.
  • Your code is very unevenly commented. It is therefore difficult to determine, which parts of the code are relevant to understanding the algorithm and which parts are just specific to your implementation. Maybe you could add more comments or alternatively just show the parts that are relevant? You could take this article of mine as an example.
In general however, keep up the good work! :-)
Sep 20 '13 #2
Thanks Nepomuk!

I should have named the article as implementation-----in Java!
This was my mistake. Agreed. Also agreed that Folder location could have been abstracted.

Last time actually I explained Dijkstra's algorithm. So this time I thought only to give the implementation of Kosaraju so that those who are struggling a bit to understand, can fully understand after seeing the code .

Cheers!
Sep 20 '13 #3

Sign in to post your reply or Sign up for a free account.

Similar topics

2
by: glenn | last post by:
Can anyone tell me a good resource to find user interface components for VS 2003? I specifically need nice look field and grid components, drop down lists, calendar components and so on. I'm...
9
by: mikharakiri_nospaum | last post by:
I have graph x y - - 1 2 2 3 3 1 4 5 and would like to query how many connected components it has (two in the example -- {1,2,3} and {4,5}). Is it doable with "recursive with"?
3
by: | last post by:
I have a collectiond derived from NameObjectCollectionBase. FxCop is complaining that I need to implement a strongly typed CopyTo(MyObjectType, int) How do I do this? I can't seem to find any...
5
by: Mike Labosh | last post by:
In VB 6, the Form_QueryUnload event had an UnloadMode parameter that let me find out *why* a form is unloading, and then conditionally cancel the event. In VB.NET, the Closing event passes a...
0
by: Jim | last post by:
Does anyone know where I can find a 'connected component' image processing function? I don't see it in numarray or scipy core... In matlab the function is called bwlabel(bw,4); and step 8 on...
110
by: Gregory Pietsch | last post by:
I'm writing a portable implementation of the C standard library for http://www.clc-wiki.net and I was wondering if someone could check the functions in math.h for sanity/portability/whatever. I'm...
21
by: Chen ShuSheng | last post by:
Hey, In head file 'stdio.h', I only find the prototype of these two function but no body. Could someone pls tell me where their bodies are ? -------------- Life is magical.
4
by: Bob Campbell | last post by:
I am trying to find C# .NET components that will allow me to scan an image file (.jpg, .bmp, etc.), extract information and file the form as a .doc, ..xls or even put the information into an SQL...
2
by: Gabriel | last post by:
Hello, I'm looking for documentation with "Best Practice" for ASP.NET application In which case use Connected or Disconnected mode Typed dataset or not ? I didn'd find anything pertinent...
2
by: Bruce | last post by:
Hi I am trying to come up with an algorithm to solve the following problem. There are x components and y machines (y x) one machine can only run one component. Each component has 2 requirements...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.