View page source

warp.utils.graph_coloring_assign#

warp.utils.graph_coloring_assign(
edges,
node_colors,
algorithm=GraphColoringAlgorithm.MCS,
)[source]#

Assign colors to graph nodes such that no two adjacent nodes share the same color.

This function assigns colors to nodes of an undirected graph represented by its edge list. The coloring ensures that no two nodes connected by an edge have the same color, which is useful for parallel constraint solving where nodes of the same color can be processed simultaneously.

Parameters:

  • edges (array) – A 2D array of shape (edge_count, 2) containing edge pairs, where each row [i, j] represents an undirected edge between nodes i and j. Must be a CPU array with int32 dtype.

  • node_colors (array) – A 1D array of shape (node_count,) that will be filled with the computed color assignments. Must be a CPU array with int32 dtype. The array size determines the number of nodes in the graph.

  • algorithm (GraphColoringAlgorithm) – The coloring algorithm to use.

Returns:

The number of colors used in the coloring.

Return type:

int

See also

graph_coloring_balance().