46 lines
1.6 KiB
Text
46 lines
1.6 KiB
Text
F first_avail_int(data)
|
||
‘return lowest int 0... not in data’
|
||
V d = Set(data)
|
||
L(i) 0..
|
||
I i !C d
|
||
R i
|
||
|
||
F greedy_colour(name, connections)
|
||
DefaultDict[Int, [Int]] graph
|
||
|
||
L(connection) connections.split(‘ ’)
|
||
I ‘-’ C connection
|
||
V (n1, n2) = connection.split(‘-’).map(Int)
|
||
graph[n1].append(n2)
|
||
graph[n2].append(n1)
|
||
E
|
||
graph[Int(connection)] = [Int]()
|
||
|
||
// Greedy colourisation algo
|
||
V order = sorted(graph.keys())
|
||
[Int = Int] colour
|
||
V neighbours = graph
|
||
L(node) order
|
||
V used_neighbour_colours = neighbours[node].filter(nbr -> nbr C @colour).map(nbr -> @colour[nbr])
|
||
colour[node] = first_avail_int(used_neighbour_colours)
|
||
|
||
print("\n"name)
|
||
V canonical_edges = Set[(Int, Int)]()
|
||
L(n1, neighbours) sorted(graph.items())
|
||
I !neighbours.empty
|
||
L(n2) neighbours
|
||
V edge = tuple_sorted((n1, n2))
|
||
I edge !C canonical_edges
|
||
print(‘ #.-#.: Colour: #., #.’.format(n1, n2, colour[n1], colour[n2]))
|
||
canonical_edges.add(edge)
|
||
E
|
||
print(‘ #.: Colour: #.’.format(n1, colour[n1]))
|
||
V lc = Set(colour.values()).len
|
||
print(" #Nodes: #.\n #Edges: #.\n #Colours: #.".format(colour.len, canonical_edges.len, lc))
|
||
|
||
L(name, connections) [
|
||
(‘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’)]
|
||
greedy_colour(name, connections)
|