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.
/** * Java Program to Implement Gabow Algorithm **/ import java.util.*; /** class Gabow **/ class Gabow { /** number of vertices **/ private int V; /** preorder number counter **/ private int preCount; private int[] preorder; /** to check if v is visited **/ private boolean[] visited; /** check strong componenet containing v **/ private boolean[] chk; /** to store given graph **/ private List<Integer>[] graph; /** to store all scc **/ private List<List<Integer>> sccComp; private Stack<Integer> stack1; private Stack<Integer> stack2; /** function to get all strongly connected components **/ public List<List<Integer>> getSCComponents(List<Integer>[] graph) { V = graph.length; this.graph = graph; preorder = new int[V]; chk = new boolean[V]; visited = new boolean[V]; stack1 = new Stack<Integer>(); stack2 = new Stack<Integer>(); sccComp = new ArrayList<>(); for (int v = 0; v < V; v++) if (!visited[v]) dfs(v); return sccComp; } /** function dfs **/ public void dfs(int v) { preorder[v] = preCount++; visited[v] = true; stack1.push(v); stack2.push(v); for (int w : graph[v]) { if (!visited[w]) dfs(w); else if (!chk[w]) while (preorder[stack2.peek()] > preorder[w]) stack2.pop(); } if (stack2.peek() == v) { stack2.pop(); List<Integer> component = new ArrayList<Integer>(); int w; do { w = stack1.pop(); component.add(w); chk[w] = true; } while (w != v); sccComp.add(component); } } /** main **/ public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Gabow algorithm Test\n"); System.out.println("Enter number of Vertices"); /** number of vertices **/ int V = scan.nextInt(); /** make graph **/ List<Integer>[] g = new List[V]; for (int i = 0; i < V; i++) g[i] = new ArrayList<Integer>(); /** accpet all edges **/ System.out.println("\nEnter number of edges"); int E = scan.nextInt(); /** all edges **/ System.out.println("Enter "+ E +" x, y coordinates"); for (int i = 0; i < E; i++) { int x = scan.nextInt(); int y = scan.nextInt(); g[x].add(y); } Gabow gab = new Gabow(); System.out.println("\nSCC : "); /** print all strongly connected components **/ List<List<Integer>> scComponents = gab.getSCComponents(g); System.out.println(scComponents); } }
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]]
Related posts:
Check If a File or Directory Exists in Java
Remove HTML tags from a file to extract only the TEXT
Configure a RestTemplate with RestTemplateBuilder
Netflix Archaius with Various Database Configurations
Java Program to Generate All Subsets of a Given Set in the Lexico Graphic Order
Spring WebClient Filters
Java Program to Implement HashTable API
Java Program to Implement String Matching Using Vectors
Add Multiple Items to an Java ArrayList
Java Program to Perform Insertion in a 2 Dimension K-D Tree
New Features in Java 15
Java – Reader to InputStream
Java Program to Implement DelayQueue API
Custom Thread Pools In Java 8 Parallel Streams
Using JWT with Spring Security OAuth
Examine the internal DNS cache
Java Program to Perform Partition of an Integer in All Possible Ways
The Dining Philosophers Problem in Java
Introduction to Apache Commons Text
Java Program to Solve a Matching Problem for a Given Specific Case
Spring Data MongoDB Transactions
Java Program to Implement Find all Back Edges in a Graph
Java Program to Represent Graph Using Adjacency Matrix
Java Program to Implement the String Search Algorithm for Short Text Sizes
Vector trong Java
Giới thiệu Google Guice – Injection, Scope
Java Program to Implement Ternary Search Algorithm
Lập trình đa luồng với CompletableFuture trong Java 8
Converting between an Array and a List in Java
Getting Started with Forms in Spring MVC
Debugging Reactive Streams in Java
Spring Security – security none, filters none, access permitAll