by Matthew Henderson
Last updated: Thu Nov 21 23:10:18 GMT 2013.
This notebook introduces the vizing
Python package for colouring graphs. The main focus of vizing
is on list-colourings but total-colourings and colourings of vertices and edges without lists are also supported.
This notebook can be viewed at: http://nbviewer.ipython.org/5857920.
The source code for this notebook can be found at: https://gist.github.com/MHenderson/5857920
In Section 1, we introduce colouring the vertices of a graph when each vertex has a list of prescribed colours. In Section 2 list-edge-colouring is discussed.
import random
random.seed(0)
def standard_colours(G):
return [G.node[node]['color'] for node in G.node.keys()]
import networkx as nx
from vizing.colouring import InOrder, RandomAvailableColor, vertex_coloring
G = nx.complete_graph(4)
for node in G.node:
G.node[node]['list'] = range(4)
vertex_coloring(G, nodes = InOrder, choose_color = RandomAvailableColor)
nx.draw_circular(G, node_color = standard_colours(G))
The next example is completing a Shidoku puzzle.
A = { 0: [1,2,3,4,5,8,12],
1: [2,3,4,5,9,13],
2: [3,6,7,10,14],
3: [6,7,11,15],
4: [5,6,7,8,12],
5: [6,7,9,13],
6: [7,10,14],
7: [11,15],
8: [9,10,11,12,13],
9: [10,11,12,13],
10: [11,14,15],
11: [15],
12: [13,14,15],
13: [14,15],
14: [15] }
G = nx.from_dict_of_lists(A)
L = { 0: [1],
1: [2],
2: [3],
3: [4],
4: [3],
5: [4],
6: [1],
7: [2],
8: [2, 4],
9: [1],
10: [4],
11: [3],
12: [3, 4],
13: [3],
14: [2],
15: [1, 4]}
for node in G.node:
G.node[node]['list'] = L[node]
vertex_coloring(G, nodes = InOrder, choose_color = RandomAvailableColor)
nx.draw_circular(G, node_color = standard_colours(G))