La fermeture transitive
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
université de bejaia
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
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.