compas-dev / compas

Core packages of the COMPAS framework.
https://compas.dev/compas/
MIT License
316 stars 109 forks source link

Non-optimal result from the vertex colouring algorithm #104

Open robin-oval opened 6 years ago

robin-oval commented 6 years ago

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 commented 6 years ago

can you propose a greedy version?

tomvanmele commented 4 years ago

@robin-oval ping :)

jf--- commented 7 months ago

@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 commented 7 months ago

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--- commented 7 months ago

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 commented 7 months ago

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--- commented 7 months ago

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