Implementation of Kosaraju's algo to find Strongly connected components

[sankar2011]

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

 
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
 
/**
 * 
 * @author Sankar
 * This talks about directed graph. This class runs Kosaraju's algorithm
 * to find out the connected components and at last gives us 5 mostly 
 * dense Strongly connected components in decreasing order
 * The word dense is defined by the number of nodes here.
 * Answer should appear like 3,3,3,0,0 or something like
 * that. These denotes the number of nodes in SCC
 */
public class Graph {
 
    private static final int SIZE = 9;//Number of nodes in the graph
    private final static String space = " ";    
    /**
     * All node vertexes
     */
    private static Vertex[] allVert = null;
    /**
     * After dfs is carried out in the reversed graph
     */
    private static Vertex[] after1Pass = null;
    /**
     * finishing times
     */
    private static int fTime = -1;
    private static int totCon = 0;
    /**
     * In the main method the array has been initialized with 5 vertexes
     */
    private static LinkedList<Vertex> leaders = new LinkedList<Vertex>();
 
    /**
     * This method creates graph from the file and closes the file.
     */
    public static void createGraph(){
 
 
        allVert = new Vertex[SIZE];//Array created but elements are null
 
 
        BufferedReader br = null;
        String sCurrentLine;
 
        try {
 
            br = new BufferedReader(new FileReader("C:\\folder\\Test.txt"));
                while ((sCurrentLine = br.readLine()) != null) {
 
 
                    int vertIdx = sCurrentLine.trim().indexOf(space);
                    String ver = sCurrentLine.trim().substring(0, vertIdx);
                    int vrtInt = Integer.parseInt(ver);
 
                    int edgeIdx = sCurrentLine.trim().lastIndexOf(space);
                    String edge = sCurrentLine.trim().substring(edgeIdx+1);
                    int edgeInt = Integer.parseInt(edge);
 
                    if(allVert[vrtInt-1]==null){
                        allVert[vrtInt-1] = new Vertex();
                        allVert[vrtInt-1].setNodeNo(vrtInt-1);
                    }
 
                    if(allVert[edgeInt-1]==null){
                        allVert[edgeInt-1] = new Vertex();
                        allVert[edgeInt-1].setNodeNo(edgeInt-1);
                    }
 
                    Vertex v = allVert[vrtInt-1];
                    Vertex u = allVert[edgeInt-1];
 
                    /**
                     * For the original graph
                     */
                    v.setOriginal(u);
                    /**
                     * For the reversed graph
                     */
                    u.setReverse(v);                    
 
 
                }                
 
 
 
        }catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }finally {
            try {
                if (br != null)br.close();
            } catch (IOException ex) {
                ex.printStackTrace();
            }
        } 
        /**
         * For testing of graph creation
         */
 
 
 
    }
 
 
 
    /**
     * 
     * @param v 
     * @param 
     * @return
     * This method runs the dfs algorithm through reversed graph
     */
    private static void dfsReverse(Vertex v){
        v.setExplored(1);
        ArrayList<Vertex> vArr = null;        
        vArr = v.getReverse();    
 
        /**
         * For all edges call dfs
         */        
        for(Vertex s:vArr){
            if(s.getExplored()==0){
                dfsReverse(s);                
            }
        }        
        fTime++;
 
        //Set the finish time of this node
        v.setFTime(fTime);
 
    }
    /**
     * DFS on the Original graph starting with maX finish time
     * @param v
     */
    private static void dfsOrig(Vertex v){
        v.setExplored(1);
        ArrayList<Vertex> vArr = null;
        /**
         * totCon counts the total number of nodes in this strongly connected component
         */
        totCon++;
        vArr = v.getOriginal();
 
        for(Vertex s:vArr){
            if(s.getExplored()==0){
                dfsOrig(s);                
            }
        }
    }
 
    /**
     *  DFS Loop
     *  This method runs dfs twice
     *  Once on the reversed graph and then on the original graph
     */
    private static void dfsLoop(){
        for(int i = SIZE-1;i>=0;i--){
            if(allVert[i]!=null){
                if(allVert[i].getExplored()==0){
                    //Run DFS on the reversed graph
                    dfsReverse(allVert[i]);
                }
            }
        }
 
        /**
         * This new array Stores Vertexes according to their finishing time
         */
        after1Pass = new Vertex[SIZE];
 
        for(int i = SIZE-1;i>=0;i--){
            if(allVert[i]!=null){
                Vertex v = allVert[i];
 
                int newInd = v.getFTime();
                after1Pass[newInd] = v;
                v.setExplored(0);
 
            }
        }
 
        /**
         * This array is no more required
         */
        allVert = null;
 
        for(int i = SIZE-1;i>=0;i--){
            if(after1Pass[i]!=null){
                Vertex v = after1Pass[i];                
                if(v.getExplored()==0){
 
                    totCon = 0;
                    leaders.add(v);
                    dfsOrig(v);
 
                    /**
                     * After dfs completes, set the number of strongly connected nodes
                     * to this node from where the dfs started
                     */
                    v.setLeaderOf(totCon);
 
                    for(int k=0;k<5;k++){
                        if(leaders.get(k).getLeaderOf()<=totCon){
                            leaders.add(k,v);
                            break;
                        }
                    }
                }
            }
        }
 
    }
    public static void main(String args[]){
        /**
         * add 5 vertexes
         */
        for(int k=0;k<5;k++){            
            leaders.add(new Vertex());
        }
        createGraph();
        dfsLoop();
        for(int k=0;k<5;k++){
 
            System.out.println(leaders.get(k).getLeaderOf());
        }
    }
 
 
}
 

Vertex.java

import java.util.ArrayList;
 
/**
 * 
 * @author Sankar
 * This class represents a node/vertex of the graph
 */
public class Vertex {
    /**
     * nodeNo indicates the vertex no
     */
    private int nodeNo = 0;
    private int fTime  = 0;
    private int explored = 0;
    private int leaderOf = 0;
 
 
    private ArrayList<Vertex> original = new ArrayList<Vertex>();
    private ArrayList<Vertex> reverse = new ArrayList<Vertex>();
    public void setNodeNo(int n){
        nodeNo = n;
    }
    public int getNodeNo(){
        return nodeNo;
    }
    public void setFTime(int n){
        fTime = n;
    }
 
    public int getFTime(){
        return fTime;
    }
    public int getExplored() {
        return explored;
    }
    public void setExplored(int explored) {
        this.explored = explored;
    }
    public int getLeaderOf() {
        return leaderOf;
    }
    public void setLeaderOf(int leaderOf) {
        this.leaderOf = leaderOf;
    }
    public ArrayList<Vertex> getOriginal() {
        return original;
    }
    public void setOriginal(Vertex v) {
        this.original.add(v);
    }
    public ArrayList<Vertex> getReverse() {
        return reverse;
    }
    public void setReverse(Vertex v) {
        this.reverse.add(v);
    }
 
 
}
 

test.txt

1 4
2 8
3 6
4 7
5 2
6 9
7 1
8 6
9 7
8 5
9 3

[Nepomuk]

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

[sankar2011]

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!