Note

This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.

rustworkx.graph_greedy_color#

graph_greedy_color(graph, /)#

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