TD 9 - Coloração de grafos

O objectivo desta Prática Laboratorial é estudar algumas ideias simples em torno da coloração de grafos, um dos conceitos ligados à alocação de registos. Dado um grafo não orientado G, uma coloração de G é uma atribuição de uma cor a cada um dos seus vértices de tal forma que dois vértices ligados por uma aresta nunca são da mesma cor. Se a coloração utiliza no máximo k cores diferentes, fala-se de k-coloração.

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.

Representação dos grafos e das colorações

Os vértices são representados aqui por inteiros. Damo-nos dois módulos S e M para representar conjuntos de inteiros e dicionários indexados por inteiros, respectivamente.
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.t
Os 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

Coloração com k cores

Tentamos aqui a k-coloração de um grafo explorando a ideia seguinte (apontada originalmente por Chaitin) : se um vértice s tem menos de k vizinhos, então podemos começar por colorir o resto do grafo e estaremos seguro de encontrar uma cor para s. Mais, a remoção de s pode diminuir o grau de outros vértices e assim permitir repetir esta mesma ideia. Quando não há mais tais vértices, procedemos ao spill de um vértice qualquer.

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 s
Escrever uma função
val color : int -> graph -> coloring
que 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) -> unit
que 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.05
Para permitir-vos a depuração, o módulo B fornece igualmente as funções seguintes :

Coloração com uma infinidade de cores

Consideramos aqui o problema ligeiramente diferente que consiste em colorir um grafo supondo que se dispõe de uma infinidade de cores. Claro, existe uma solução trivial que consiste em atribuir uma cor diferente a cada vértice. Desejamos no entanto utilizar o número mínimo de cores. Ainda aqui, o problema é NP-completo. Por isso vamos utilizar um método simples, correcto mas não ótimo.

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 vizinhos
Escrever uma função
val spill : graph -> coloring
que 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 :

solução

voltar à pagina da UC