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)