Java Program to Implement Gabow Algorithm

«
»
This is a Java Program to Implement Gabow Algorithm. Gabow algorithm is used for finding all strongly connected components in a graph.

Here is the source code of the Java Program to Implement Gabow Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  *     Java Program to Implement Gabow Algorithm
  3.  **/
  4.  
  5. import java.util.*;
  6.  
  7. /** class Gabow **/
  8. class Gabow
  9. {
  10.     /** number of vertices **/
  11.     private int V;    
  12.     /** preorder number counter **/
  13.     private int preCount;
  14.     private int[] preorder;
  15.     /** to check if v is visited **/
  16.     private boolean[] visited;  
  17.     /** check strong componenet containing v **/
  18.     private boolean[] chk;    
  19.     /** to store given graph **/
  20.     private List<Integer>[] graph;
  21.     /** to store all scc **/
  22.     private List<List<Integer>> sccComp;
  23.     private Stack<Integer> stack1;
  24.     private Stack<Integer> stack2;
  25.  
  26.     /** function to get all strongly connected components **/
  27.     public List<List<Integer>> getSCComponents(List<Integer>[] graph) 
  28.     {
  29.         V = graph.length;
  30.         this.graph = graph;
  31.         preorder = new int[V];
  32.         chk = new boolean[V]; 
  33.         visited = new boolean[V];
  34.         stack1 = new Stack<Integer>();
  35.         stack2 = new Stack<Integer>();
  36.         sccComp = new ArrayList<>();
  37.  
  38.         for (int v = 0; v < V; v++)
  39.               if (!visited[v])
  40.                 dfs(v);
  41.  
  42.         return sccComp;
  43.       }
  44.     /** function dfs **/
  45.     public void dfs(int v) 
  46.     {
  47.         preorder[v] = preCount++;
  48.         visited[v] = true;
  49.         stack1.push(v);
  50.         stack2.push(v);
  51.  
  52.         for (int w : graph[v]) 
  53.         {
  54.             if (!visited[w])
  55.                 dfs(w);
  56.             else if (!chk[w]) 
  57.                 while (preorder[stack2.peek()] > preorder[w])
  58.                     stack2.pop();            
  59.         }
  60.         if (stack2.peek() == v) 
  61.         {
  62.             stack2.pop();
  63.             List<Integer> component = new ArrayList<Integer>();
  64.             int w;
  65.             do 
  66.             {
  67.                 w = stack1.pop();
  68.                 component.add(w);
  69.                 chk[w] = true;
  70.             } while (w != v);  
  71.             sccComp.add(component);            
  72.         }                       
  73.     }    
  74.     /** main **/
  75.     public static void main(String[] args)
  76.     {
  77.         Scanner scan = new Scanner(System.in);
  78.         System.out.println("Gabow algorithm Test\n");
  79.         System.out.println("Enter number of Vertices");
  80.         /** number of vertices **/
  81.         int V = scan.nextInt();
  82.  
  83.         /** make graph **/
  84.         List<Integer>[] g = new List[V];        
  85.         for (int i = 0; i < V; i++)
  86.             g[i] = new ArrayList<Integer>();        
  87.         /** accpet all edges **/
  88.         System.out.println("\nEnter number of edges");
  89.         int E = scan.nextInt();
  90.         /** all edges **/
  91.         System.out.println("Enter "+ E +" x, y coordinates");
  92.         for (int i = 0; i < E; i++)
  93.         {
  94.             int x = scan.nextInt();
  95.             int y = scan.nextInt();
  96.             g[x].add(y);
  97.         }    
  98.  
  99.         Gabow gab = new Gabow();        
  100.         System.out.println("\nSCC : ");
  101.         /** print all strongly connected components **/
  102.         List<List<Integer>> scComponents = gab.getSCComponents(g);
  103.         System.out.println(scComponents);        
  104.     }    
  105. }

Gabow algorithm Test
 
Enter number of Vertices
8
 
Enter number of edges
14
Enter 14 x, y coordinates
0 1
1 2
2 3
3 2
3 7
7 3
2 6
7 6
5 6
6 5
1 5
4 5
4 0
1 4
 
SCC :
[[5, 6], [7, 3, 2], [4, 1, 0]]

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.