rustworkx.graph_greedy_color#

graph_greedy_color()#

Color a PyGraph object using a greedy graph coloring algorithm.

This function uses one of several greedy strategies described in: [1]. The Degree (aka largest-first) strategy colors the nodes with higher degree first. The Saturation (aka DSATUR and SLF) strategy dynamically chooses the vertex that has the largest number of different colors already assigned to its neighbors, and, in case of a tie, the vertex that has the largest number of uncolored neighbors. The IndependentSet strategy finds independent subsets of the graph and assigns a different color to each of these subsets.

Note

The coloring problem is NP-hard and this is a heuristic algorithm which may not return an optimal solution.

Parameters:

  • PyGraph – The input PyGraph object to color.

  • preset_color_fn – An optional callback function that is used to manually specify a color to use for particular nodes in the graph. If specified this takes a callable that will be passed a node index and is expected to either return an integer representing a color or None to indicate there is no preset. Note if you do use a callable there is no validation that the preset values are valid colors. You can generate an invalid coloring if you the specified function returned invalid colors for any nodes.

  • strategy – The strategy used by the algorithm. When the strategy is not explicitly specified, the Degree strategy is used by default.

Returns:

A dictionary where keys are node indices and the value is the color

Return type:

dict

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.generalized_petersen_graph(5, 2)
coloring = rx.graph_greedy_color(graph)
colors = [coloring[node] for node in graph.node_indices()]

# Draw colored graph
layout = rx.shell_layout(graph, nlist=[[0, 1, 2, 3, 4],[6, 7, 8, 9, 5]])
mpl_draw(graph, node_color=colors, pos=layout)
../_images/rustworkx.graph_greedy_color_0_0.png