GRAPH THEORY : TRANSITIVE CLOSURE AND MUCH MORE ..!

#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());
		}
	  }