Java Program to Find the Transitive Closure of a Graph

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.

  1. import java.util.Scanner;
  2.  
  3. public class TransitiveClosure
  4. {
  5.     private int transitiveMatrix[][];
  6.     private int numberofvertices;
  7.     public static final int INFINITY = 999;
  8.  
  9.     public TransitiveClosure(int numberofvertices)
  10.     {
  11.         transitiveMatrix= new int[numberofvertices + 1][numberofvertices + 1];
  12.         this.numberofvertices = numberofvertices;
  13.     }
  14.  
  15.     public void transitiveClosure(int adjacencymatrix[][])
  16.     {
  17.         for (int source = 1; source <= numberofvertices; source++)
  18.         {
  19.             for (int destination = 1; destination <= numberofvertices; destination++)
  20.             {
  21.                 transitiveMatrix[source][destination] = adjacencymatrix[source][destination];
  22.             }
  23.         }
  24.  
  25.         for (int intermediate = 1; intermediate <= numberofvertices; intermediate++)
  26.         {
  27.             for (int source = 1; source <= numberofvertices; source++)
  28.             {
  29.                 for (int destination = 1; destination <= numberofvertices; destination++)
  30.                 {
  31.                     if (transitiveMatrix[source][intermediate] + transitiveMatrix[intermediate][destination]
  32.                                < transitiveMatrix[source][destination])
  33.                         transitiveMatrix[source][destination] = transitiveMatrix[source][intermediate] 
  34.                                 + transitiveMatrix[intermediate][destination];
  35.                 }
  36.             }
  37.         }
  38.  
  39.         for (int source = 1; source <= numberofvertices; source++)
  40.             System.out.print("\t" + source);
  41.  
  42.         System.out.println();
  43.         for (int source = 1; source <= numberofvertices; source++)
  44.         {
  45.             System.out.print(source + "\t");
  46.             for (int destination = 1; destination <= numberofvertices; destination++)
  47.             {
  48.                 System.out.print(transitiveMatrix[source][destination] + "\t");
  49.             }
  50.             System.out.println();
  51.         }
  52.     }
  53.  
  54.     public static void main(String... arg)
  55.     {
  56.         int adjacency_matrix[][];
  57.         int numberofvertices;
  58.  
  59.         Scanner scan = new Scanner(System.in);
  60.         System.out.println("Enter the number of vertices");
  61.         numberofvertices = scan.nextInt();
  62.         adjacency_matrix = new int[numberofvertices + 1][numberofvertices + 1];
  63.  
  64.         System.out.println("Enter the Weighted Matrix for the graph");
  65.         for (int source = 1; source <= numberofvertices; source++)
  66.         {
  67.             for (int destination = 1; destination <= numberofvertices; destination++)
  68.             {
  69.                 adjacency_matrix[source][destination] = scan.nextInt();
  70.                 if (source == destination)
  71.                 {
  72.                     adjacency_matrix[source][destination] = 0;
  73.                     continue;
  74.                 }
  75.                 if (adjacency_matrix[source][destination] == 0)
  76.                 {
  77.                     adjacency_matrix[source][destination] = INFINITY;
  78.                 }
  79.             }
  80.         }
  81.  
  82.         System.out.println("The Transitive Closure of the Graph"); 
  83.         TransitiveClosure transitiveClosure = new TransitiveClosure(numberofvertices);
  84.         transitiveClosure.transitiveClosure(adjacency_matrix);
  85.  
  86.         scan.close();
  87.     }
  88. }

$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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.