Graph theory : transitive closure and much more ..!

Soyez le premier à donner votre avis sur cette source.

Snippet vu 3 904 fois - Téléchargée 21 fois

Contenu du snippet

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.

Billal BEGUERADJ

Source / Exemple :

#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.nn";
 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  :nnn";
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("nn");
 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  :   -->nnn");
 for(i=0;i<*l;i++)
 {
 for(j=0;j<*l;j++)
    printf("%8d",m[i][j]);
    printf("nn");
}
 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("nn");
}
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 :nnn";
 for(i=0; i<n; i++)
 {
 for(j=0;j<n;j++)
  printf("%8d",a[i][j]);
 printf("nn");
 }
 cout<<"nttPlease, 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());
  }
   }

A voir également

Ajouter un commentaire

Commentaires

PCBill
Messages postés
48
Date d'inscription
lundi 25 décembre 2006
Statut
Membre
Dernière intervention
29 septembre 2009

Bonjour Monsieur XKAMEN ;
Après la lecture de votre message, un large sourire a traversé mon visage : en fait, on puit aisément sentir dans votre intervention aussi bien de la sincérité que de la naivité.
Si je l'ai codé en Anglais c'est parce que j'ai prévu sa déposition sur un site anglophone (chose que je n'ai pas fait, en fin de compte : vive cppfrance !).
Et pour ce qui est de la carence des commentaires c'est certainement dû au caractère intuitif des procédures que j'ai y implémentées ; nonobstant, je suis tout à fait d'accord que pour un débutant il faut une bonne dose de commentaires.
Je tiens à vous signaler qu'il faut quand même tester tous ces magnifiques codes de cppfrance et ne pas se contenter de vérifier s'ils sont bien armés de commentaires !
En fait, je plaisante mon ami : autrement, je souhaite ne refaire les deux sottises que vous m'avez signalé.
Thank You Monsieur XKAMEN.

Bonjour Monsieur CYBERBOY2054 ;
Vos remarques sont pertinentes, je vous en remercie.
Je n'ai point prêté attention à l'optimisation algorithmique qui a pris en charge la recherche des circuits : votre remarque est à a juste valeur.
Toutefois, j'aimerais signaler que le but majeur de ce petit programme est la mise en lumière ?programmation en C, je veux dire- de l'algorithme le plus intuitif et le plus naïf qu'il et que l'on trouve dans la littérature. J'ai cherché maintes fois l'implémentation du ledit algorithme sur le net : en vain. C'est ainsi que j'ai décidé de le déposer ici même.
Pour ce qui est du reste, vous savez mieux que moi qu'aussi perfectionné un algorithme il est toujours appelé à une optimisation meilleure.
Mon code s'exécute parfaitement : you can try it yourself !
Merci pour vos remarques.
.
Cyberboy2054
Messages postés
173
Date d'inscription
jeudi 20 décembre 2001
Statut
Membre
Dernière intervention
22 août 2008

Interesting, yet some parts could be algorithmically optimised,
for example:
# 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++;
# }
# }
-> You only want to check for the diagonal, but walk through the whole array.
Here is an idea:
# 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++)
# {
# if(a[i][i]==1)
# {
# nb++;
# }
# }
# ....
Only 10*10 entries in the worst case but your solution will perform 100 tests, whille mine does only 10 :p

I didn't try to compile, but the code doesn't look to be complete, can you give us what may be missing ?
xkamen
Messages postés
26
Date d'inscription
vendredi 8 avril 2005
Statut
Membre
Dernière intervention
31 janvier 2008

Bonjour PCBill,

Je trouve que pour un code débutant, cela manque un peu de commentaires surtout que tout est en anglais, pour le peu qu'il y ait des titres. Je pense que tu devrais rajouter des commentaires et si possible les mettre en français, pour les débutants qui souhaiteraient comprendre comment ton programme fonctionne. Personnellement, je n'ai pas toujours le temps de regarder de manière approfondie un programme posté sur cppfrance, donc s'il n'y a pas de commentaires, je ne le regarde même pas.

Merci.

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.