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.

```
#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:

$ 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.

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

« Prev - C++ Program to Check if a Graph is Strongly Connected or Not

» Next - C++ Program to Apply the Prim’s Algorithm to Find the Minimum Spanning Tree of a Graph

Related Posts:

Recommended Articles: