Imagine que você tenha um mapa com algumas áreas delimitadas (países, estados, etc), e deseja colorir cada área com uma cor diferente das áreas vizinhas.

Para um mapa pequeno (digamos, com no máximo 7 áreas), você pode simplesmente atribuir uma cor para cada área e se dar por satisfeito. Mas para um mapa com muitas áreas, você provavelmente quer usar um número mínimo de cores: muitas cores diferentes vão deixar o mapa confuso.

Esse é um típico problema a ser resolvido com coloração de grafos, uma área da ciência da computação explorada ativamente ainda hoje. Existe uma gama de problemas que podem ser resolvidos com técnicas desse tipo — outro exemplo popular é o quebra-cabeça Sudoku.

Hoje vamos mostrar um exemplo resolvendo esse problema usando um algoritmo simples para achar a configuração de cores mínima.

Veja a representação visual do grafo para colorir um mapa dos países da América do Sul:

Ao fim desse post, você terá aprendido a gerar colorizações e imagens para grafos como esse. 🙂

Escolhendo uma representação para o grafo

Existem várias maneiras de representar grafos com diferentes relações custo-benefício por operação, você escolhe a mais apropriada dependendo do tipo de grafo e do problema que você vai resolver. As duas representações mais comuns são matriz de adjacências e lista de adjacências — as demais são geralmente variações dessas.

Para o nosso problema, vamos simplesmente usar um dicionário Python mapeando os nós adjacentes:

grafo = {
    'A': ['B', 'C'],
    'B': ['A'],
    'C': ['A'],
}

Essa representação contém um pouco de duplicação, mas é interessante porque deixa trivial obter os nós do grafo fazendo grafo.keys() e consultar os nós adjacentes de um nó com grafo[nó].

Implementando o algoritmo

Vamos usar um algoritmo de colorização de grafos simples: começamos testando uma configuração com N cores, e caso detectamos que não seja possível, tentamos com N+1. Repetimos isso até encontrarmos uma solução ou atingirmos o limite de tentativas válidas.

Veja o código:

def try_coloring(graph, num_colors):
    assert num_colors >= 0, "Invalid number of colors: %s" % num_colors
    colors = {}

    def neighbors_have_different_colors(nodes, color):
        return all(color != colors.get(n) for n in nodes)

    for node, adjacents in graph.items():

        found_color = False

        for color in range(num_colors):
            if neighbors_have_different_colors(adjacents, color):
                found_color = True
                colors[node] = color
                break

        if not found_color:
            return None

    return colors


def find_graph_colors(graph):
    for num_colors in range(1, len(graph)):
        colors = try_coloring(graph, num_colors)
        if colors:
            return colors

Temos duas funções:

try_coloring() recebe um grafo e um número de cores para tentar. Ela tenta construir uma configuração de cores para o grafo, atualizando um dicionário que mapeia as cores para cada nó. Caso encontre uma configuração de cor válida a função devolve o dicionário; caso contrário, devolve None.

find_graph_colors() recebe um grafo e simplesmente aciona a função try_coloring() com diferentes valores para o número de cores, até que encontre uma configuração válida (ou esgote as tentativas). Também devolve a configuração encontrada ou None caso não for possível.

Coloque o código acima em um arquivo graph_coloring.py, e experimente chamar a função try_coloring() usando o shell para o nosso grafo exemplo:

>>> from graph_coloring import *
>>> grafo = {
...     'A': ['B', 'C'],
...     'B': ['A'],
...     'C': ['A'],
... }
>>> try_coloring(grafo, 1)
>>> try_coloring(grafo, 2)
{'A': 0, 'C': 1, 'B': 1}

Repare como a tentativa de colorir com apenas uma cor não funciona, mas a segunda já fornece uma configuração de cores válida para o nosso pequeno grafo. A propósito, a sessão acima está suplicando para ser usada como doctest para a função try_coloring(). 😉

Bem, esse algoritmo é um pouco ingênuo e definitivamente não-otimizado, pois envolve um certo retrabalho a cada vez que tenta uma configuração de cores nova. Isso não é um problema para os grafos que vamos usar, então se preocupar com performance agora é desnecessário, mas é legal perceber onde podemos mexer caso seja necessário melhorá-lo.

Para o caso específico de mapas, existe um teorema afirmando que é sempre possível resolver esse problema usando 4 cores. Isso funciona porque os grafos que representam mapas são sempre grafos planares, isto é, podem ser representados num plano sem nenhuma aresta se cruzando — o que reduz as possibilidades de conexões entre os vértices.

Gerando uma representação visual

Uma maneira interessante de validar o nosso trabalho acima (e mais divertida do que usando testes de unidade) é gerar uma representação visual do grafo com as respectivas cores.

Para isso, vamos usar a suite open source de software para visualização de grafos Graphviz (instale no Debian/Ubuntu/Mint com sudo apt-get install graphviz; há pacotes também para Windows e Mac).

Iniciação ao uso do GraphViz

O Graphviz usa uma linguagem própria para descrever grafos chamada DOT, que você pode explorar usando a aplicação GraphViz Workspace.

Você também pode criar um arquivo.dot manualmente usando seu editor de texto favorito, e testar a saída com o comando dot. Crie um arquivo com o seguinte conteúdo que descreve nosso grafo de exemplo:

graph {
    A -- B;
    A -- C;
}

Compile uma imagem PNG com o comando dot:

dot -Tpng -o resultado.png arquivo.dot

Se você tem o ImageMagick instalado (no Debian/Ubuntu/Mint: sudo apt-get install imagemagick), pode visualizar a imagem diretamente fazendo pipe do comando dot para o comando display:

dot -Tpng arquivo.dot | display

Para gerarmos grafos coloridos, vamos gerar uma representação do grafo que lista as conexões/arestas do grafo e imprime a configuração de cores por último, semelhante ao exemplo seguinte:

graph {
    A -- B;
    A -- C;
    A [style="filled",fillcolor="#ffffb2"];
    B [style="filled",fillcolor="#fd5d3c"];
    C [style="filled",fillcolor="#41b6c4"];
}

Para uma documentação mais completa sobre como usar a ferramenta dot para desenhar grafos, veja o documento Drawing graphs with dot.

Gerando a representação DOT

Eis a nossa gloriosa função para gerar a representação do nosso grafo usando a linguagem DOT:

PALETTE = ('#8dd3c7', '#ffffb3', '#bebada', '#fb8072', '#80b1d3', '#fdb462',
           '#b3de69', '#fccde5', '#d9d9d9', '#bc80bd', '#ccebc5', '#ffed6f')


def generate_dot(graph, colors=None, palette=PALETTE):
    assert len(set(colors.values())) <= len(palette), (
        "Too few colors in the palette")

    edges = []
    for node, adjacents in graph.items():
        for n in adjacents:
            if not ((node, n) in edges or (n, node) in edges):
                edges.append((node, n))

    result = 'graph {\n'
    result += ''.join('    "{}" -- "{}";\n'.format(*e) for e in edges)

    if colors:
        style = '    "{}" [style="filled",fillcolor="{}",shape=box];\n'
        result += ''.join(style.format(node, palette[color])
                          for node, color in colors.items())
    result += '}\n'

    return result

A função recebe um grafo na representação de dicionário que combinamos no começo, um dicionário mapeando os números das cores para os nós do grafo (opcional) e uma paleta de cores (usada para obter as cores propriamente ditas, indexadas pelos números do dicionário de cores).

Nota: as cores da paleta fornecida são de uma das paletas disponíveis no site do GraphViz baseadas no fantástico trabalho da Cynthia Brewer.

Exemplo de saída da função generate_dot() para o nosso grafo de exemplo, usando uma paleta própria:

>>> from graph_coloring import *
>>> grafo = {
... 'A': ['B', 'C'],
... 'B': ['A'],
... 'C': ['A'],
... }
>>> colors = try_coloring(grafo, 2)
>>> colors
{'A': 0, 'C': 1, 'B': 1}
>>> print(generate_dot(grafo, colors, palette=['red', 'yellow']))
graph {
 "A" -- "B";
 "A" -- "C";
 "A" [style="filled",fillcolor="red",shape=box];
 "C" [style="filled",fillcolor="yellow",shape=box];
 "B" [style="filled",fillcolor="yellow",shape=box];
}

Gerando a imagem com GraphViz para essa mesma saída, obtemos a imagem:

Finalizando

Veja o exemplo completo aqui (baixar graph_coloring.py), contendo o código mostrado nesse post mais a geração do grafo do mapa da América Latina mostrado no começo do post.

Desafio: experimente rodar com Python 2 e Python 3, tem uma sutil diferença no resultado. Consegue sacar o quê e por quê? Poste nos comentários. 😉