Dados G e k, determinar se G é k-colorável é um problema NP-completo. Como não é razoável processar em tempo não-polinomial o problema da alocação de registos, procedemos da forma seguinte : tentamos colorir o grafo com k cores mas, em caso de falhanço, autorizamo-nos retirar (spill) um ou mais vértices do grafo. Num segundo momento, consideraremos estes vértices eliminados, e utilizaremos um segundo algoritmo de coloração, desta vez com a possibilidade de utilização de um número qualquer de cores.
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)Um grafo é então representado por um dicionário associando a cada vértice o conjunto dos seus vizinhos :
type graph = S.t M.tOs grafos não são orientados : de cada vez que x está no conjuntos dos vizinhos de y, y está também no conjunto dos vizinhos de x.
As cores são igualmente representados por inteiros (consecutivos). Uma coloração é um dicionário que associa a cada vértice de um grafo a sua cor :
type coloring = int M.t
Consideramos aqui a variante do algoritmo de Chaitin designada de « coloração otimista », cujo pseudo-código é o seguinte :
colorir(g) se g é vazio retornar a coloração vazia se existe um vértice s de g de grau < k colorir (g \ s) atribuir uma cor disponível a s senão escolher um vértice s de g arbitrariamente colorir (g \ s) se uma cor está disponível para s, atribuir-lhe esta cor senão spill de sEscrever uma função
val color : int -> graph -> coloringque realiza este algoritmo. As k cores serão representadas pelos inteiros 0,1,...k-1 e os vértices spilled terão a cor -1.
Dicas. Poderá ser útil começar por definir as funções seguintes :
Testes. algum código é-vos fornecido para testar. Para utilizá-lo é necessário utilizar o ficheiro bench.ml e o arquivo tests.tar.gz (que convém ser descomprimido na pasta de trabalho, com tar zxf tests.tar.gz). Os ficheiros fornecidos utilizam-se da seguinte forma :
open Bench module B = Make(S)(M)e compilamos com um comando da forma ocamlopt bench.ml td12.ml -o td12. O módulo B fornece uma função
B.bench1 : int -> (int -> graph -> coloring) -> unitque toma em argumento k e a função color requerida anteriormente e testa-a com todos os ficheiros contidos no directório "tests". o resultado deve ser algo de semelhante a :
coloração com k = 3 tests/full-3.dot: coloração ok / 0 spilled para 3 / relação = 0.00 tests/lin-3.dot: coloração ok / 0 spilled para 3 / relação = 0.00 tests/full-4.dot: coloração ok / 1 spilled para 4 / relação = 0.25 tests/circle-4.dot: coloração ok / 0 spilled para 4 / relação = 0.00 tests/lin-4.dot: coloração ok / 0 spilled para 4 / relação = 0.00 ... média = 0.05Para permitir-vos a depuração, o módulo B fornece igualmente as funções seguintes :
O algoritmo proposto é o seguinte :
spill(g) se g está vazio retornar a coloração vazia senão escolher arbitrariamente um vértice s de g colorir (g \ s) atribuir a s a menor cor não utilizada pelos seus vizinhosEscrever uma função
val spill : graph -> coloringque implementa este algoritmo. as cores utilizadas deverão ser representadas por inteiros consecutivos 0,1,...k-1. Poderemos tirar novamente vantagem da função de remoção de um vértice no grafo utilizada na questão anterior.
É vos fornecido igualmente código de teste :
coloração avec une infinité de couleurs tests/full-3.dot: coloração ok / 3 cores para 3 vértices / relação = 1.00 tests/full-10.dot: coloração ok / 10 cores para 10 vértices / relação = 1.00 tests/lin-3.dot: coloração ok / 2 cores para 3 vértices / relação = 0.67 tests/full-4.dot: coloração ok / 4 cores para 4 vértices / relação = 1.00 tests/circle-4.dot: coloração ok / 2 cores para 4 vértices / relação = 0.50 tests/lin-4.dot: coloração ok / 2 cores para 4 vértices / relação = 0.50 ... média = 0.66