Opérations sur les graphes

Les opérations de base sur les graphes sont:

• initialisation et destruction du graphe
• ajout, suppression de sommets
• ajout, suppression de liaisons (arc ou arête)

[modifier] Graphes statiques

[modifier] Spécifications

init_graphe : entier x booléen -> graphe

init_graphe initialise un graphe contenant un nombre de sommets fixe (ordre), l'information indiquant si le graphe est orienté et renvoit le nouveau graphe.

libere_graphe: -> graphe

libere_graphe libère le graphe passé en paramètre.

affiche_graphe: -> graphe

affiche_graphe affiche la matrice d'adjacence sur la sortie standard.

ajout_arc : graphe x entier x entier x flottant

ajout_arc ajoute un arc entre les sommets src et dest possédant un coût cout. (graphe orienté)

ajout_arrete : graphe x entier x entier x flottant

ajout_arrete ajoute une arrête entre les sommets src et dest possédant un coût cout. (graphe non-orienté)

[modifier] Implémentation

[modifier] C

t_graphe_s init_graphe(int ordre, int estOriente);
void libere_graphe(t_graphe_s g);
void affiche_graphe(t_graphe_s g);
void ajout_arc(t_graphe_s g, unsigned int src, unsigned int dest, float cout);
void ajout_arrete(t_graphe_s g, unsigned int src, unsigned int dest, float cout);

t _graphe_s init_graphe(int ordre, int estOriente)
{
   t_graphe_s res;
   int i,j;
   res.estOriente = estOriente;
   res.ordre      = ordre;
   res.adj        = malloc(ordre*ordre*sizeof(float));
   for(i=0;i<res.ordre;i++)
      for(j=0;j<res.ordre;j++)
         *(res.adj+i*res.ordre+j) = 0.0;
   return res;
}
void libere_graphe(t_graphe_s g)
{
   free(g.adj);
   g.adj = NULL;
 }

void affiche_graphe(t_graphe_s g)
{
   int i,j;
   
   printf("\tOrdre: %u\n\tEst oriente: %d\n\n", g.ordre, g.estOriente);

   printf("Liaison x -> y\n\n");

   printf("\n \\ y\n");
   printf("|x\\");
   for(i=0;i<g.ordre*4+1;i++) /* précision = 1 un chiffre après la virgule soit 3 digits */
      printf("-");
      
   printf("\n");
   for(i=0;i<g.ordre;i++)
   {
      printf("|%d|",i);
      for(j=0;j<g.ordre;j++)
         printf("%.1lf ", *(g.adj+i*g.ordre+j));
      printf("|\n");
   }
   for(i=0;i<g.ordre*4+4;i++)
      printf("-");
   printf("\n");      
}

void ajout_arc(t_graphe_s g, unsigned int src, unsigned int dest, float cout)
{
   *(g.adj+(src-1)*g.ordre+(dest-1)) = cout;
}

void ajout_arrete(t_graphe_s g, unsigned int src, unsigned int dest, float cout)
{
   *(g.adj+(src-1)*g.ordre+(dest-1)) = cout;
   *(g.adj+(dest-1)*g.ordre+(src-1)) = cout;
}

[modifier] CAML

[modifier] Graphes dynamiques

[modifier] Spécifications

[modifier] Implémentation

[modifier] C

[modifier] CAML