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 :

  • uma função que retorna um vértice de grau inferior a k quando possível, ou que levanta a excepção Not_found caso contrário. (Para isso, poderemos por exemplo percorrer o conjunto dos vértices do grafo com M.iter e levantar uma excepção do tipo exception Found of int mal se encontra um vértice que verifica esta propriedade.)
  • uma função remove removendo um vértice dum grafo (cuidado : é igualmente necessário remover as ocorrências deste vértice no conjunto dos vizinhos dos vértices restantes).
  • uma função que determina uma cor possível para um vértice, dadas as cores para os outros vértices do grafo, e que levanta a excepção Not_found caso não haja cores possíveis para este vértice.

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 :
  • B.parse : string -> graph : lê o grafo contido num ficheiro de teste (exemplo : B.parse "tests/full-4.dot")
  • B.show_file : string -> unit : mostra o grafo contido num ficheiro de test ; para B.show_file "tests/full-4.dot", a ferramenta gv que permite a visualização deste tipo de ficheiros deverá apresentar uma imagem deste tipo
  • B.show_graph : graph -> unit : mostra o grafo com a ferramenta gv (útil para testar a função remove, por exemplo)
  • B.print_colors : coloring -> unit : mostra uma coloração sobre a saída standard
  • B.show1 : int -> (int -> graph -> coloring) -> string -> unit : dados k, a função color e um ficheiro de teste, mostra o grafo e a sua ; para B.show1 3 color "tests/full-4.dot", o resultado deve assemelhar-se a
    (os vértices spilled estão desenhados com pontilhado).

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 :

  • B.bench2 : (graph -> coloring) -> unit toma em argumento a função spill por desenvolver e teste-a sobre todas os ficheiros contidos na pasta "tests". O resultado deve ser algo como :
    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
    
  • B.show2 : (graph -> coloring) -> string -> unit : dados a função spill e um ficheiro de teste, mostra o grafo e a sua coloração ; para B.show2 spill "tests/random-10-15.dot", o resultado deve ser algo como
solução

voltar à pagina da UC



Para este TD

Lembre-se de ter uma instalação funcional do OCaml (≥ 4.02.3) com Menhir.

Considere usar o opam !