LA FERMETURE TRANSITIVE

#include<stdio.h>
#include<conio.h>
#include <stdlib.h>
#include <time.h>
int n;
void test(int a,int b,int t[5][5])

	{
	int t1[5][5],t2[5][5],k,i,j,l;
	if (t[a][b]!=0)
		  {
		  printf("il existe un chemin de sommet a vers b de  longueur 1\n\n\n");
		  }
  if (t[a][b]==0)
	  {
	  //transferer t dans t1
		  for (i=1;i<=n;i++)
		  for (j=1;j<=n;j++)
			 t1[i][j]=t[i][j];

	  }
		k=n-1;
	  prod:
	  if (k!=0)
	  {
			 for(i=1;i<=n;i++)
			 for(j=1;j<=n;j++)
			  t2[i][j]=0;

		  for (l=1;l<=n;l++)
		  for (j=1;j<=n;j++)
		  for (i=1;i<=n;i++)
			 t2[j][l]=t2[j][l]+t1[j][i]*t[i][l];

						//tranferer t2 dans t1

					for (i=1;i<=n;i++)
					for (j=1;j<=n;j++)
					  t1[i][j]=t2[i][j];


		  if (t1[a][b]!=0)
		  {
		  printf("il existe un chemin de sommet a vers b de  longueur %d\n\n\n",n-k+1);
		  goto fin;
		  }
		 k=k-1;
		 goto prod;
	  }
	  else
	  printf("il n'y a pas de chemin entre %d et %d\n",a,b);



 fin:
 }
								  // la procedure de chemin pour la question N°4
  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 int chemin(int x,int y,int t[5][5])
	{
	int t1[5][5],t2[5][5],k,i,j,l,s;
		  s=0;
		  if (t[x][y]!=0)
			  s=1;

		  else
			  {
													 //transferer t dans t1
					  for (i=1;i<=n;i++)
					  for (j=1;j<=n;j++)
							t1[i][j]=t[i][j];


						k=n-1;
				 while(k!=0)
							{
								for (l=1;l<=n;l++)
								for (j=1;j<=n;j++)
								for (i=1;i<=n;i++)
									t2[j][l]=t2[j][l]+t1[j][i]*t[i][l];



												 //tranferer t2 dans t1
								for (i=1;i<=n;i++)
								for (j=1;j<=n;j++)
								 t1[i][j]=t2[i][j];


								if (t1[x][y]!=0)
								  s=1;

								k=k-1;
							}
				}
		 return s;
	}
///////////////////////////////////////*la procdure de la fermeture trasitive*//
int ferm(int t[5][5])
 {
		int m[5][5],m1[5][5],m2[5][5],m3[5][5],i,j,l,s;
																			//transferer t dans m1 etm2
		for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		{
		m[i][j]=t[i][j];
		m2[i][j]=t[i][j];
		}


 startf:
																	 //calcul le prduit de m1=m*t
					  for (i=1;i<=n;i++)
					  for (j=1;j<=n;j++)
					  m1[i][j]=0;


		  for (l=1;l<=n;l++)
		  for (j=1;j<=n;j++)
		  for (i=1;i<=n;i++)
		  m1[j][l]=m1[j][l]+m[j][i]*t[i][l];

					//// vers le booleen
					 for (i=1;i<=n;i++)
					 for (j=1;j<=n;j++)
						 {
						 if(m1[i][j]!=0)
						 m1[i][j]=1;
						 }

					///////////////////////////////transfrer m1 dans m
					  for (i=1;i<=n;i++)
					  for (j=1;j<=n;j++)
							 m[i][j]=m1[i][j];


					 for (i=1;i<=n;i++)
					  for (j=1;j<=n;j++)
							 m3[i][j]=m2[i][j]+m[i][j];

					 //// vers le booleen
					 for (i=1;i<=n;i++)
					 for (j=1;j<=n;j++)
						 {
						 if(m1[i][j]!=0)
						 m3[i][j]=1;
						 }

s=1;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			{
			  if(m2[i][j]!=m3[i][j])
			  s=0;
			}

if (s==1)
{
	 for (i=1;i<=n;i++)
	 for (j=1;j<=n;j++)
	 t[i][j]=m2[i][j];

}
  else
  {
	 for (i=1;i<=n;i++)
	 for (j=1;j<=n;j++)
	 m1[i][j]=m2[i][j];
 //
	for (i=1;i<=n;i++)
	for (j=1;j<=n;j++)
	m2[i][j]=m1[i][j]+m[i][j];


	 /////////////////////////
	 for (i=1;i<=n;i++)
					{
						for (j=1;j<=n;j++)
							{
							if(m2[i][j]!=0)
							m2[i][j]=1;
							else
							m2[i][j]=0;
							}
					}
	 goto startf;
	}
return 0;
}
 ///////////////////////////////////////////////////////////////////////////////////////
