2014:02:17:Graphes

Révision par les graphes

Ce TP a pour but de vous faire réviser le C standard au travers d'un peu de manipulation algorithmique sur les graphes.

Nous allons manipuler une représentation dynamique (légèrement différente de celle du TD d'algo) et effectuer un parcours profondeur classique au cours duquel nous construirons un fichier au format graphviz représentant l'arbre courant du parcours.

Construire le graphe

Pour construire le graphe, nous allons partir d'une représentation statique (sous forme de matrice, donc) pour faire simple cette matrice sera représenter en dure dans notre code.

Note sur les numéros de sommets: il est souvent commode d'avoir les numéros de sommet du graphe qui commencent à 1 bien que les tableaux commencent à 0. pour régler la question, nous choisirons de numéroter les sommets à partir de 1, mais lors de la lecture de la matrice, décalerons le numéros de sommets: la ligne 0 correspondra donc au sommet 1.

La structure choisie est une structure hybride: les listes d'adjacences sont dynamiques mais on utilise un vecteur pour représenter l'ensemble de sommets. Une conséquence pratique de l'utilisation d'un vecteur est que l'on peut directement utiliser le numéro du sommet comme référence à celui-ci.

/* graph.h : the graph data structure */
 
#include <stdlib.h>
 
#ifndef _GRAPH_H_
#define _GRAPH_H_
 
typedef struct s_adj   *adj;
 
struct s_adj {
  size_t        src, dst;
  adj           next;
};
 
typedef struct s_vertex *vertex;
 
struct s_vertex {
  size_t        ins, outs;
  adj           succ, pred;
};
 
struct s_graph {
  size_t        order;
  vertex        vertices;
};
 
typedef struct s_graph *graph;
 
/* Build graph from matrix  , */
 
void  add_link(graph g, int src, int dst);
graph graph_from_matrix(size_t order, int madj[]);
 
#endif

Pour simplifier l'accès aux sommets, on laissera vide la première case du vecteur de sommets.

Construction

• Compléter l'implémentation du type graphe suivante:

/* graph.c : Graph implem */
 
#include <stdlib.h>
#include <stdio.h>
#include "graph.h"
 
// add a link between vertex src and dst in g
void add_link(graph g, int src, int dst)
{
  // FIX ME !
}
 
// The array is a linear version of the matrix,
// the logial cell cell (i,j) is at index (i * order + j)
// if this cell is true (!= 0) then there's a link between
// vertex (i+1) and vertex (j+1)
graph graph_from_matrix(size_t order, int madj[])
{
  // FIX ME !
}

Détails auquels il faut faire attention:

• le graphe est orienté, dans la fonction add_link il faut bien penser à ajouter un élément dans la liste des successeurs de src et dans la liste des prédécesseurs de dst.
• chaque sommet stocke ses deux demi-degrés dans les champs ins (demi-degré intérieur) et outs (demi-degré extérieur), il faut bien les mettre à jour dans add_link.
• pour être sûr que les sommets soient rencontrés dans l'ordre croissant pendant le parcours, il faut soit ajouter les sucesseurs en fin de liste (plus compliqué) soit parcourir la ligne de la matrice à l'envers …

Affichage via dot

Pour visualiser le graphe, nous allons utiliser le format graphviz, pour ça je vous fourni quelques petites fonctions d'affichage toutes prêtes:

/* to_dot.h: Dot output */
 
#include <stdlib.h>
 
#ifndef _TO_DOT_H_
#define _TO_DOT_H_
 
typedef struct s_dot *dot_file;
 
// open a dot file with name file_name
// the graph (in the dot file) wil be nammed graph_name
dot_file open_dot_graph(char *file_name, char *graph_name);
 
// Close and free a previously openned dot file
void close_dot_graph(dot_file df);
 
// print an edge (in graph or spanning tree)
void print_edge(dot_file df, int src, int dst);
 
// print a forward edge in a spanning tree
void print_forward_edge(dot_file df, int src, int dst);
 
// print a backward edge in a spanning tree
void print_back_edge(dot_file df, int src, int dst);
 
// print a cross edge in a spanning tree
void print_cross_edge(dot_file df, int src, int dst);
 
#endif

… et l'implem ..

/* Dot output */
 
#include <stdlib.h>
#include <stdio.h>
 
#include "to_dot.h"
 
 
struct s_dot {
  FILE         *file;
};
 
dot_file open_dot_graph(char *file_name, char *graph_name)
{
  dot_file      df;
  df = malloc(sizeof (struct s_dot));
  df->file = fopen(file_name,"w");
  fprintf(df->file,"digraph %s {\n",graph_name);
  return df;
}
 
void close_dot_graph(dot_file df)
{
  fprintf(df->file, "}\n");
  fclose(df->file);
  free(df);
}
 
void print_tree_edge(dot_file df, int src, int dst)
{
  fprintf(df->file, "  %d -> %d;\n", src, dst);
}
 
void print_forward_edge(dot_file df, int src, int dst)
{
  fprintf(df->file, "  %d -> %d [color=\"blue\" constraint=\"false\"];\n",
          src, dst);
}
 
void print_back_edge(dot_file df, int src, int dst)
{
  fprintf(df->file, "  %d -> %d [color=\"red\" constraint=\"false\"];\n",
          src, dst);
}
 
void print_cross_edge(dot_file df, int src, int dst)
{
  fprintf(df->file, "  %d -> %d [color=\"orange\" constraint=\"false\"];\n",
          src, dst);
}

• Écrire la fonction graph_to_dot(fname, name, g) qui produit un fichier graphviz via les fonctions de to_dot.h

// To be added in graph.h and graph.c
void graph_to_dot(char *fname, char *name, graph g);

Pour cette partie vous n'aurez besoin que des fonctions open_dot_graph, close_dot_graph et print_edge.

Pour tester tout ça, voici un petit main accompagné d'un graphe sous-forme de matrice.

size_t order = 8;
 
int mat_graph[] = {
  0, 1, 0, 0, 1, 0, 0, 1,
  0, 0, 1, 0, 0, 0, 0, 0,
  0, 1, 0, 1, 0, 0, 0, 0,
  0, 1, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 1, 0, 0,
  1, 0, 1, 0, 0, 0, 1, 1,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
};
 
int main()
{
  graph g;
 
  g = graph_from_matrix(order, mat_graph);
 
  graph_to_dot("graph.dot", "G", g);
 
  return 0;
}

Vous pourrez après visualiser le graph en générant une image via dot (ou tout autre programme de la famille graphviz.)

$ dot -T png graph.dot -O
$ display graph.dot.png

Parcours profondeur

L'objectif est maintenant d'implémenter un parcours profondeur traditionnel non complet avec un point de départ donné. Notre objectif sera d'afficher l'arbre du parcours avec tous les types d'arcs.

Dans l'exercice précédent vous avez tous les fonctions d'affichages pour les différents types d'arc, il ne vous reste plus qu'à les détecter. Le code de la fonction d'appel est fournie, il ne vous reste donc plus que la fonction récursive.

/* depthfirst.c: Depthfirst traversal */
 
#include <stdlib.h>
#include "to_dot.h"
#include "graph.h"
 
// g    : graph
// src  : current vertex
// po   : prefix order (filled with 0 at init)
// so   : suffix order (filled with 0 at init)
// count: pointer to the counter for prefix/suffix order
// df   : dot file for the outpout
void recdf(graph g, int src, int po[], int so[], size_t *count, dot_file df)
{
  // FIX ME !
}
 
void depthfirst(char *fname, char *gname, graph g, int src)
{
  int          *po, *so;
  size_t        count;
  dot_file      df;
  po = calloc(1 + g->order, sizeof (int));
  so = calloc(1 + g->order, sizeof (int));
  count = 0;
  df = open_dot_graph(fname, gname);
  recdf(g, src, po, so, &count, df);
  close_dot_graph(df);
}
 
// Some code to test ...
 
size_t order = 8;
 
int mat_graph[] = {
  0, 1, 0, 0, 1, 0, 0, 1,
  0, 0, 1, 0, 0, 0, 0, 0,
  0, 1, 0, 1, 0, 0, 0, 0,
  0, 1, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 1, 0, 0,
  1, 0, 1, 0, 0, 0, 1, 1,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
};
 
int main()
{
  graph g;
 
  g = graph_from_matrix(order, mat_graph);
 
  depthfirst("tree.dot", "tree", g, 1);
 
  return 0;
}

Et pour finir un petit Makefile pour compiler tout ça.

# A Makefile
 
CC=clang
CFALGS= -Wall -Wextra -std=c99 -O2
 
SRC= depthfirst.c  graph.c  to_dot.c
OBJ= ${SRC:.c=.o}
 
all: depthfirst
 
depthfirst: ${OBJ}
	${CC}  -o depthfirst ${OBJ} ${LDFLAGS}
 
# Build png automatically ...
.SUFFIXES: .dot .png
 
.dot.png:
	dot -T png -o$@ $<
 
clean::
	rm -f *~ *.o depthfirst
 
# END

More

Si vous n'en avez pas assez, voici quelques pistes pour continuer.

Parcours largeur

Si vous souhaitez aller plus loin, l'étape suivante est le parcours largeur. Il y a deux grandes étapes:

• Fournir une implémentation complète de files (queue).
• Implémenter le parcours largeur sur le même modèle que le parcours profondeur: affichage de l'arbre couvrant au format dot.

Itérateurs

Pour uniformiser l'accès aux sommets et aux liaisons et pour séparer l'interface du graphe de son implémentation, nous pourrions fournir une notion d'itérateurs.

Pour ça, il faut s'inspirer des structures de données génériques vues en cours et pour chaque itérateurs fournir:

• une fonction d'accès (qui permet de récupérer le point de départ)
• une fonction renvoyant le dernier élément pour arrêter les boucles
• une fonction pour passer au suivant