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 | Type | Description |
|---|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
ax
|
Axes | None
|
Matplotlib axes to draw on. Creates a new figure if |
None
|
Returns:
| Type | Description |
|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
graph
|
Graph
|
A NetworkX graph. |
required |
n_colors
|
int
|
Number of available colors. |
required |
Returns:
| Type | Description |
|---|---|
GraphColoringData
|
The graph coloring data instance. |
from_adjacency_matrix(adjacency_matrix: np.ndarray, node_names: list[int | str], n_colors: int) -> GraphColoringData
staticmethod
Create data from an adjacency matrix.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
adjacency_matrix
|
ndarray
|
Symmetric binary adjacency matrix. |
required |
node_names
|
list[int | str]
|
Node identifiers. |
required |
n_colors
|
int
|
Number of available colors. |
required |
Returns:
| Type | Description |
|---|---|
GraphColoringData
|
The graph coloring data instance. |
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:
| Name | Type | Description | Default |
|---|---|---|---|
n_nodes
|
int
|
Number of nodes. |
5
|
n_colors
|
int
|
Number of available colors. |
3
|
edge_prob
|
float
|
Probability of an edge between two nodes of different color. |
0.5
|
seed
|
int | None
|
Random seed for reproducibility. |
None
|
Returns:
| Type | Description |
|---|---|
GraphColoringData
|
A randomly generated, feasible data instance. |
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:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
GraphColoringData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
str
|
Formatted description of the formulation. |
formulate(data: GraphColoringData) -> Model
staticmethod
Formulate the graph coloring problem.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
GraphColoringData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
Model
|
A LunaModel ready to be solved. |
interpret(solution: Solution, data: GraphColoringData) -> GraphColoringSolution
staticmethod
Extract the graph coloring solution.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
solution
|
Solution
|
The solver solution. |
required |
data
|
GraphColoringData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
GraphColoringSolution
|
Structured solution with color assignments. |
Solution
Solution model for Graph Coloring use case.
GraphColoringSolution
Bases: UcSolution
Solution for the Graph Coloring use case.
Attributes:
| Name | Type | Description |
|---|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
GraphColoringData | None
|
Problem data for reconstructing the graph. Required. |
None
|
ax
|
Axes | None
|
Matplotlib axes to draw on. |
None
|
Returns:
| Type | Description |
|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
min_nodes
|
int | None
|
Minimum number of nodes. |
None
|
max_nodes
|
int | None
|
Maximum number of nodes. |
None
|
n_colors
|
int
|
Number of available colors. |
3
|
edge_prob
|
float
|
Probability of an edge between two nodes of different color. |
0.5
|
num_instances
|
int
|
Instances per size. |
1
|
seed
|
int | None
|
Random seed. |
None
|
sizes
|
Sequence[int] | None
|
Explicit sizes to generate, e.g. |
None
|
Returns:
| Type | Description |
|---|---|
GraphColoringCollection
|
Collection of generated instances. |
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:
| Name | Type | Description | Default |
|---|---|---|---|
max_runtime
|
float
|
SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds. |
3600
|
quiet
|
bool
|
Suppress the SCIP solver output. |
True
|
Returns:
| Type | Description |
|---|---|
list[bool]
|
Feasibility mask over the instances as they were before filtering,
in that order: |
Raises:
| Type | Description |
|---|---|
ValueError
|
If |