Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como resolver o problema conhecido como M-Coloring usando backtracking?

+1 voto
87 visitas

2 Respostas

+2 votos
respondida Jul 7 por JoaoMaria (71 pontos)  
import os
import networkx as nx
import matplotlib.pyplot as plt

cores = ["red", "blue", "green", "yellow", "black", "gray"]

estados={}

def verificaCor(estado, cor, Grafo):
    for vizinho in Grafo.neighbors(estado):
        corVizinho = Grafo.node[vizinho]['cor']
        if corVizinho == cor:
            return False
    return True


def pegaCor(estado, Grafo):
    for cor in cores:
        if verificaCor(estado, cor, Grafo):
            return cor

def le_dados(arq):
    return [[x for x in line.split()] for line in arq]

if __name__ == "__main__":
    nome_arq = input('Entre com o nome do arquivo de dados =>')
    if nome_arq=='':
        nome_arq = "mcolor.txt"
    forma=input("Forma do grafo: 1 - Espectral 2 - Concha =>")
    arq = open(nome_arq, "r")
    dados = le_dados(arq.readlines())
    nEstados=int(dados[0][0])
    for i in range(1,nEstados+1):
        num=len(dados[i])
        fronteira=[]
        for x in range(1,num):
            fronteira.append(dados[i][x])
        estados[dados[i][0]]=fronteira

    Grafo = nx.Graph()

    for estado in estados:
        Grafo.add_node(estado,{'cor':' '})
        for f in range(0,len(estados[estado])):
            Grafo.add_edge(estado,estados[estado][f])

    for estado in Grafo.node:
        Grafo.node[estado]['cor']=pegaCor(estado, Grafo)

    cores=[]
    for estado in Grafo.node:
        cores.append(Grafo.node[estado]['cor'])

    if forma=='1':
        nx.draw_spectral(Grafo, node_color=cores)
        aux= nx.spectral_layout(Grafo)
    else:
        nx.draw_shell(Grafo, node_color=cores)
        aux= nx.shell_layout(Grafo)

    nnode=0
    labels = {}
    pos={}
    for estado in Grafo.node:
        labels[nnode]=estado
        pos[nnode]=aux[estado]
        pos[nnode][1]=pos[nnode][1]+0.05
        nnode+=1

    nx.draw_networkx_labels(Grafo, pos,labels)
    plt.show()
+1 voto
respondida Jul 7 por João Gabriel Souza (76 pontos)  
editado Jul 7 por João Gabriel Souza

Introdução

O problema conhecido como M - Coloring Problem consiste em determinar um grafo não direcional que pode ser colorido com até \(m\) cores em que não possa existir dois vértices adjacentes no grafo que possuam cores iguais.

A figura abaixo ajuda a esclarecer o problema.
A imagem será apresentada aqui.
Fonte: Geeks for geeks

Percebe-se pela figura que nenhum nó adjacente possui cores iguais.

Backtracking

É um tipo de estratégia que representa um refinamento do método de Força Bruta. Essa estratégia aborda problemas cuja solução depende de uma sequência de escolhas em que cada escolha te leva adiante em algum caminho possível. Se você faz uma sequência de escolhas corretas, essa sequência te levará a solução desejada. Em caso contrário, essa estratégia te permite retornar ao momento onde a escolha errada foi tomada e você pode retomar o problema a partir daí.

M - Graphing Coloring Problem

O problema do graph coloring é o seguinte: Dado uma constante inteira positiva \(K\) e um grafo \(G\), pergunta-se: Pode-se os vértices de \(G\) serem apropriadamente coloridos nas \(k\) cores possíveis?

O algoritmo backtraking começa colorindo o vértice \(1\) com a cor de índice \(1\). Em geral, se os vértices \(1, 2, \dots, L - 1\) já estiverem com cores atribuídas, o vértice \(L\) receberá a primeira cor do índice de cores, consistente com as cores que já foram designadas. Ou seja, o algoritmo irá atribuir a primeira cor do índice que não foi utilizada nos vértices vizinhos.

A sequência será a seguinte:

  1. Primeiro o algoritmo gera uma lista ou sequência de cores.
  2. Depois gera uma lista ou dicionário de vértices.
  3. Em terceiro plano atribui a primeira cor do índice de cores ao primeiro vértice.
  4. Em sequência para atribuir a cor ao próximo vértice, primeiro compara se este é vizinho ao vértice anterior. Se for o caso altera a cor do segundo vértice, caso o segundo vértice não seja vizinho ao primeiro vértice mantêm-se a primeira cor.
  5. Realiza-se este teste sucessivamente até preencher todos os vértices do grafo.
  6. Por fim o grafo estará com todos os vértices coloridos sendo que os vizinhos, que possuem ligações por arestas, não possuirão cores iguais.

A implementação em Python segue abaixo.

Primeiro importa-se a biblioteca \(networkx\) que auxilia na construção dos grafos e a biblioteca \(matplotlib.pyplot\) que nos gera as saídas dos gráficos.

import networkx as nx
import matplotlib.pyplot as plt

Como variáveis globais têm-se a lista de cores e o dicionário de estados. Cada elemento da lista de cores será atribuído a cada elemento do dicionário de estados. Observa-se também que é atribuído cada ligação, fronteiras ou vizinhanças, a cada estado neste ponto.

cores = ["red", "blue", "green", "yellow", "black", "gray"]




