C++ Program to Find the Transitive Closure of a Graph using Warshall’s Algorithm

«
»
This is a C++ Program find the transitive closure using Warshall’s algorithm. In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal (Lidl and Pilz 1998:337). If the binary relation itself is transitive, then the transitive closure is that same binary relation; otherwise, the transitive closure is a different relation. For example, if X is a set of airports and x R y means “there is a direct flight from airport x to airport y”, then the transitive closure of R on X is the relation R+: “it is possible to fly from x to y in one or more flights.”

Here is source code of the C++ Program to Construct Transitive Closure Using Warshall’s Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<iostream>
  2. #include<conio.h>
  3.  
  4. using namespace std;
  5. const int num_nodes = 10;
  6.  
  7. int main()
  8. {
  9.     int num_nodes, k, n;
  10.     char i, j, res, c;
  11.     int adj[10][10], path[10][10];
  12.  
  13.     cout << "\n\tMaximum number of nodes in the graph :";
  14.     cin >> n;
  15.     num_nodes = n;
  16.     cout << "\n\n\tNODES ARE LABELED AS A,B,C,......\n\n";
  17.     cout << "\nEnter 'y'for 'YES' and 'n' for 'NO' !!\n";
  18.  
  19.     for (i = 65; i < 65 + num_nodes; i++)
  20.         for (j = 65; j < 65 + num_nodes; j++)
  21.         {
  22.             cout << "\n\tIs there an EDGE from " << i << " to " << j << " ? ";
  23.             cin >> res;
  24.             if (res == 'y')
  25.                 adj[i - 65][j - 65] = 1;
  26.             else
  27.                 adj[i - 65][j - 65] = 0;
  28.         }
  29.     cout << "\nAdjacency Matrix:\n";
  30.  
  31.     cout << "\n\t\t\t   ";
  32.     for (i = 0; i < num_nodes; i++)
  33.     {
  34.         c = 65 + i;
  35.         cout << c << " ";
  36.     }
  37.     cout << "\n\n";
  38.     for (int i = 0; i < num_nodes; i++)
  39.     {
  40.         c = 65 + i;
  41.         cout << "\t\t\t" << c << "  ";
  42.         for (int j = 0; j < num_nodes; j++)
  43.             cout << adj[i][j] << " ";
  44.         cout << "\n";
  45.     }
  46.     for (int i = 0; i < num_nodes; i++)
  47.         for (int j = 0; j < num_nodes; j++)
  48.             path[i][j] = adj[i][j];
  49.  
  50.     for (int k = 0; k < num_nodes; k++)
  51.         for (int i = 0; i < num_nodes; i++)
  52.             if (path[i][k] == 1)
  53.                 for (int j = 0; j < num_nodes; j++)
  54.                     path[i][j] = path[i][j] || path[k][j];
  55.  
  56.     for (int i = 0; i < num_nodes; i++)
  57.         for (int j = 0; j < num_nodes; j++)
  58.             adj[i][j] = path[i][j];
  59.  
  60.     cout << "\nTransitive Closure of the Graph:\n";
  61.  
  62.     cout << "\n\t\t\t   ";
  63.     for (i = 0; i < num_nodes; i++)
  64.     {
  65.         c = 65 + i;
  66.         cout << c << " ";
  67.     }
  68.     cout << "\n\n";
  69.     for (int i = 0; i < num_nodes; i++)
  70.     {
  71.  
  72.         c = 65 + i;
  73.         cout << "\t\t\t" << c << "  ";
  74.         for (int j = 0; j < num_nodes; j++)
  75.             cout << adj[i][j] << " ";
  76.         cout << "\n";
  77.     }
  78.     return 0;
  79. }

Output:

advertisement
$ g++ Warshall.cpp
$ a.out
 
Maximum number of nodes in the graph :5
 
	NODES ARE LABELED AS A,B,C,......
 
Enter 'y'for 'YES' and 'n' for 'NO' !!
	Is there an EDGE from A to A ? y
	Is there an EDGE from A to B ? 
	Is there an EDGE from A to C ? 
	Is there an EDGE from A to D ? y
	Is there an EDGE from A to E ? 
	Is there an EDGE from B to A ? 
	Is there an EDGE from B to B ? n
	Is there an EDGE from B to C ? n
	Is there an EDGE from B to D ? n
	Is there an EDGE from B to E ? n
	Is there an EDGE from C to A ? n
	Is there an EDGE from C to B ? y
	Is there an EDGE from C to C ? y
	Is there an EDGE from C to D ? y
	Is there an EDGE from C to E ? n
	Is there an EDGE from D to A ? n
	Is there an EDGE from D to B ? y
	Is there an EDGE from D to C ? n
	Is there an EDGE from D to D ? y
	Is there an EDGE from D to E ? n
	Is there an EDGE from E to A ? n
	Is there an EDGE from E to B ? y
	Is there an EDGE from E to C ? y
	Is there an EDGE from E to D ? y
	Is there an EDGE from E to E ? y
 
Adjacency Matrix:
 
			   A B C D E 
 
			A  1 0 0 1 0 
			B  0 0 0 0 0 
			C  0 1 1 1 0 
			D  0 1 0 1 0 
			E  0 1 1 1 1 
 
Transitive Closure of the Graph:
 
			   A B C D E 
 
			A  1 1 0 1 0 
			B  0 0 0 0 0 
			C  0 1 1 1 0 
			D  0 1 0 1 0 
			E  0 1 1 1 1 
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

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