rustworkx.graph_greedy_color#

graph_greedy_color(graph, /, preset_color_fn=None)#

Color a PyGraph object using a greedy graph coloring algorithm.

This function uses a largest-first strategy as described in [1] and colors the nodes with higher degree first.

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.

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