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.

`#include<iostream>`

`#include<conio.h>`

using namespace std;

const int num_nodes = 10;

int main()

`{`

int num_nodes, k, n;

char i, j, res, c;

int adj[10][10], path[10][10];

cout << "\n\tMaximum number of nodes in the graph :";

cin >> n;

num_nodes = n;

cout << "\n\n\tNODES ARE LABELED AS A,B,C,......\n\n";

cout << "\nEnter 'y'for 'YES' and 'n' for 'NO' !!\n";

for (i = 65; i < 65 + num_nodes; i++)

for (j = 65; j < 65 + num_nodes; j++)

`{`

cout << "\n\tIs there an EDGE from " << i << " to " << j << " ? ";

cin >> res;

if (res == 'y')

adj[i - 65][j - 65] = 1;

`else`

adj[i - 65][j - 65] = 0;

`}`

cout << "\nAdjacency Matrix:\n";

cout << "\n\t\t\t ";

for (i = 0; i < num_nodes; i++)

`{`

c = 65 + i;

cout << c << " ";

`}`

cout << "\n\n";

for (int i = 0; i < num_nodes; i++)

`{`

c = 65 + i;

cout << "\t\t\t" << c << " ";

for (int j = 0; j < num_nodes; j++)

cout << adj[i][j] << " ";

cout << "\n";

`}`

for (int i = 0; i < num_nodes; i++)

for (int j = 0; j < num_nodes; j++)

path[i][j] = adj[i][j];

for (int k = 0; k < num_nodes; k++)

for (int i = 0; i < num_nodes; i++)

if (path[i][k] == 1)

for (int j = 0; j < num_nodes; j++)

path[i][j] = path[i][j] || path[k][j];

for (int i = 0; i < num_nodes; i++)

for (int j = 0; j < num_nodes; j++)

adj[i][j] = path[i][j];

cout << "\nTransitive Closure of the Graph:\n";

cout << "\n\t\t\t ";

for (i = 0; i < num_nodes; i++)

`{`

c = 65 + i;

cout << c << " ";

`}`

cout << "\n\n";

for (int i = 0; i < num_nodes; i++)

`{`

c = 65 + i;

cout << "\t\t\t" << c << " ";

for (int j = 0; j < num_nodes; j++)

cout << adj[i][j] << " ";

cout << "\n";

`}`

return 0;

`}`

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

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