coloreado de grafos

coloradito.py

# ejemplo coloreado de grafos con networkx
# gabriel sanchez

import networkx as nx
import matplotlib.pyplot as plt
import itertools

G = nx.Graph()

colores_dict = {0:'pink', 1: 'blue', 2: 'green', 3:'red', 4:'orange', 5:'yellow'}
colores = []

G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_node(4)

G.add_edge(1,2)
G.add_edge(2,3)
G.add_edge(1,3)
G.add_edge(3,4)
G.add_edge(1,4)

def coloreado_voraz(grafo):
    colores = {}
    nodos = grafo.nodes()
    for u in nodos:
        colores_vecinos = {colores[v] for v in grafo[u] if v in colores}
        for color in itertools.count():
            if color not in colores_vecinos:
                break
        colores[u] = color
    return colores

coloreado = coloreado_voraz(G)

for i,j in coloreado.items():
    colores.append(colores_dict[coloreado[i]])
nx.draw(G,node_color = colores,with_labels = True)

plt.show()