20131209:TP:OCaml:Graphs:Foncteurs

Introduction

Notre objectif est de construire un parcours largeur de graphe indépendant de la représentation des graphes, à l'aide de foncteur.

Graphes

Pour commencer nous écrire un module de représentation des graphes avec les opérations qui nous seront nécessaires pour la suite.

Voici l'interface du module:

(* Generic Graph Interface *)
 
(* Abstract type for vertices *)
type vertex
 
(* Graph type *)
type t
 
(* make order : build a Graph with order vertices *)
val make : int -> t
 
(* order g : returns the number of vertices in g *)
val order : t -> int
 
(* get_vertex g id : retrieve vertex *)
val get_vertex : t -> int -> vertex
 
(* get_id v : returns vertex id *)
val get_id : vertex -> int
 
(* add_edge g src dst cost : add an edge (src -> dst) with cost *)
val add_edge : t -> int -> int -> float -> unit
 
(* iter_successor g f v : apply function f on all successor of v *)
val iter_successor : t -> (vertex -> float -> unit) -> vertex -> unit
 
(* iter_predecessor g f v : apply function f on all predecessor of v *)
val iter_predecessor : t -> (vertex -> float -> unit) -> vertex -> unit

En théorie vous pouvez construire n'importe quelle représentation, mais celle-ci devrait être simple et efficace:

type vertex = {
  id    : int;
  mutable succ  : (int * float) list;
  mutable pred  : (int * float) list;
}
 
type t = {
  order         : int;
  vertices      : vertex array;
}

C'est une représentation classique: un tableau de sommets où chaque sommet contient sa liste de successeurs (avec le coût associé) et sa liste de prédécesseurs. Les graphes sont orientés et n'ont pas de liaisons multiples (1-graphes.)

Attention: les sommets vont être numéroté de 1 à order et nos tableaux commencent à 0, il faut tricher un peu, voici une implémentation de la fonction get_vertex:

let get_vertex g id = g.vertices.(id - 1)

• Implémenter l'ensemble des opérations du module Graph

Parcours largeur

Le parcours largeur est un classique pour les graphes et les arbres. On va maintenant en faire une implémentation générique en utilisant uniquement les opérations abstraites sur le graphe.

Voici la base du foncteur:

module type GraphType =
sig
(* Abstract type for vertices *)
  type vertex
 
(* Graph type *)
  type t
 
(* make order : build a Graph with order vertices *)
  val make : int -> t
 
(* order g : returns the number of vertices in g *)
val order : t -> int
 
(* get_vertex g id : retrieve vertex *)
  val get_vertex : t -> int -> vertex
 
(* get_id v : returns vertex id *)
val get_id : vertex -> int
 
(* add_edge g src dst cost : add an edge (src -> dst) with cost *)
  val add_edge : t -> int -> int -> float -> unit
 
(* iter_successor g f v : apply function f on all successor of v *)
  val iter_successor : t -> (vertex -> float -> unit) -> vertex -> unit
 
(* iter_predecessor g f v : apply function f on all predecessor of v *)
  val iter_predecessor : t -> (vertex -> float -> unit) -> vertex -> unit
end
 
module Make (G : GraphType) =
struct
  open G
 
  (* Perform a simple breadth first traversal of g from src *)
  (* Builds and return a parent vector *)
  let traverse g src = (* FIX ME *)
end

La fonction traverse du foncteur va accomplir un parcours largeur classique (à l'aide d'une file.) Il s'agit d'un parcours simple (on ne recommence pas sur les sommets non atteints) depuis un sommet donné.

Le parcours va construire et retourner un vecteur de pères (à la case i on trouvera le père du sommet i dans le parcours.) La racine du parcours aura pour père -1. Le vecteur de pères pourra servir de vecteur de marques.

• Écrire la fonction traverse

Tests

Enfin, pour tester tout ça, je vous fourni un loader de graphes. Le format en entrée est dérivé du format Graphviz (dot), les fichiers sont compatibles avec les commandes de génération de graphe de Graphviz (dot, fdp, twopi, circo, neato, sfdp) et contiennent les informations qui nous intéressent.

Voici un exemple:

digraph {
  order = 9;
  1 -> 2 [cost = 1.];
  1 -> 3 [cost = 1.];
  1 -> 4 [cost = 1.];
  2 -> 5 [cost = 1.];
  3 -> 6 [cost = 1.];
  4 -> 5 [cost = 1.];
  5 -> 7 [cost = 1.];
  5 -> 8 [cost = 1.];
  6 -> 8 [cost = 1.];
  6 -> 9 [cost = 1.];
  7 -> 9 [cost = 1.];
  8 -> 9 [cost = 1.];
  8 -> 3 [cost = 1.];
  9 -> 1 [cost = 1.];
}

Attention, le parser n'est pas très évolué, vous devez respecter la syntaxe scrupuleusement (notamment, les coûts sont des floats à la OCaml.)

Le loader se présente sous la forme d'un foncteur prenant en paramètre le module de graphe, voici son code: media:graph_builder.ml

Le foncteur s'appelle: Graph_builder.Builder

Pour compiler ce bout de code, vous aurez besoin de passer par camlp4, mais comme je suis gentil, je vous fourni un fichier _tags pour compiler avec ocamlbuild:

"graph_builder.ml": camlp4of

Il vous reste à faire un programme principal utilisant les foncteurs (loader et algo) avec votre module Graph, vous pourrez ensuite lire un graphe avec la fonction load file (venant du foncteur) dont le type est:

(* G is the graph module *)
val load: string -> G.t

• Implémenter le programme principal, en instanciant les deux foncteurs. Votre programme chargera un graphe, effectuera un parcours largeur depuis l'un des sommets et affichera sous une forme ou une autre le vecteur de pères construit pendant le parcours.

Pour aller plus loin ?

Si vous avez le temps et que vous voulez approfondir (pour réviser pour le partiel par exemple) vous pouvez:

• Implémenter un module de graphe en représentation statique (avec toutes les opérations définies dans graph.mli)
• Implémenter un parcours profondeur sur le même principe.
• Générer un fichier dot à partir du vecteur de pères (pour afficher l'arbre couvrant.)
• …