void circuit(int t[5][5])
{
 int i,h;
 h=0;
 ferm(t);

 for(i=1;i<=n;i++)
 {
  if(t[i][i]==1)
  h=1;
 }
 if(h==0)
 printf("il n'existe pas de circuit \n\n");
 else
 printf ("il existe  aux moins un circuit dans G\n\n");
 }
 //////////////////////////////////////ensemble des successeurs//////////////////////////


void successeur(int t[5][5],int x )
 {
  int i;


	printf("l'ensemble des successeurs de %d C'est l'ensemble \nD={",x);
		  for (i=1;i<=n;i++)
		  {
		  if (t[x][i]==1)
		  printf("%d,",i);
		  }
	 printf("\b");
	printf("}\n");
}
 void warshall(int t[5][5])
 {
  int i,j,k;

  for(k=1;k<=n;k++)
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	 t[i][j]=t[i][j]+(t[i][k]*t[k][j]);

	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	 {
	 if(t[i][j]!=0)
		t[i][j]=1;
	  }
    printf("*lamatrice associer à la fermeture transitive \na partir de l'algorithme de Wershall:\n\n");
	for(i=1;i<=n;i++)
	{
	for(j=1;j<=n;j++)
	 {
	 printf("     %d ",t[i][j]);
	 }
	 printf("\n\n\n");
	 }
											////////////////////////////
 }



						/*le programme principale */
