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, always feasible graph coloring instance.

A color is drawn for every node first, and an edge is only considered between nodes of two different colors. That planted coloring is a valid one, so the generated instance is guaranteed to be colorable with n_colors colors.

Because only differently colored pairs are eligible, edge_prob yields an effective edge density of edge_prob * (1 - 1 / n_colors). With n_colors=1 all nodes share a color and the graph has no edges.

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 two nodes of different color.

  • 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 LunaModel 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 | None = None, max_nodes: int | None = None, n_colors: int = 3, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> GraphColoringCollection classmethod

Generate random graph coloring instances.

Every generated instance is colorable with n_colors colors, see :meth:GraphColoringData.generate_random.

Parameters:

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

    Minimum number of nodes.

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

    Maximum number of nodes.

  • n_colors (int, default: 3 ) –

    Number of available colors.

  • edge_prob (float, default: 0.5 ) –

    Probability of an edge between two nodes of different color.

  • num_instances (int, default: 1 ) –

    Instances per size.

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

    Random seed.

  • sizes (Sequence[int] | None, default: None ) –

    Explicit sizes to generate, e.g. [10, 50, 100], instead of a range. Mutually exclusive with min_nodes/max_nodes, by default None.

Returns:

filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]

Drop the instances of this collection that have no feasible solution.

Every instance is formulated and handed to SCIP, which stops as soon as it finds the first feasible solution. An instance is removed from the collection when SCIP proves the model infeasible, when no solution turns up within max_runtime, or when formulating it fails altogether. This keeps randomly generated instances from breaking a downstream pipeline.

Parameters:

  • max_runtime (float, default: 3600 ) –

    SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.

  • quiet (bool, default: True ) –

    Suppress the SCIP solver output.

Returns:

  • list[bool] –

    Feasibility mask over the instances as they were before filtering, in that order: True where the instance was kept, False where it was removed.

Raises: