vertex_coloring

compas.topology.vertex_coloring(adjacency)

Color the vertices of a network such that no two colors are adjacent.

Parameters

network (compas.datastructures.Network) – The network object.

Notes

For more info, see 1.

References

1

Chu-Carroll, M. Graph Coloring Algorithms. Available at: http://scienceblogs.com/goodmath/2007/06/28/graph-coloring-algorithms-1/.

Warning

This is a greedy algorithm, so it might be slow for large networks.

Examples

>>> import compas
>>> from compas.datastructures import Network
>>> network = Network.from_obj(compas.get('lines.obj'))
>>> key_color = vertex_coloring(network.adjacency)
>>> key = network.get_any_node()
>>> color = key_color[key]
>>> any(key_color[nbr] == color for nbr in network.neighbors(key))
False