estados={}
estados['Alagoas'] = ['Bahia', 'Pernambuco',  'Sergipe' ]
estados['Bahia'] = ['Alagoas', 'Pernambuco', 'Piaui', 'Sergipe' ]
estados['Ceara'] = ['Piaui', 'Paraiba', 'Pernambuco','Rio Grande do Norte']
estados['Maranhao'] = ['Piaui']
estados['Paraiba'] = ['Ceara', 'Pernambuco','Rio Grande do Norte']
estados['Pernambuco'] = ['Alagoas','Bahia','Ceara', 'Paraiba']
estados['Piaui'] = ['Ceara','Maranhao', 'Bahia']
estados['Rio Grande do Norte'] = ['Ceara', 'Paraiba']
estados['Sergipe'] = ['Alagoas', 'Bahia' ]

A primeira parte do código irá verificar a cor atribuída a cada estado com sua vizinhança, caso a cor seja igual irá alterar a cor para a subsequente da lista de cores. Por exemplo, digamos que o primeiro estado a ser analisado é o estado de Alagoas, como a primeira cor da lista é vermelho o algoritmo compara todos os vizinhos de Alagoas para ver se tem algum estado com atribuição de cor vermelha. Como este é o primeiro estado então atribuí-se vermelho para Alagoas, já no próximo estado será atribuído a primeira cor da lista que é vermelho. Se este estado fizer ligação com Alagoas então sua cor será trocada para próxima cor da lista que é azul. Caso não haja nenhum estado vizinho a este segundo estado então é mantido a cor azul, caso haja algum estado vizinho com a cor azul então é atribuída a cor subsequente. O algoritmo faz isso para todos os estados do dicionário atribuindo as respectivas cores da lista. Seguindo o processo explicado acima.

def verificaCor(estado, cor, Grafo):
    for vizinho in Grafo.neighbors(estado):
        corVizinho = Grafo.node[vizinho]['cor']
        if corVizinho == cor:
            return False
    return True

Observe que a função \(verificaCor\) utiliza de funções grafos da biblioteca \(networkx\), isso é importante para se conseguir atribuir as cores aos respectivos estados e com isso, conseguir pegar essas cores e estados e colocá-los na estrutura de grafos do pacote. Esse passo é importante para geração da figura. A função seguinte faz exatamente a extração desses valores para serem atribuídos ao grafo gerado.

def pegaCor(estado, Grafo):
    for cor in cores:
        if verificaCor(estado, cor, Grafo):
            return cor

Na parte seguinte chama-se as funções para montagem do grafo pretendido. Primeiro faz-se um \(for\) para adicionar a cor e seu respectivo estado no vértice. Depois faz-se um outro \(for\) para se adicionar os links entre os vértices, seus vizinhos ou fronteiras do grafo. Por fim pega-se a cor de cada estado e guarda-se na sequência para então atribuir a cada vértice.

Após essas atribuições gera-se o grafo. Na parte final do código busca-se atribuir o \(label\) de cada estado em seus vértices. Para encontra a posição é necessário gerar um índice para cada par de estado e cor para então conseguir gerar o respectivo \(label\). Esta estrutura é necessária pois, a biblioteca \(networkx\) exige índices para gerar os \(labels\) nos grafos.

if __name__ == "__main__":

    Grafo = nx.Graph()

    for estado in estados:
#        print(estado, estados[estado])
        Grafo.add_node(estado,{'cor':' '})
        for f in range(0,len(estados[estado])):
            Grafo.add_edge(estado,estados[estado][f])
#            print (estado,estados[estado][f])
    for estado in Grafo.node:
        Grafo.node[estado]['cor']=pegaCor(estado, Grafo)
    cores=[]
    for estado in Grafo.node:
        cores.append(Grafo.node[estado]['cor'])

    nx.draw_spectral(Grafo, node_color=cores)
    aux= nx.spectral_layout(Grafo)

    """
    nx.draw_shell(Grafo, node_color=cores)
    aux= nx.shell_layout(Grafo)
    """
    nnode=0
    labels = {}
    pos={}
    for estado in Grafo.node:
        labels[nnode]=estado
        pos[nnode]=aux[estado]
        pos[nnode][3]=pos[nnode][4]+0.05
        nnode+=1
    print(labels)
    print(pos)
    nx.draw_networkx_labels(Grafo, pos,labels)
    plt.show()

O resultado para o primeiro grafo tipo espectral, que facilita a didática do exercício, segue abaixo.

A imagem será apresentada aqui.

Uma outra forma de grafo pode ser apresentado trocando a parte do código que gera grafos espectrais para a função que gera grafos em formato de concha. O código para alteração segue abaixo.

nx.draw_shell(Grafo, node_color=cores)
    aux= nx.shell_layout(Grafo)

Também é necessário trocar a posição dos \(labels\) para que fique melhor a visualização do grafo.

 pos[nnode][6]=pos[nnode][7]+0.1

O resultado desse grafo será:

A imagem será apresentada aqui.

Referências

Backtraking
Edward A. Bender. A theoretical analysis of backtracking in the graph coloring problem. Journal of Algorithms, (1985), v. 6, Issue 2.
Graph Coloring 1
M - Coloring

comentou Jul 7 por JoaoMaria (71 pontos)  
Excelente! a sacada de utilizar a própria estrutura do Grafo foi bastante eficaz.
A solução ficou bastante genérica. Testei  com outros dados (por exemplo, coloquei dados de minha família)  e funcionou!
Sugiro que coloque os dados em um arquivo livrando o código dos dados, além de pedir qual  forma do desenho  (Espectral ou em forma de concha).
comentou Jul 7 por JoaoMaria (71 pontos)  
editado Jul 7 por JoaoMaria
Segue minha sugestão de código abaixo:
comentou Jul 7 por João Gabriel Souza (76 pontos)  
Obrigado pela sugestão de código João!
O interessante é que seu código serve para qualquer estrutura de dados, diferente do meu em que os dados são pré dispostos no código.
...