void main()
{
int t[5][5],t1[5][5],m[5][5],t5[5][5],p,j,i,a,b,x,var;
	 printf("    ===========================================================\n");
	 printf("                     UNIVERSITE DE BEJAIA\n ");
	 printf("                   DEPARTEMENT D'INFORMATIQUE \n ");
	 printf("            ETUDIANT : TOUATI MOHAMED \n ");
	 printf("               MODLE DE RECHERCHE OPERATIONNELLE\n");
	 printf("    ===========================================================\n");
	 printf("                             ***bonjour***\n\n");
	  printf("TAPPEZ SUR UNE TOUCHE POUR COMANCER LES MANIPULATIONS :\n\n\n");
	  getch();
	  clrscr();
	 printf("    ===========================================================\n");
	 printf("                     UNIVERSITE DE BEJAIA\n ");
	 printf("                   DEPARTEMENT D'INFORMATIQUE \n ");
	 printf("            ETUDIANT : TOUATI MOHAMED \n ");
	 printf("               MODLE DE RECHERCHE OPERATIONNELLE\n");
	 printf("    ===========================================================\n\n");


time_t ti;
oui:
printf("introduire le nombre de sommet n  \n\n");
printf("n=");
scanf("%d",&n);
if (n>=5)
goto oui;

a:
printf(" pour avoir la matrice manualement tappez '1'  \n\n");
printf(" pour avoir la mtrice automatiquement tappez '2'  \n");
  scanf("%d",&p);
if(p!=1 && p!=2)
  {
	 goto a;
  }
if (p==1)
{
printf(" donnez maintenant les valeurs de la matrice:\n");
	for(i=1;i<=n;i++)
		{
		  for(j=1;j<=n;j++)
			  {
				ref:
				printf("X(%d,%d)=",i,j);
				scanf("%d",&t[i][j]);
				if (t[i][j]!=1&&t[i][j]!=0)
					{
					 printf("error!!!\a\n");
					printf("reffere l'introduction de la valeure de X(%d,%d)=0/1\n",i,j);
					 goto ref;
					 }
				}
		 }

}
else
{
srand((unsigned) time(&ti));
for(i=1;i<=n;i++)
	{
		 for(j=1;j<=n;j++)
			 {
			  t[i][j]=(rand() % 2);
			  printf("  %d    ",t[i][j]);
			  }
		 printf("\n\n\n");
	 }
 }
 getch();
 debvar:
 clrscr();
 //////////////////////////////////////////////////////
 //////////////////////////////////////////////////////
 /////////////////////////////debut////////////////////
 //////////////////////////////////////////////////////
 printf("                    * * * M E N U * * *\n\n");
 printf(" * AFFICHER LA MATRICE D'ADJACENCE........................(0)\n\n");
 printf(" * REINITIALISER LE GRAPHE................................(1)\n\n");
 printf(" * AFFECHER LES SOMMETS ET LES ARCS.......................(2)\n\n");
 printf(" * TESTER L'EXISTANCE D'UN CHEMIN.........................(3)\n\n");
 printf(" * AFFICHER LA MATRICE DE LA RELATION 'R'.................(4)\n\n");
 printf(" * CALCULER LA FERMETURE TRANSITIVE.......................(5)\n\n");
 printf(" * TESTER L'EXISTANCE DE CIRCUIT..........................(6)\n\n");
 printf(" * AFFICHER LES SUCCESSEURS D'UN SOMMET DONNE.............(7)\n\n");
 printf(" * ETABLIR LA FERMETURE TRANSITIVE DE 'WERSHLL'...........(8)\n\n");
 printf(" * TERMINER LE PROGRAMME..................................(9)\n");
 printf("                              CHOIX= ");
 scanf("%d",&var);
  if(var==0)
 {clrscr();
 goto var0;}
 if(var==1)
 {clrscr();
 goto oui;}
  if(var==2)
 {clrscr();
 goto var2;}
 if(var==3)
  {clrscr();
 goto var3;}
 if(var==4)
 {clrscr();
 goto var4;}
 if(var==5)
  {clrscr();
 goto var5;}
 if(var==6)
 {clrscr();
 goto var6;}
 if(var==7)
 {clrscr();
 goto var7;}
 if(var==8)
 {clrscr();
 goto var8;}
 if(var==9)
 {clrscr();
 goto var9;}
 if(var<0 ||var>9)
 {printf("la valeur choisit n'existe pas dans le menu!!\a\n");
 getch();
 clrscr();
 goto debvar;
 }
 var0:
 printf("M=\n");
		  for(i=1;i<=n;i++)
		  {
		  for(j=1;j<=n;j++)
		  {
			  printf("  %d    ",t[i][j]);
		  }
		  printf("\n\n\n");
		  }
		  getch();
 goto debvar;

 var2:
 printf(" \n l'ensemble des sommets X={ ");
  for(i=1;i<n;i++)
  printf("%d, ",i);
  printf("%d",n);
  printf("}");
 printf("\n l'ensemble des arcs G est U={");
  for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{ if(t[i][j]==1)
	  printf("(%d,%d)",i,j);

	}
	printf("}\n\n\n\n\n");
	getch(); //////////////////////////////////////////////var2
	goto debvar;
	var3:
	printf("introduire les deux sommets a et b \n");
	ra:
	printf("a=");
  scanf("%d",&a);
	 if (a>n ||a<=0)
	 {
	 printf("le sommet a n'existe pas!\a\n  ");
	 goto ra;
	 }
	 rb:
	 printf("b=");
  scanf("%d",&b);
	if (b>n ||b<=0)
	 {
	 printf("le sommet b n'existe pas!\a\n  ");
	 goto rb;
	 }
	test(a,b,t);
	getch();
	goto debvar;
	 clrscr();
			 var4:

	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		m[i][j]=chemin(i,j,t);

		 //afficage de la matrice aRb
  printf("On définie la matrice de la relation R tel que X x X--->{0,1},\n ");
  printf("                                             (x,y)|--->xRy,\n");
  printf("    xRy=1 si il existe un chemin de x vers y\n    xRy=0 si non\n\n");
  for(i=1;i<=n;i++)
		{
		for(j=1;j<=n;j++)
		{
		printf("%d       ",m[i][j]);
		}
		printf("\n\n\n");
		}
		getch();
		goto debvar;
//////////////////////////////////////////////////////////////////////////////////////////
////////////////////////question N°5//////////////////////////////
	  var5:

 clrscr();
 for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
 t1[i][j]=t[i][j];
  ferm(t1);
  printf("la matrice associée a la fermeture transitive est\n\n");
  for(i=1;i<=n;i++)
		{
		for(j=1;j<=n;j++)
		{
		printf("  %d    ",t1[i][j]);
		}
		printf("\n\n\n");
		}
  getch();
  goto debvar;
  ////////////////////////////////////
  var6:
circuit(t1);
	getch();
	 goto debvar;
	  var7:
	 printf("introduire le sommet x \n ");
	 succ:
	 printf("x=");
	 scanf("%d",&x);
			if (x<0 || x>n)
					{
					 printf("error!!!\a\n");
					printf("reffere l'introduction de la valeure de 0<=X<=%d\n\n",n);
					 goto succ;
					 }

	successeur(t,x);
		 getch();
	 goto debvar;

	var8:

					  for (i=1;i<=n;i++)
					  for (j=1;j<=n;j++)
						t5[i][j]=t[i][j];
	warshall(t5);

	getch();
	goto debvar;
	var9:
	printf("FIN DE L'APPLICATION!\n\n\n\n\n\n\n\n\n                        ****************MERCI****************\n\n\n\n\n\n\n\n\n\n\n\n");
  printf("                                   par Mr:TOUATI MOHAMED\n");
  printf("                                           et Mr:MEDJANI LARBI");
 }