Non-optimal result from the vertex colouring algorithm

[robin-oval]

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/

---

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()

[tomvanmele]

can you propose a greedy version?

[tomvanmele]

@robin-oval ping :)

[jf---]

@tomvanmele pong, this is addressed in the (stale but cool) cgal_skeleton, right? since the author didn't ping back, and since another implementation exists, closing seems reasonable?

[tomvanmele]

unfortunately not yet resolved. compas_singular had something like this but is in a completely unusable state. will keep this to remind myself that i need to do something about that...

[jf---]

cgal_skeleton & cgal_singular are quite impressive but possible beyond maintaining. that is to say: I think they're very valuable but possible its more productive to integrate (some) those contributions into compas, in the core lib. I'm going on a hunch here

[tomvanmele]

some features will indeed be absorbed in other packages, or even the core library, but it is unfortunately not high on my todo list. also i want to make sure to do this (politically) correctly since it involves re-coding the work of some of our students...

btw, you keep referring to those packages as cgal_skeleton and cgal_singular. are we sure we are talking about the same thing?

[jf---]

Understandable, and yes I think so, I'm pretty sure I've seen this problem implemented either one of those packages authored by @robin-oval. But absolutely it's key to have the authors perspective.

Let me get back to this issue and be more specific which would be the relevant aspects that perhaps could land into compas core.

I'm a huge fan of computational geometry, medial axises, Conway operators and the topological operators that @robin-oval implemented. Terrific PhD thesis @robin-oval