vertex_coloring

compas.topology.vertex_coloring(adjacency)[source]

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

Parameters:
adjacencydict[hashable, dict[hashable, None]] | dict[hashable, sequence[hashable]]

An adjacency dictionary representing the connectivity of the graph by mapping nodes identifiers to neighbour identifiers. Examples of valid adjacency dicts are

  • {0: [1, 2, 3, 4], 1: [0], 2: [0], 3: [0], 4: [0]}

  • {0: {1: None, 2: None, 3: None, 4: None}, 1: {0: None}, 2: {0: None}, 3: {0: None}, 4: {0: None}}

Returns:
dict[hashable, int]

A dict mapping each node of the graph to a color number.

Warning

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

Notes

This algorithms works on any data structure that can be interpreted as a graph, e.g. networks, meshes, volmeshes, etc..

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/.

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