Source code of Warshall Algorithm is listed below
/*
IDE : CODE BLOCKS 10.05
warshall.cpp
*/
//USE OF WARSHALL'S ALGORITHM TO CREATE TRANSITIVE CLOSURE OF A GRAPH
#include<iostream>
#include<conio.h>
#include<windows.h>
using namespace std;
const int num_nodes =10;
int main()
{
//.VARIABLE DECLARATION
int num_nodes,k,n,choice;
char i,j,res,graph[]="TRANSITIVE CLOSURE";
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";
for(int i=0;i<=9;i++)
{
cout<<"\n\t\t\t"<<graph[i];
}
cout<<" CLOSURE\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";
for(int i=0;i<num_nodes;i++)
{
cout<<"\t\t\t";
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";
for(int i=0;i<num_nodes;i++)
{
cout<<"\t\t\t";
for(int j=0;j<num_nodes;j++)
cout<<adj[i][j]<<" ";
cout<<"\n";
}
//...END MAIN
getch();
return 0;
}
/*
IDE : CODE BLOCKS 10.05
warshall.cpp
*/
//USE OF WARSHALL'S ALGORITHM TO CREATE TRANSITIVE CLOSURE OF A GRAPH
#include<iostream>
#include<conio.h>
#include<windows.h>
using namespace std;
const int num_nodes =10;
int main()
{
//.VARIABLE DECLARATION
int num_nodes,k,n,choice;
char i,j,res,graph[]="TRANSITIVE CLOSURE";
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";
for(int i=0;i<=9;i++)
{
cout<<"\n\t\t\t"<<graph[i];
}
cout<<" CLOSURE\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";
for(int i=0;i<num_nodes;i++)
{
cout<<"\t\t\t";
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";
for(int i=0;i<num_nodes;i++)
{
cout<<"\t\t\t";
for(int j=0;j<num_nodes;j++)
cout<<adj[i][j]<<" ";
cout<<"\n";
}
//...END MAIN
getch();
return 0;
}
Drop a Comment if any error occurs !!!
No comments:
Post a Comment