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 Create a Random Graph Using Random Edge Generation
Assert an Exception is Thrown in JUnit 4 and 5
How to Get All Dates Between Two Dates?
Java Program to Implement Rope
Java Program to Implement Word Wrap Problem
Java Program to Implement EnumMap API
Beans and Dependency Injection
Wrapper Classes in Java
Inheritance with Jackson
Spring Boot - Zuul Proxy Server and Routing
Lớp Arrarys trong Java (Arrays Utility Class)
Java Program to Implement Find all Forward Edges in a Graph
How to Get a Name of a Method Being Executed?
Tiêu chuẩn coding trong Java (Coding Standards)
New Features in Java 11
Java Program to Search for an Element in a Binary Search Tree
Spring Security Remember Me
Validate email address exists or not by Java Code
Batch Processing with Spring Cloud Data Flow
JPA/Hibernate Persistence Context
Java Program to Search Number Using Divide and Conquer with the Aid of Fibonacci Numbers
Spring Boot Change Context Path
Guide to the Synchronized Keyword in Java
Copy a List to Another List in Java
Explain about URL and HTTPS protocol
Unsatisfied Dependency in Spring
A Guide to @RepeatedTest in Junit 5
Java Program to Implement Bresenham Line Algorithm
Introduction to Spring Cloud Netflix – Eureka
Spring Data JPA and Null Parameters
Java Program to implement Array Deque
An Intro to Spring Cloud Zookeeper