Numero Cromatico de um grafo

[mundo]

Boa noite, estou a tentar resolver um exercicio cujo enunciado é:

"O objectivo deste programa é determinar o número cromático de um grafo, ou seja, o menor número de cores necessário para colorir um grafo de tal forma que nodos adjacentes tenham cores distintas. Irá receber uma lista de pares de nodos que são adjacentes entre si e deverá imprimir o número cromático do grafo."

Como exemplo de input temos:

portugal espanha

espanha franca

franca alemanha

alemanha belgica

belgica franca

usa canada

usa mexico

marrocos argelia

argelia libia

argelia mali

e o output deveria ser 2 para este caso.

Eu fiz o seguinte código:

import sys

# Funcao para preencher o grafo
def arestaAB(grafo, origem, destino):
   if origem in grafo:
       grafo[origem].append(destino)
   else:
       grafo[origem] = [destino]

   if destino in grafo:
       grafo[destino].append(origem)
   else:
       grafo[destino] = [origem]


#Funcao que verifica se ha uma solucao, e vai preenchendo o sol com a solucao
def find(sol, i, k):

   #so ha um vertice por isso existe solucao
   if i == k:
       return True
   # caso contrario e necessario verificar o resto
   else:

       #para o numero de vertices vamos verificar se existe solucao
       for j in range(1,k):

           #adicionamos a solucao a lista
           sol[i] = j

           #continuamos de forma recursiva
           if find(sol, i+1, k):
               return True

   #Chegamos aqui nao ha solucao
   return False


grafo = {}

for line in sys.stdin:
   a,b = line.split()
   arestaAB(grafo,a,b)

#print grafo

sol = []
cores = len(grafo.keys())

for i in range(cores):
   if find(sol,i,cores) == True:
       print i

Isto está a dar IndexError na linha

sol[i] = j 

e não estou a perceber porquê, se alguém poder ajudar agradeço.

Cumprimentos

Edited May 22, 2014 at 06:52 PM by mundo

[Pedro C.]

É importante meteres o erro aqui para conseguirmos perceber melhor o que está a acontecer.

No teu caso em particular diria que é um erro de indexação. Como o "sol" está vazio (sol=[]) quando tentas aceder a uma posição (que não existe) ele dá problemas.

[charlie_v]

devias inciiar a lista de sol [ ] com o tamanho de 'k' assim já não terias problemas de indexação. podes também alterar a linha 'sol = j' para sol.append(j) mas ao fazeres isto vais aumentar o tamanho final da lista porque enquanto 'i' estiver em range de 'cores' o teu algoritmo vai sempre adicionar elementos a lista (se bem percebi o código)

[mundo]

Mesmo assim não sei porquê, não me está a dar o resultado correcto