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

graph_greedy_edge_color()#

Color edges of a PyGraph object using a greedy approach.

This function works by greedily coloring the line graph of the given graph.

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.

Parameters:

  • PyGraph – The input PyGraph object to edge-color.

  • preset_color_fn – An optional callback function that is used to manually specify a color to use for particular edges in the graph. If specified this takes a callable that will be passed an edge 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 edges.

  • strategy – The greedy 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 edge indices and the value is the color

Return type:

dict

import rustworkx as rx

graph = rx.generators.cycle_graph(7)
edge_colors = rx.graph_greedy_edge_color(graph)
assert edge_colors == {0: 0, 1: 1, 2: 0, 3: 1, 4: 0, 5: 1, 6: 2}