TD 12 - Coloriage de graphe

L'objectif de ce TD est d'étudier quelques idées simples concernant le coloriage de graphes, un problème directement lié à l'allocation de registres. Étant donné un graphe non orienté G, un coloriage de G est une assignation de couleurs à chacun de ses sommets de telle sorte que deux sommets reliés par une arête ne portent pas la même couleur. Si le coloriage utilise au plus k couleurs différentes, on parle de k-coloriage.

Étant donnés G et k, déterminer si G est k-coloriable est un problème NP-complet. Comme il ne serait pas raisonnable d'allouer un temps non-polynômial au problème de l'allocation de registres, on procède de la manière suivante : on tente de colorier le graphe avec k couleurs mais, en cas d'échec, on s'autorise à retirer (spill) un ou plusieurs sommets du graphe. Dans un second temps, on considérera ces sommets éliminés et on leur appliquera un second algorithme de coloration, avec cette fois une infinité de couleurs possibles.

Représentation des graphes et des coloriages

Les sommets des graphes sont représentés ici par des entiers. On se donne deux modules S et M pour des ensembles d'entiers et des dictionnaires indexés par des entiers, respectivement.

module S = Set.Make(struct type t = int let compare = Pervasives.compare end)
module M = Map.Make(struct type t = int let compare = Pervasives.compare end)

Un graphe est alors représenté par un dictionnaire associant à chaque sommet l'ensemble de ses voisins :

type graph = S.t M.t

Les graphes sont non orientés : dès lors que x est dans l'ensemble des voisins de y alors y est de même dans l'ensemble des voisins de x.

Les couleurs sont également représentées par des entiers (consécutifs). Un coloriage est un dictionnaire associant à chaque sommet d'un graphe sa couleur :

type coloring = int M.t

Coloriage avec k couleurs

Dans cette première question, on tente de k-colorier un graphe en exploitant l'idée suivante due à Chaitin : si un sommet s a moins de k voisins, alors on peut commencer par colorier le reste du graphe et on sera certain de trouver ensuite une couleur s. De plus, la suppression de s peut diminuer le degré d'autres sommets et ainsi permettre de répéter cette même idée. Lorsqu'il n'y a plus de tel sommet, on spill un sommet quelconque.

On considère ici la variante de l'algorithme de Chaitin appelée « coloriage optimiste », dont le pseudo-code est le suivant :

colorier(g)
  si g est vide
    renvoyer le coloriage vide
  s'il existe un sommet s de g de degré < k
    colorier (g \ s)
    attribuer une couleur disponible à s
  sinon
    choisir un sommet s de g arbitrairement
    colorier (g \ s)
    si une couleur reste disponible pour s, la lui attribuer
    sinon spiller s

Écrire une fonction

val color : int -> graph -> coloring

réalisant cet algorithme. Les k couleurs seront représentées par les entiers 0,1,...k-1 et les sommets spillés porteront la couleur -1.

Indications. Il pourra être utile de commencer par définir les fonctions suivantes :

une fonction renvoyant un sommet de degré inférieur à k, le cas échéant, et levant l'exception Not_found sinon. (Pour cela, on pourra par exemple parcourir l'ensemble des sommets du graphe avec M.iter et lever une exception du type exception Found of int dès qu'un sommet vérifiant la propriété a été trouvé.)
une fonction remove supprimant un sommet d'un graphe (attention : il faut alors correctement supprimer les occurrences de ce sommet comme voisin des sommets restants).
une fonction qui détermine une couleur possible pour un sommet, étant données des couleurs pour les autres sommets du graphe, et lève l'exception Not_found s'il n'y a pas de couleur possible pour ce sommet.

Tests. Du code vous est fourni pour tester. Pour l'utiliser il faut récupérer d'une part le fichier bench.ml et d'autre part l'archive tests.tar.gz qu'il convient de décompresser à l'endroit où vous travaillez (avec tar zxf tests.tar.gz). Les fichiers fournis s'utilisent ainsi :

