In this project, we wish to estimate the number of $J$-colorings of a given graph of size $K$. For this, we will define a graph using the networkx
package. Then, we will write an algorithm that verifies if a coloring is valid. Finally, we will estimate the number of colorings using a Monte-Carlo method.
We start with some useful imports:
# For mybinder, uncomment
# !pip install numpy matplotlib ipywidgets networkx
import numpy as np
import matplotlib.pyplot as plt
% matplotlib inline
% matplotlib notebook
import networkx as nx
import ipywidgets as widgets
Defining a graph can be extremely simple, as networkx
has a large list of graph generators. We will use as example the Petersen graph.
G = nx.petersen_graph()
plt.figure()
nx.draw(G)
G.nodes()
G.edges()
We will denote a coloring using a dict of integers, where each integer corresponds to a color, such that d[i] = j
means node $i$ is colored with color $j$.
def random_coloring(graph,n_colors):
coloring = {}
for node in graph.nodes():
coloring[node] = np.random.randint(0,n_colors)
return coloring
some_coloring = random_coloring(G,5)
some_coloring
We can draw the coloring
def draw_coloring(G,coloring,colors):
fig = plt.figure()
n_colors = len(colors)
pos = nx.spring_layout(G)
for i in range(n_colors):
nx.draw_networkx_nodes(G,pos,[x for x in G.nodes() if coloring[x]==i],width=8,node_color=colors[i])
nx.draw_networkx_edges(G,pos,width=1.0,alpha=0.5)
plt.axis('off')
plt.show()
return fig
some_colors = ['red','blue','green','yellow','purple']
fig2 = draw_coloring(G,some_coloring,some_colors)
To verify if a graph is correctly colored is to verify if each edge connects nodes with different colors. We see that the coloring provided above does not work.
def valid_coloring(graph,coloring):
return not any([coloring[x]==coloring[y] for (x,y) in graph.edges()])
valid_coloring(G,some_coloring)
If the above says 'True', you are lucky! Try with some other random colorings to see if the result changes.
def mc_number_colorings(graph,n_colors,M=1000):
results = []
for j in range(M):
coloring = random_coloring(graph,n_colors)
results += [1.*valid_coloring(graph,coloring)]
count = np.cumsum(results)/np.arange(1,M+1)*(len(graph.nodes())**n_colors)
return count
estimate = mc_number_colorings(G,10,M=int(1e3))
estimate[-1]
def start_plot(estimate,maxM):
to_plot = estimate[:maxM]
lim = np.max(to_plot)
fig = plt.figure()
plt.xlim((0,maxM))
plt.ylim((0,lim))
plt.plot([],[],label='Estimation')
plt.legend(loc='upper right')
plt.title('MC estimated number of graph colorings')
plt.show()
return fig
fig3 = start_plot(estimate,1000)
def update_plot(estimate,M,figure):
to_plot = estimate[:M]
plt.figure(figure.number)
l, = figure.axes[0].lines
l.set_xdata(np.arange(1,M+1))
l.set_ydata(to_plot)
def update_length(value):
update_plot(estimate=estimate,M=value['new'],figure = fig3)
slider = widgets.IntSlider(min=0,max=1000,step=1,value=0)
slider.observe(update_length,names='value')
display(slider)