Graph theory : transitive closure and much more ..!
Contenu du snippet
The following code presents 2 ways to input your adjacency matrix then it performs some transitive closure methods including the warshall's one and some other primitive things. Just for beginners !
See you soon.
Billal BEGUERADJ
See you soon.
Billal BEGUERADJ
Source / Exemple :
#include<stdio.h>
#include<iostream.h>
#include<conio.h>
#include<dos.h>
#include<time.h>
#include<stdlib.h>
#define max 10
/******************************************************************************/
/******************************************************************************/
/* Definition of our program's procedure and functions */
/******************************************************************************/
/******************************************************************************/
void display(int [10][10],int); // to display the resulted matrix
void vertices(int); // returns the listing of vertices
void edges(int[10][10],int); // returns the listing of edges
void move(int[10][10],int[10][10],int); // for moving data from a given matrix to an other
void addition(int[10][10],int[10][10],int[10][10],int ); // for adding the data of two matrices
void multiply(int[10][10],int[10][10],int[10][10],int); // for multiplying to matrices
int equality(int[10][10],int[10][10],int ); // seeking if two matrices are the same
void trans_hull(int [10][10],int); //
void transclosure2(int [10][10],int ); // transitive closure using the algo seen in our coure
void successors(int[10][10],int); // to display a given edge's successor
void check_if_there_is_at_least_a_circuit(int [10][10],int ); // fetching the existence of circuits
void warshall_hull(int [10][10],int[10][10]); // warshall transitive closure
void border(); // this procedure draw our pretty border
void generate_adjac_matrix(int[10][10],int); // this allows you to have a random adjacency matrix from the compiler
void loop(int [10][10],int); // this procedure outputs the number of loops in our graph
void input(int [10][10],int*); // to input the adjacency matrix
int n; // order of the adjacency matrix must be declared a global variable
int mat[10][10]; // the adjacency matrix must be declared a global variable too
/******************************************************************************/
/*******************************************************************************/
/* Here's the beginning of the main program */
/*******************************************************************************/
/******************************************************************************/
void main(void)
{
int x=1,q=0 ;
int path[10][10];
textbackground(BLUE);
textcolor(10);
do{
clrscr(); // clear the secreen
sound(5000);
delay(500);
nosound();
border();
gotoxy(8,4);
cout<<" << Dear, welcome >>. n";
gotoxy(8,7);
cout<<"1) Input your adjacency matrix. n";
gotoxy(8,8);
cout<<"2) Transitive closure using the algo seen in course.n";
gotoxy(8,9);
cout<<"3) Display the graph's vertices.n";
gotoxy(8,10);
cout<<"4) Listing of the existing paths in the graph.n";
gotoxy(8,11);
cout<<"5) Listing the successors of a given edge.n";
gotoxy(8,12);
cout<<"6) Checking of existing circuits in the graph. n";
gotoxy(8,13);
cout<<"7) Transitive Closure using the Warshall's algo.nn";
gotoxy(8,16);
cout<<"a) Display the graph's edges.n";
gotoxy(8,17);
cout<<"b) Display the number of loops in the graph.n";
gotoxy(8,18);
cout<<"c) Display the adjacency matrix.n";
gotoxy(8,19);
cout<<"ESC ------> Abort the software.";
gotoxy(8,21);
cout<<"Make your choice, please : ";
switch (getch())
{
case '1':
input(mat,&n);
q++;
break;
case '2':
if(q!=0)
{
trans_hull(mat,n);
}
else
{
printf("a");
}
break;
case'3': if(q!=0)
{
clrscr();
edges(mat,n);
while(!kbhit());
}
else
{
printf("a");
}
break;
case'4':
if(q!=0)
{
cout<<"Here is the transitive closure :n";
trans_hull(mat,n);
}else
{
printf("n");
}
break;
case'5':
if(q!=0)
{
successors(mat,n);
}else
{
printf("n");
}
break;
case'6':
if(q!=0)
{
clrscr();
transclosure2(mat,n);
}else
{
printf("n");
}
break;
case'7':
if(q!=0)
{
warshall_hull(mat,path);
}else
{
printf("a");
}
break;
case'a':
if(q!=0)
{
clrscr();
vertices(n);
}else
{
printf("a");
}
break;
case'b':
if(q!=0)
{
loop(mat,n);
}else
{
printf("a");
}
break;
case'c':
if(q!=0)
{
display(mat,n);
}else
{
printf("a");
}
break;
case 27:
x=0;
break;
default:
printf("a");
}
} while(x!=0);
}// end of the main program
///////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
/******************************************************************************/
/******************************************************************************/
/******************************************************************************/
/******************************************************************************/
/******************************************************************************/
/******** Hereafter we're going to implement the needed procedure **********/
/****************** defined above *************************/
/*----------------------------------------------------------------------------*/
/******************************************************************************/
/******************************************************************************/
/******************************************************************************/
/******************************************************************************/
/******************************************************************************/
/* Implémentation of the procedure that allows us to input our */
/* adjacency matrix */
/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/
void input(int m[10][10],int *l)
{
int i,j;
int choice;
clrscr();
do{
border();
gotoxy(6,10);
cout<<" Adjacency matrix :nnn";
gotoxy(10,12);
cout<<"1) Input it yourself.n";
gotoxy(10,14);
cout<<"2) Give the hand to your compiler. ";
cin>>choice;
}while(choice!=1 && choice!=2);
switch(choice)
{
case 1:
clrscr();
border();
do{
gotoxy(6,10);
printf("Input the boundaries ( order ) of your adjacency matrix : ");
scanf("%d",l);
}while(*l<=0 || *l>max);
clrscr();
border();
gotoxy(6,10);
cout<<"Please, input the elements of your adjacency matrix : ";
printf("nn");
clrscr();
border();
for(i=0;i<*l;i++)
for(j=0;j<*l;j++)
{
label :gotoxy(8+6*j,3+2*i);
scanf("%d",&m[i][j]);
if(m[i][j]!=1 && m[i][j]!=0 )
goto label;
}
clrscr();
border();
gotoxy(6,4);
printf("<--- Here is the resulted matrix : -->nnn");
for(i=0;i<*l;i++)
{
for(j=0;j<*l;j++)
printf("%8d",m[i][j]);
printf("nn");
}
gotoxy(6,18);
cout<<"Press any key to continue ...";
while(!kbhit());
break;
case 2:
generate_adjac_matrix(m,n);
break;
}
}
/*******************************************************************************/
/*******************************************************************************/
/* this procedure moves data from one matrix to an other one */
/*******************************************************************************/
/*******************************************************************************/
void move(int t1[10][10],int t2[10][10],int l)
{
int i,j;
for(i=0;i<l;i++)
{
for(j=0;j<l;j++)
{
t2[i][j]=t1[i][j];
}
}
}
/*******************************************************************************/
/*******************************************************************************/
/* procedure that outputs a given matrix */
/*******************************************************************************/
/*******************************************************************************/
void display(int m[10][10],int l)
{int i,j;
clrscr();
border();
gotoxy(6,10);
printf("n<--- If a[i][j] is worth 1 it means there is a path : -->n");
cout<<"t between the vertex i and that of j. n";
for(i=0;i<l;i++)
{
for(j=0;j<l;j++)
printf("%8d",m[i][j]);
printf("nn");
}
getch();
}
/*******************************************************************************/
/*******************************************************************************/
/* Matrix multiplication procedure */
/******************************************************************************/
/*******************************************************************************/
void multiply(int a[10][10],int b[10][10],int c[10][10],int l)
{
int i,j,k;
for(i=0;i<l;i++)
for(j=0;j<l;j++)
{
c[i][j]=0;
for(k=0;k<l;k++)
c[i][j]=c[i][j]||(a[i][k]&& b[k][j]);
}
}
/*******************************************************************************/
/*******************************************************************************/
/* Matrix addition procedure */
/*******************************************************************************/
/*******************************************************************************/
void addition(int a[10][10],int b[10][10],int c[10][10],int l )
{
int i,j;
for(i=0;i<l;i++)
for(j=0;j<l;j++)
c[i][j]=a[i][j]||b[i][j];
}
/*******************************************************************************/
/*******************************************************************************/
/* Matrix equality checking procedure */
/*******************************************************************************/
/*******************************************************************************/
int equality(int a[10][10],int b[10][10],int l )
{
int i=0,j=0;
int ok=8;
while( i<l && j< l && ok==0)
{
if(a[i][j]==b[i][j])
{
i++;
j++;
}else
{
ok=1;
break;
}
}
return ok;
}
/*******************************************************************************/
/*******************************************************************************/
/* lock hull procedure ackording to the */
/* algo implemented together */
/* in the course */
/*******************************************************************************/
/*******************************************************************************/
void trans_hull(int mat[10][10],int n)
{
int found=0;
int a[10][10];
int b[10][10];
int c[10][10];
int d[10][10];
int e[10][10];
move(mat,e,n);
move(mat,d,n);
move(mat,a,n);
move(mat,b,n);
label:
multiply(a,b,c,n);
move(c,a,n);
addition(d,a,d,n );
found = equality(e,d,n);
if(found==0)
{
move(d,e,n);
goto label;
}
else
{
clrscr();
display(d,n);
}
}
/******************************************************************************/
/******************************************************************************/
/* this procedure displays the graph's vertices */
/******************************************************************************/
/******************************************************************************/
void vertices(int n)
{
border();
gotoxy(6,10);
cout<<"Listing of the graph's edges : n";
cout<<"{ ";
for(int i=1;i<n;i++)
cout<<"("<<i<<"), ";
if( i==n)
cout<<"("<<i<<") ";
cout<<"}";
while(!kbhit());
}
/******************************************************************************/
/******************************************************************************/
/* this procedure outputs the graph's edges */
/******************************************************************************/
/******************************************************************************/
void edges(int mat[10][10],int n)
{
border();
gotoxy(6,10);
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j)
if(mat[i][j]==1){
cout<<(i+1)<<" ---> "<<(j+1)<<"n";}
cout<<"Press Any key to coninue ...";
while(!kbhit());
}
/******************************************************************************/
/******************************************************************************/
/* This procedure displays the sucessors of a given vertex */
/******************************************************************************/
/******************************************************************************/
void successors(int a[10][10],int n)
{
int i; // the edge you would like to list its sucessors
do{
clrscr();
border();
gotoxy(6,10);
cout<<"Input the edge you would like to list its sucessors : from 0 to n-1 ";
cin>>i;
}while(i>(n-1)); // the edge must not overcome the matrix's boundaries
gotoxy(6,12);
cout<<"Listing of your edge's successors :n ";
for(int j=0;j<=n;j++)
if(a[i][j]==1){
cout<<"{ "<<(j+1)<<" , }"; }
while(!kbhit());
}
/******************************************************************************/
/******************************************************************************/
/* This procedure examines if there are circuits in our graph */
/* and outputs those circuits number */
/******************************************************************************/
/******************************************************************************/
void check_if_there_is_at_least_a_circuit(int a[10][10],int n)
{
int nb=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
if(a[i][j]==1&& i==j)
{
nb++;
}
}
border();
gotoxy(6,10);
cout<<"There "<<nb<<" circuits in your graph !";
gotoxy(6,12);
cout<<"Press any key to continue ...";
while(!kbhit());
}
////////////////////////////////////////////////////////////////////////////////
/*******************************************************************************/
/* second transitive closure */
/*******************************************************************************/
/******************************************************************************/
void transclosure2(int mat[10][10],int n)
{
int found=0;
int a[10][10];
int b[10][10];
int c[10][10];
int d[10][10];
int e[10][10];
move(mat,e,n);
move(mat,d,n);
move(mat,a,n);
move(mat,b,n);
label:
multiply(a,b,c,n);
move(c,a,n);
addition(d,a,d,n );
found = equality(e,d,n);
if(found==0)
{
move(d,e,n);
goto label;
}
else
{
clrscr();
check_if_there_is_at_least_a_circuit(d,n );
while(!kbhit());
}
}
/******************************************************************************/
/******************************************************************************/
/* Implementation of the warshall's famous algorithme */
/******************************************************************************/
/******************************************************************************/
void warshall_hull( int adjmat[10][10], int path[10][10])
{
int i,j,k;
clrscr();
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
path[i][j] = adjmat[i][j];
for(i = 0;i <n; i++)
for(j = 0;j < n; j++)
if(path[i][j] == 1)
for(k = 0; k < n; k++)
if(path[j][k] == 1)
path[i][k] = 1;
clrscr();
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%5d",path[i][j]);
printf("n");
}
cout<<"Press any key to continue ...";
while(!kbhit());
}
/*******************************************************************************/
/*******************************************************************************/
/* this procedure draws the our pretty border */
/*******************************************************************************/
/*******************************************************************************/
void border(){
int i;
clrscr();
for(i=3;i<78;i++){
gotoxy(i,1);
printf("");
gotoxy(i,22);
printf("*");
gotoxy(i,25);
printf("");}
for (i=0;i<26;i++){
gotoxy(3,i);
printf("");
gotoxy(78,i);
printf(""); }
gotoxy(8,24);
printf(" Billal BEGUERADJ ");
}
/******************************************************************************/
/******************************************************************************/
/* this procedure tells the compiler to generate */
/* a random adjacency matrix */
/******************************************************************************/
/******************************************************************************/
void generate_adjac_matrix(int a[10][10],int n)
{
int i,j;
clrscr();
border();
gotoxy(6,10);
cout<<"Input the number of your graph edges : ";
scanf("%d",&n);
randomize();
for(i=0; i<n; i++)
for(j=0;j<n;j++)
a[i][j]= rand() % 2;
clrscr();
border();
gotoxy(6,4);
cout<<"Hereafter is the adjacency matrix generated randomly by your compiler :nnn";
for(i=0; i<n; i++)
{
for(j=0;j<n;j++)
printf("%8d",a[i][j]);
printf("nn");
}
cout<<"nttPlease, press any key to continue ...";
while(!kbhit());
}
/******************************************************************************/
/******************************************************************************/
/* Implementation of the procedure that outputs */
/* the number of loops in our graph */
/******************************************************************************/
/******************************************************************************/
void loop(int mat[10][10],int n)
{
int i,j;
int nb=0;
clrscr();
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(mat[i][j]==1 && i==j)
nb++;
if(nb==0)
{
border();
gotoxy(6,10);
cout<<"There is no loop in your graph !";
gotoxy(6,10);
cout<<"so your graph is not reflexive.";
while(!kbhit());
}
else
if(nb==n)
{
border();
gotoxy(6,8);
cout<<"There are "<<nb<<" loops in your graph";
gotoxy(6,10);
cout<<"Your graph is reflexive !";
while(!kbhit());
}
else
{ border();
gotoxy(6,8);
cout<<"There are "<<nb<<" loops in your graph";
gotoxy(6,10);
cout<<"and your graph is not reflexive.";
while(!kbhit());
}
}
A voir également
- Graph theory : transitive closure and much more ..!
- Graph php ✓ - Forum PHP
- Graph c# - Forum C# / .NET
- Graph pert ✓ - Forum Visual Basic
- Bases de données graph - Forum Java
- Casio graph 80 - Forum ASM
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.