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
- 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
Expand|Select|Wrap|Line Numbers
- 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);
- }
- }
1 4
2 8
3 6
4 7
5 2
6 9
7 1
8 6
9 7
8 5
9 3