Skip to content

Graph Coloring API Reference

Data

Data model for Graph Coloring use case.

GraphColoringData

Bases: UcData

Data for the Graph Coloring use case.

The graph coloring problem assigns colors to vertices of a graph such that no two adjacent vertices share the same color.

Attributes:

  • name (Literal['graph_coloring']) –

    Identifier for this data type.

  • adjacency_matrix (BinAdjMatrix) –

    Symmetric binary adjacency matrix of the graph.

  • node_names (list[int | str]) –

    Node identifiers corresponding to rows/columns of the adjacency matrix.

  • n_colors (int) –

    Number of available colors.

plot(*, ax: Axes | None = None) -> Axes

Plot the graph instance.

Parameters:

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Return a string representation of the data.

from_graph(graph: nx.Graph, n_colors: int) -> GraphColoringData staticmethod

Create data from a NetworkX graph.

Parameters:

  • graph (Graph) –

    A NetworkX graph.

  • n_colors (int) –

    Number of available colors.

Returns:

from_adjacency_matrix(adjacency_matrix: np.ndarray, node_names: list[int | str], n_colors: int) -> GraphColoringData staticmethod

Create data from an adjacency matrix.

Parameters:

  • adjacency_matrix (ndarray) –

    Symmetric binary adjacency matrix.

  • node_names (list[int | str]) –

    Node identifiers.

  • n_colors (int) –

    Number of available colors.

Returns:

generate_random(n_nodes: int = 5, n_colors: int = 3, edge_prob: float = 0.5, seed: int | None = None) -> GraphColoringData staticmethod

Generate a random graph coloring instance.

Parameters:

  • n_nodes (int, default: 5 ) –

    Number of nodes.

  • n_colors (int, default: 3 ) –

    Number of available colors.

  • edge_prob (float, default: 0.5 ) –

    Probability of an edge between any two nodes.

  • seed (int | None, default: None ) –

    Random seed for reproducibility.

Returns:

Formulation

Formulation for Graph Coloring use case.

GraphColoringFormulation

Bases: UcFormulation[GraphColoringData, GraphColoringSolution]

Constraint-based formulation for Graph Coloring.

Mathematical Formulation

Symbols: n — number of nodes k — number of available colors E — set of edges in the graph

Decision Variables: x[i,c] in {0,1} — 1 if node i is assigned color c, 0 otherwise for i = 0, ..., n-1 and c = 0, ..., k-1

Objective: Minimize 0 (feasibility problem)

Constraints: - Each node exactly one color: sum_c x[i,c] == 1 for each node i - Adjacent nodes different colors: x[i,c] + x[j,c] <= 1 for each edge (i,j) in E, each color c

to_string(data: GraphColoringData) -> str staticmethod

Format the formulation as a string.

Parameters:

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: GraphColoringData) -> Model staticmethod

Formulate the graph coloring problem.

Parameters:

Returns:

  • Model –

    A Luna Model ready to be solved.

interpret(solution: Solution, data: GraphColoringData) -> GraphColoringSolution staticmethod

Extract the graph coloring solution.

Parameters:

  • solution (Solution) –

    The solver solution.

  • data (GraphColoringData) –

    The problem data.

Returns:

Solution

Solution model for Graph Coloring use case.

GraphColoringSolution

Bases: UcSolution

Solution for the Graph Coloring use case.

Attributes:

  • name (Literal['graph_coloring']) –

    Identifier for this solution type.

  • color_assignment (dict[int | str, int]) –

    Mapping from node to assigned color index.

  • n_colors_used (int) –

    Number of distinct colors used in the solution.

  • is_valid (bool) –

    Whether no two adjacent nodes share the same color.

plot(data: GraphColoringData | None = None, *, ax: Axes | None = None) -> Axes

Plot the graph coloring solution.

Parameters:

  • data (GraphColoringData | None, default: None ) –

    Problem data for reconstructing the graph. Required.

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Return a string representation of the solution.

Instance

Instance model for GraphColoring use case.

GraphColoringInstance

Bases: UcInstance[GraphColoringData, GraphColoringFormulation, GraphColoringSolution]

Instance combining data and formulation for Graph Coloring.

Collection

Collection of Graph Coloring instances.

GraphColoringCollection

Bases: UcInstanceCollection[GraphColoringInstance]

Collection of Graph Coloring instances.

from_random(min_nodes: int, max_nodes: int, n_colors: int = 3, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> GraphColoringCollection classmethod

Generate random graph coloring instances.

Parameters:

  • min_nodes (int) –

    Minimum number of nodes.

  • max_nodes (int) –

    Maximum number of nodes.

  • n_colors (int, default: 3 ) –

    Number of available colors.

  • edge_prob (float, default: 0.5 ) –

    Edge probability.

  • num_instances (int, default: 1 ) –

    Instances per size.

  • seed (int | None, default: None ) –

    Random seed.

Returns: