Voir la source de 2014:02:17:Graphes

[[category:EPITA:TP:20132014]]

== 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 <tt>0</tt> correspondra donc au sommet <tt>1</tt>.''

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.

<source lang="C">
/* 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
</source>

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:'''

<source lang="C">
/* 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 !
}
</source>

Détails auquels il faut faire attention:
* le graphe est orienté, dans la fonction <tt>add_link</tt> il faut bien penser à ajouter un élément dans la liste des successeurs de <tt>src</tt> '''et''' dans la liste des prédécesseurs de <tt>dst</tt>.
* chaque sommet stocke ses deux demi-degrés dans les champs <tt>ins</tt> (demi-degré intérieur) et <tt>outs</tt> (demi-degré extérieur), il faut bien les mettre à jour dans <tt>add_link</tt>.
* 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:

<source lang="C">
/* 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
</source>

… et l'implem ..

<source lang="C">
/* 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);
}
</source>

* '''Écrire la fonction <tt>graph_to_dot(fname, name, g)</tt> qui produit un fichier graphviz via les fonctions de <tt>to_dot.h</tt>'''
<source lang="C">
// To be added in graph.h and graph.c
void graph_to_dot(char *fname, char *name, graph g);
</source>

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

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

<source lang="C">
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;
}
</source>

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

<pre>
$ dot -T png graph.dot -O
$ display graph.dot.png
</pre>

== 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.

<source lang="C">
/* 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;
}
</source>

Et pour finir un petit <tt>Makefile</tt> pour compiler tout ça.

<source lang="make">
# 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
</source>

== 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