Saturday, May 18, 2013

Implementation of Warshall's Algorithm in C++ with Source Codes

Warshall's algorithm is used to find the transitive closure of a graph. It's one of the efficient method to compute closure path that can be produced. Transitive closure is an important application in graph theory in computer science.
The following provides the source codes for implementing the Warshall's algorithm:

``````
//.............................USE OF WARSHALL'S ALGORITHM TO CREATE TRANSITIVE CLOSURE OF A GRAPH..........

#include<iostream>
#include<conio.h>

using namespace std;
const int num_nodes =10;

int main()
{
//..............................................................VARIABLE DECLARATION
int num_nodes,k,n;
char i,j,res,c;
int adj[10][10],path[10][10];

cout<<"\n\t\t\t\t.............................................................................\n";
cout<<"\n\t\t\t\t\"USE OF WARSHALL'S ALGORITHM TO CREATE TRANSITIVE CLOSURE OF A GRAPH\"";
cout<<"\n\t\t\t\t.............................................................................\n";

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";

//..................................................................CREATING ADJACENCY MATRIX

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;
}

//...................................................................DISPLAYING THE ADJ. MATRIX

cout<<"\n........................................Adjacency 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";
}

//...................................................................APPLYING WARSHALL'S ALGORITHM

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];

//....................................................................DISPLAYING THE TRANSITIVE CLOSURE

cout<<"\n........................................Transitive 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";
}

//...................................................................END MAIN

getch();
return 0;

}

``````

1 comment :

1. hi. where did the value 65 (used in creating the adjacency matrix) came from? thanks. :)