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:
Java Program to Implement PriorityBlockingQueue API
Ignore Null Fields with Jackson
Marker Interface trong Java
Cơ chế Upcasting và Downcasting trong java
An Introduction to Java.util.Hashtable Class
Mapping Nested Values with Jackson
Hashtable trong java
Java Program to Implement Brent Cycle Algorithm
Add Multiple Items to an Java ArrayList
Java Program to Find Minimum Element in an Array using Linear Search
Java Program to Perform Naive String Matching
Mệnh đề Switch-case trong java
Send email with authentication
Spring NoSuchBeanDefinitionException
Circular Dependencies in Spring
How to Get a Name of a Method Being Executed?
Java Program to Implement Quick Hull Algorithm to Find Convex Hull
Hướng dẫn Java Design Pattern – Transfer Object
Spring – Injecting Collections
Spring REST API + OAuth2 + Angular (using the Spring Security OAuth legacy stack)
Java Program to Implement Stack using Two Queues
Một số ký tự đặc biệt trong Java
Java Program to Perform Inorder Recursive Traversal of a Given Binary Tree
Lập trình mạng với java
Spring Security Registration – Resend Verification Email
Jackson – JsonMappingException (No serializer found for class)
Guide to Java OutputStream
Tạo ứng dụng Java RESTful Client với thư viện OkHttp
Guide to java.util.concurrent.BlockingQueue
Spring RequestMapping
Working with Tree Model Nodes in Jackson
Java CyclicBarrier vs CountDownLatch