Graph colouring
A Graph is a collection of nodes
(or vertices), connected by edges (or not).
Nodes directly connected by edges are called neighbours.
In our representation of graphs, nodes are numbered and edges are represented by the two node numbers connected by the edge separated by a dash. Edges define the nodes being connected. Only unconnected nodes need a separate description.
For example,
0-1 1-2 2-0 3
Describes the following graph. Note that node 3 has no neighbours
- Example graph
+---+ | 3 | +---+ +-------------------+ | | +---+ +---+ +---+ | 0 | --- | 1 | --- | 2 | +---+ +---+ +---+
A useful internal datastructure for a graph and for later graph algorithms is as a mapping between each node and the set/list of its neighbours.
In the above example:
0 maps-to 1 and 2 1 maps to 2 and 0 2 maps-to 1 and 0 3 maps-to <nothing>
- Graph colouring task
Colour the vertices of a given graph so that no edge is between verticies of the same colour.
- Integers may be used to denote different colours.
- Algorithm should do better than just assigning each vertex a separate colour. The idea is to minimise the number of colours used.
- Show for each edge, the colours assigned on each vertex.
- Show the total number of nodes, edges, and colours used for each graph.
- Use the following graphs
- Ex1
0-1 1-2 2-0 3
+---+ | 3 | +---+ +-------------------+ | | +---+ +---+ +---+ | 0 | --- | 1 | --- | 2 | +---+ +---+ +---+
- Ex2
The wp articles left-side graph
1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7
+----------------------------------+
| |
| +---+ |
| +-----------------| 3 | ------+----+
| | +---+ | |
| | | | |
| | | | |
| | | | |
| +---+ +---+ +---+ +---+ |
| | 8 | --- | 1 | --- | 6 | --- | 4 | |
| +---+ +---+ +---+ +---+ |
| | | | |
| | | | |
| | | | |
| | +---+ +---+ +---+ |
+----+------ | 7 | --- | 2 | --- | 5 | -+
| +---+ +---+ +---+
| |
+-------------------+
- Ex3
The wp articles right-side graph which is the same graph as Ex2, but with different node orderings and namings.
1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6
+----------------------------------+
| |
| +---+ |
| +-----------------| 5 | ------+----+
| | +---+ | |
| | | | |
| | | | |
| | | | |
| +---+ +---+ +---+ +---+ |
| | 8 | --- | 1 | --- | 4 | --- | 7 | |
| +---+ +---+ +---+ +---+ |
| | | | |
| | | | |
| | | | |
| | +---+ +---+ +---+ |
+----+------ | 6 | --- | 3 | --- | 2 | -+
| +---+ +---+ +---+
| |
+-------------------+
- Ex4
This is the same graph, node naming, and edge order as Ex2 except some of the edges x-y are flipped to y-x. This might alter the node order used in the greedy algorithm leading to differing numbers of colours.
1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7
+-------------------------------------------------+
| |
| |
+-------------------+---------+ |
| | | |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
| 4 | --- | 5 | --- | 2 | --- | 7 | --- | 1 | --- | 6 | --- | 3 | --- | 8 |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
| | | | | |
+---------+-----------------------------+---------+ | |
| | | |
| | | |
+-----------------------------+-------------------+ |
| |
| |
+-----------------------------+
Perl 6
<lang perl6>#!/usr/bin/env perl6
sub GraphNodeColor(@RAW) {
my %OneMany = my %NodeColor = ();
for @RAW { %OneMany{$_[0]}.push: $_[1] ; %OneMany{$_[1]}.push: $_[0] }
my @ColorPool = "0", "1" … %OneMany.elems-2; # as string
my %NodePool = %OneMany.keys.SetHash;
if %OneMany<Nil>:exists { # skip islanders for now
%NodePool{$_}:delete for @(%OneMany<Nil>);
%NodePool<Nil>:delete;
}
while %NodePool.keys.Bool {
my $color = @ColorPool.grab;
my %TempPool = %NodePool;
while (my \n = %TempPool.keys.pick) {
%NodeColor{n} = $color;
%TempPool{n}:delete;
%TempPool{$_}:delete for @(%OneMany{n}) ; # skip neighbors as well
%NodePool{n}:delete;
}
}
if %OneMany<Nil>:exists { # islanders use an existing color
%NodeColor{$_} = %NodeColor.values.pick for @(%OneMany<Nil>);
}
return %NodeColor
}
my \DATA = [
[<0 1>,<1 2>,<2 0>,<3 Nil>,<Nil 4>,<5 Nil>], [<1 6>,<1 7>,<1 8>,<2 5>,<2 7>,<2 8>,<3 5>,<3 6>,<3 8>,<4 5>,<4 6>,<4 7>], [<1 4>,<1 6>,<1 8>,<3 2>,<3 6>,<3 8>,<5 2>,<5 4>,<5 8>,<7 2>,<7 4>,<7 6>], [<1 6>,<7 1>,<8 1>,<5 2>,<2 7>,<2 8>,<3 5>,<6 3>,<3 8>,<4 5>,<4 6>,<4 7>],
];
for DATA {
say "DATA : ", $_; say "Result : ", my %output = GraphNodeColor $_; say "Nodes : ", %output.keys.elems; say "Edges : ", $_.elems; say "Colors : ", %output.values.Set.elems;
}</lang>
- Output:
DATA : [(0 1) (1 2) (2 0) (3 Nil) (Nil 4) (5 Nil)]
Result : {0 => 0, 1 => 5, 2 => 2, 3 => 0, 4 => 0, 5 => 0}
Nodes : 6
Edges : 6
Colors : 3
DATA : [(1 6) (1 7) (1 8) (2 5) (2 7) (2 8) (3 5) (3 6) (3 8) (4 5) (4 6) (4 7)]
Result : {1 => 4, 2 => 4, 3 => 4, 4 => 4, 5 => 5, 6 => 5, 7 => 5, 8 => 5}
Nodes : 8
Edges : 12
Colors : 2
DATA : [(1 4) (1 6) (1 8) (3 2) (3 6) (3 8) (5 2) (5 4) (5 8) (7 2) (7 4) (7 6)]
Result : {1 => 2, 2 => 3, 3 => 2, 4 => 3, 5 => 2, 6 => 3, 7 => 2, 8 => 3}
Nodes : 8
Edges : 12
Colors : 2
DATA : [(1 6) (7 1) (8 1) (5 2) (2 7) (2 8) (3 5) (6 3) (3 8) (4 5) (4 6) (4 7)]
Result : {1 => 6, 2 => 6, 3 => 6, 4 => 6, 5 => 4, 6 => 4, 7 => 4, 8 => 4}
Nodes : 8
Edges : 12
Colors : 2
Python
<lang python>import re from collections import defaultdict from itertools import count
connection_re = r"""
(?: (?P<N1>\d+) - (?P<N2>\d+) | (?P<N>\d+) (?!\s*-)) """
class Graph:
def __init__(self, name, connections):
self.name = name
self.connections = connections
g = self.graph = defaultdict(list) # maps vertex to direct connections
matches = re.finditer(connection_re, connections,
re.MULTILINE | re.VERBOSE)
for match in matches:
n1, n2, n = match.groups()
if n:
g[n] += []
else:
g[n1].append(n2) # Each the neighbour of the other
g[n2].append(n1)
def greedy_colour(self, order=None):
"Greedy colourisation algo."
if order is None:
order = self.graph # Choose something
colour = self.colour = {}
neighbours = self.graph
for node in order:
used_neighbour_colours = (colour[nbr] for nbr in neighbours[node]
if nbr in colour)
colour[node] = first_avail_int(used_neighbour_colours)
self.pp_colours()
return colour
def pp_colours(self):
print(f"\n{self.name}")
c = self.colour
e = canonical_edges = set()
for n1, neighbours in sorted(self.graph.items()):
if neighbours:
for n2 in neighbours:
edge = tuple(sorted([n1, n2]))
if edge not in canonical_edges:
print(f" {n1}-{n2}: Colour: {c[n1]}, {c[n2]}")
canonical_edges.add(edge)
else:
print(f" {n1}: Colour: {c[n1]}")
lc = len(set(c.values()))
print(f" #Nodes: {len(c)}\n #Edges: {len(e)}\n #Colours: {lc}")
def first_avail_int(data):
"return lowest int 0... not in data"
d = set(data)
for i in count():
if i not in d:
return i
if __name__ == '__main__':
for name, connections in [
('Ex1', "0-1 1-2 2-0 3"),
('Ex2', "1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7"),
('Ex3', "1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6"),
('Ex4', "1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7"),
]:
g = Graph(name, connections)
g.greedy_colour()</lang>
- Output:
Ex1
0-1: Colour: 0, 1
0-2: Colour: 0, 2
1-2: Colour: 1, 2
3: Colour: 0
#Nodes: 4
#Edges: 3
#Colours: 3
Ex2
1-6: Colour: 0, 1
1-7: Colour: 0, 1
1-8: Colour: 0, 1
2-5: Colour: 0, 1
2-7: Colour: 0, 1
2-8: Colour: 0, 1
3-5: Colour: 0, 1
3-6: Colour: 0, 1
3-8: Colour: 0, 1
4-5: Colour: 0, 1
4-6: Colour: 0, 1
4-7: Colour: 0, 1
#Nodes: 8
#Edges: 12
#Colours: 2
Ex3
1-4: Colour: 0, 1
1-6: Colour: 0, 1
1-8: Colour: 0, 1
2-3: Colour: 1, 0
2-5: Colour: 1, 0
2-7: Colour: 1, 0
3-6: Colour: 0, 1
3-8: Colour: 0, 1
4-5: Colour: 1, 0
4-7: Colour: 1, 0
5-8: Colour: 0, 1
6-7: Colour: 1, 0
#Nodes: 8
#Edges: 12
#Colours: 2
Ex4
1-6: Colour: 0, 1
1-7: Colour: 0, 1
1-8: Colour: 0, 1
2-5: Colour: 2, 0
2-7: Colour: 2, 1
2-8: Colour: 2, 1
3-5: Colour: 2, 0
3-6: Colour: 2, 1
3-8: Colour: 2, 1
4-5: Colour: 2, 0
4-6: Colour: 2, 1
4-7: Colour: 2, 1
#Nodes: 8
#Edges: 12
#Colours: 3
Python dicts preserve insertion order and Ex2/Ex3 edges are traced in a similar way which could be the cause of exactly the same colours used for Ex2 and Ex3. The wp article must use an earlier version of Python/different ordering of edge definitions.
Ex4 changes the order of nodes enough to affect the number of colours used.