La fermeture transitive

Soyez le premier à donner votre avis sur cette source.

Vue 8 473 fois - Téléchargée 359 fois

Description

ce programme resume quelque notions de base de la theorie des graphe la fermeture transitive d'un graphe l'existance d'un circuit d'un chemin dans un graphe ...etc

Source / Exemple :


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

Conclusion :


université de bejaia

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
2
Date d'inscription
lundi 14 novembre 2005
Statut
Membre
Dernière intervention
24 juillet 2008

C'est vrai qu'il est peu compréhensible (lol). Je vais peut-être jeté un coup d' oeil sur ton code.. mais il fait quoi au juste? Au cas où j'arriverai pas à le compiler... :P
Messages postés
5
Date d'inscription
mardi 22 juillet 2008
Statut
Membre
Dernière intervention
4 septembre 2008

je n'ai rien compris a tout cela un peut d'aide stp
Messages postés
871
Date d'inscription
jeudi 6 juillet 2006
Statut
Membre
Dernière intervention
6 janvier 2012
1
salut

sur la ligne 56 je pense

goto fin;
}
k=k-1;
goto prod;
}
else
printf("il n'y a pas de chemin entre %d et %d\n",a,b);
fin:
; } <=== ici t'a oublié de mettre " ; "

et ici sur 255

int main() <== pas "void"
{
int t[5][5]

et aussi comme c'est int main alors c'est int clrscr();

printf("TAPPEZ SUR UNE TOUCHE POUR COMANCER LES MANIPULATIONS :\n\n\n");
getch();
int clrscr();
printf(" ===========================================================\n");

d'ailleur tout les "clrscr();" dans la int main doivent etre "int clrscr();"

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.