This Java program is to find the transitive closure of a graph.Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here reachable mean that there is a path from vertex i to j. The reach-ability matrix is called transitive closure of a graph.
Here is the source code of the Java program to find the transitive closure of graph. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
import java.util.Scanner; public class TransitiveClosure { private int transitiveMatrix[][]; private int numberofvertices; public static final int INFINITY = 999; public TransitiveClosure(int numberofvertices) { transitiveMatrix= new int[numberofvertices + 1][numberofvertices + 1]; this.numberofvertices = numberofvertices; } public void transitiveClosure(int adjacencymatrix[][]) { for (int source = 1; source <= numberofvertices; source++) { for (int destination = 1; destination <= numberofvertices; destination++) { transitiveMatrix[destination] = adjacencymatrix[destination]; } } for (int intermediate = 1; intermediate <= numberofvertices; intermediate++) { for (int source = 1; source <= numberofvertices; source++) { for (int destination = 1; destination <= numberofvertices; destination++) { if (transitiveMatrix[intermediate] + transitiveMatrix[intermediate][destination] < transitiveMatrix[destination]) transitiveMatrix[destination] = transitiveMatrix[intermediate] + transitiveMatrix[intermediate][destination]; } } } for (int source = 1; source <= numberofvertices; source++) System.out.print("\t" + source); System.out.println(); for (int source = 1; source <= numberofvertices; source++) { System.out.print(source + "\t"); for (int destination = 1; destination <= numberofvertices; destination++) { System.out.print(transitiveMatrix[destination] + "\t"); } System.out.println(); } } public static void main(String... arg) { int adjacency_matrix[][]; int numberofvertices; Scanner scan = new Scanner(System.in); System.out.println("Enter the number of vertices"); numberofvertices = scan.nextInt(); adjacency_matrix = new int[numberofvertices + 1][numberofvertices + 1]; System.out.println("Enter the Weighted Matrix for the graph"); for (int source = 1; source <= numberofvertices; source++) { for (int destination = 1; destination <= numberofvertices; destination++) { adjacency_matrix[destination] = scan.nextInt(); if (source == destination) { adjacency_matrix[destination] = 0; continue; } if (adjacency_matrix[destination] == 0) { adjacency_matrix[destination] = INFINITY; } } } System.out.println("The Transitive Closure of the Graph"); TransitiveClosure transitiveClosure = new TransitiveClosure(numberofvertices); transitiveClosure.transitiveClosure(adjacency_matrix); scan.close(); } }
$javac TransitiveClosure.java $java TransitiveClosure Enter the number of vertices 4 Enter the Weighted Matrix for the graph 0 0 3 0 2 0 0 0 0 7 0 1 6 0 0 0 The Transitive Closure of the Graph 1 2 3 4 1 0 10 3 4 2 2 0 5 6 3 7 7 0 1 4 6 16 9 0
Related posts:
Guide to WeakHashMap in Java
Quick Guide on Loading Initial Data with Spring Boot
Java Program to Implement the Program Used in grep/egrep/fgrep
Summing Numbers with Java Streams
Java Program to do a Breadth First Search/Traversal on a graph non-recursively
LIKE Queries in Spring JPA Repositories
Hướng dẫn Java Design Pattern – Strategy
Java Web Services – Jersey JAX-RS – REST và sử dụng REST API testing tools với Postman
A Guide to TreeSet in Java
Spring REST API + OAuth2 + Angular
Java Program to Implement Merge Sort on n Numbers Without tail-recursion
Java Program to Implement Shunting Yard Algorithm
MyBatis with Spring
More Jackson Annotations
Spring’s RequestBody and ResponseBody Annotations
The Order of Tests in JUnit
Java Program to Check Multiplicability of Two Matrices
The Thread.join() Method in Java
Java Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not
Jackson – JsonMappingException (No serializer found for class)
Spring RestTemplate Error Handling
Hướng dẫn Java Design Pattern – Transfer Object
New Features in Java 13
CharSequence vs. String in Java
Disable DNS caching
How to Add a Single Element to a Stream
Java Program to find the peak element of an array using Binary Search approach
Java Program to Implement Caesar Cypher
Java – InputStream to Reader
Java – Reader to InputStream
Java Program to Generate a Random Subset by Coin Flipping
How to Get the Last Element of a Stream in Java?