open Bench
module B = Make(S)(M)

et on compile avec une commande de la forme ocamlopt bench.ml td12.ml -o td12. Le module B fournit une fonction

B.bench1 : int -> (int -> graph -> coloring) -> unit

qui prend en argument k et votre fonction color et la teste sur tous les fichiers contenus dans le répertoire "tests". Le résultat doit ressembler à :

coloriage avec k = 3
  tests/full-3.dot: coloriage ok / 0 spilled sur 3 / rapport = 0.00
  tests/lin-3.dot: coloriage ok / 0 spilled sur 3 / rapport = 0.00
  tests/full-4.dot: coloriage ok / 1 spilled sur 4 / rapport = 0.25
  tests/circle-4.dot: coloriage ok / 0 spilled sur 4 / rapport = 0.00
  tests/lin-4.dot: coloriage ok / 0 spilled sur 4 / rapport = 0.00
  ...
moyenne = 0.05

Pour vous permettre de débugger, le module B fournit également les fonctions suivantes :

B.parse : string -> graph : lit le graphe contenu dans un fichier de test (exemple : B.parse "tests/full-4.dot")
B.show_file : string -> unit : montre le graphe contenu dans un fichier de test ; pour B.show_file "tests/full-4.dot", l'outil gv doit s'ouvrir sur une image telle que
B.show_graph : graph -> unit : montre le graphe avec l'outil gv (utile pour tester la fonction remove, par exemple)
B.print_colors : coloring -> unit : affichage un coloriage sur la sortie standard
B.show1 : int -> (int -> graph -> coloring) -> string -> unit : étant donnés k, votre fonction color et un fichier de test, montre le graphe et son coloriage ; pour B.show1 3 color "tests/full-4.dot", le résultat doit ressembler à ceci (les sommets spillés sont dessinés en pointillés).

Coloriage avec une infinité de couleurs

On considère ici le problème légèrement différent qui consiste à colorier un graphe en supposant disposer d'une infinité de couleurs. Bien entendu, il existe une solution triviale consistant à assigner une couleur différente à chaque sommet. On souhaite cependant utiliser le moins de couleurs possibles. Là encore, le problème est NP-complet et nous allons utiliser une méthode simple, correcte mais non optimale.

L'algorithme proposé est le suivant :

spill(g)
   si g est vide
     renvoyer le coloriage vide
   sinon
     choisir arbitrairement un sommet s de g
     colorier (g \ s)
     attribuer à s la plus petite couleur non utilisée par ses voisins

Écrire une fonction

val spill : graph -> coloring

réalisant cet algorithme. Les couleurs utilisées seront représentées par des entiers consécutifs 0,1,...k-1. On pourra avantageusement réutiliser la fonction de suppression d'un sommet dans un graphe utilisée dans la question précédente.

Du code est également fourni pour tester :

B.bench2 : (graph -> coloring) -> unit prend en argument votre fonction spill la teste sur tous les fichiers contenus dans le répertoire "tests". Le résultat doit ressembler à :

coloriage avec une infinité de couleurs
  tests/full-3.dot: coloriage ok / 3 couleurs pour 3 sommets / rapport = 1.00
  tests/full-10.dot: coloriage ok / 10 couleurs pour 10 sommets / rapport = 1.00
  tests/lin-3.dot: coloriage ok / 2 couleurs pour 3 sommets / rapport = 0.67
  tests/full-4.dot: coloriage ok / 4 couleurs pour 4 sommets / rapport = 1.00
  tests/circle-4.dot: coloriage ok / 2 couleurs pour 4 sommets / rapport = 0.50
  tests/lin-4.dot: coloriage ok / 2 couleurs pour 4 sommets / rapport = 0.50
  ...
moyenne = 0.66

B.show2 : (graph -> coloring) -> string -> unit : étant donnés votre fonction spill et un fichier de test, montre le graphe et son coloriage ; pour B.show2 spill "tests/random-10-15.dot", le résultat doit ressembler à ceci

solution

retour à la page du cours