TD 11 - 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 :

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 td11.ml -o td11. 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 :

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 :

solution

retour à la page du cours