Accueil > > > GRAPH THEORY : TRANSITIVE CLOSURE AND MUCH MORE ..!
GRAPH THEORY : TRANSITIVE CLOSURE AND MUCH MORE ..!
Information sur la source
Description
Howdy ;
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.
Source
-
- #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.\n\n";
- 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 :\n\n\n";
- 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("\n\n");
- 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 : -->\n\n\n");
- for(i=0;i<*l;i++)
- {
- for(j=0;j<*l;j++)
- printf("%8d",m[i][j]);
- printf("\n\n");
- }
- 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("\n\n");
- }
- 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 :\n\n\n";
- for(i=0; i<n; i++)
- {
- for(j=0;j<n;j++)
- printf("%8d",a[i][j]);
- printf("\n\n");
- }
- cout<<"\n\t\tPlease, 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());
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
#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.\n\n";
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 :\n\n\n";
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("\n\n");
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 : -->\n\n\n");
for(i=0;i<*l;i++)
{
for(j=0;j<*l;j++)
printf("%8d",m[i][j]);
printf("\n\n");
}
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("\n\n");
}
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 :\n\n\n";
for(i=0; i<n; i++)
{
for(j=0;j<n;j++)
printf("%8d",a[i][j]);
printf("\n\n");
}
cout<<"\n\t\tPlease, 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());
}
}
Sources du même auteur
Sources de la même categorie
Commentaires et avis
Discussions en rapport avec ce code source dans le forum
Théorie des Graphs Ti89 Titanium [ par jeanphilippe37 ]
Slt à tous, J'aimerai savoir s'il existe un programme pour faire le tableau de précédents etc.. pour la théorie des graphs. J'ai une Ti 89 Titani
|
Derniers Blogs
IMAGINE CUP 2012, MAKE A SIGN EN FINALEIMAGINE CUP 2012, MAKE A SIGN EN FINALE par junarnoalg
Voilà qui est fait, la nouvelle est officielle ! L'équipe belge "Make a Sign" va au pays des kangourous défendre son projet dans la catégorie Software Design. http://www.imaginecup.com/CompetitionsContent/Competition/WorldwideFinalists.aspx V...
Cliquez pour lire la suite de l'article par junarnoalg KINECT 1.5 IS OUT !KINECT 1.5 IS OUT ! par Vko
La version 1.5 du Kinect For Microsoft vient tout juste de sortir ! Plein de nouveautés: Tracking de squelette en Near Mode Détection en position assise Détection faciale avec un SDK dédié Documentation et des guideline (enfin) Un out...
Cliquez pour lire la suite de l'article par Vko LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) par richardc
Mise à jour des Web API du 14 Mai
Réservez dès maintenant votre journée du 20 juin pour le Windows Azure Dev Camp 2012 à Paris
Mise à jour de Team Foundation Service
MechCommander 2 sur Windows 8
Entity Framework 5 Release Candidate e...
Cliquez pour lire la suite de l'article par richardc REACTIVE EXTENSIONS : CONSOMMER DES SERVICES AVEC RX PARTIE 3, LES PIèGES à éVITERREACTIVE EXTENSIONS : CONSOMMER DES SERVICES AVEC RX PARTIE 3, LES PIèGES à éVITER par Groc
Une mauvaise utilisation de rx lors de l'écriture d'une couche d'accès à des services peut conduire à des cas embarassants avec des erreurs mal gérées, des appels qui ne partent lorsqu'ils le devraient, et même des résultats incorrects . le tout nuis...
Cliquez pour lire la suite de l'article par Groc SHAREPOINT BLOG SITE, PROBLèME D'ARCHIVESSHAREPOINT BLOG SITE, PROBLèME D'ARCHIVES par junarnoalg
Dernièrement, nous avons migré le site
myTIC
vers un nouveau serveur SharePoint 2010. Dans les contenus que nous vouloins récupérer, nous avions un certain nombre de blogs.
Nous avons utilisé les commandes Power...
Cliquez pour lire la suite de l'article par junarnoalg
Forum
MATRICE TEMPLATEMATRICE TEMPLATE par hjr2610
Cliquez pour lire la suite par hjr2610 RE : SAC A DOS RE : SAC A DOS par hadjkaddour
Cliquez pour lire la suite par hadjkaddour
Logiciels
sDEVIS-FACTURES vlPRO (8.1.0.3)SDEVIS-FACTURES VLPRO (8.1.0.3)sDEVIS-FACTURES vlPRO a été mis au point pour les particuliers, créateurs, entrepreneurs, artisa... Cliquez pour télécharger sDEVIS-FACTURES vlPRO 974 Application Server (12.2.4.6)974 APPLICATION SERVER (12.2.4.6)Développez de puissantes applications dans un environnement de 'cloud computing', clusterisé, séc... Cliquez pour télécharger 974 Application Server vPicture (1.4.2.1)VPICTURE (1.4.2.1)Avec vPicture, hébergez vos images facilement et rapidement.
vPicture est un utilitaire simple, ... Cliquez pour télécharger vPicture Easy-Planning (2.2.1.6)EASY-PLANNING (2.2.1.6)Easy-Planning permet de créer des plannings sous la représentation de diagrammes et est adapté au... Cliquez pour télécharger Easy-Planning COM-BACKUP (2.0)COM-BACKUP (2.0)
COM-BACKUP est un logiciel de sauvegarde qui permet de planifier les sauvegardes de vos dossiers ...
Cliquez pour télécharger COM-BACKUP
|