compas-dev / compas-dev/compas

Non-optimal result from the vertex colouring algorithm

Open
#104 7 comments 0 reactions 1 assignee Claimed by @tomvanmele View on GitHub
enhancement
Dominant language
Python
Stars
386
Forks
122
Avg merge
11d 46m
Merged PRs (30d)
1

Description

The algorithm for vertex colouring does not yield the minimum number of colours for the simple network in the example. The result gives three colours, though it is two-colourable. The algorithm is not greedy, using heuristics and it's normal it fails for some networks. We can consider having two algorithms: a greedy one and a heuristic one?

Reference of the current algorithm: http://scienceblogs.com/goodmath/2007/06/28/graph-coloring-algorithms-1/
____
```python
from compas.datastructures.network import Network
from compas.topology import vertex_coloring
from compas.plotters import NetworkPlotter

vertices_0 = [[2,0,0],
[-1,0,0],
[0,1,0],
[1,0,0],
[-2,0,0],
[0,-1,0],
[0,0,0],
]

edges_0 = [
[6,3],
[3,0],
[0,5],
[5,4],
[4,1],
[1,6],
[6,2],
]

graph = Network.from_vertices_and_edges(vertices_0, edges_0)
key_color = vertex_coloring(graph.adjacency)
print key_color

colors = ['#ff0000', '#0000ff', '#00ff00']

plotter = NetworkPlotter(graph, figsize=(10, 7))

plotter.draw_vertices(facecolor={key: colors[key_color[key]] for key in graph.vertices()})
plotter.draw_edges()

plotter.show()
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.