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 graph coloring instance.
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 any two nodes. |
0.5
|
seed
|
int | None
|
Random seed for reproducibility. |
None
|
Returns:
| Type | Description |
|---|---|
GraphColoringData
|
A randomly generated 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 Luna Model 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, 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:
| Name | Type | Description | Default |
|---|---|---|---|
min_nodes
|
int
|
Minimum number of nodes. |
required |
max_nodes
|
int
|
Maximum number of nodes. |
required |
n_colors
|
int
|
Number of available colors. |
3
|
edge_prob
|
float
|
Edge probability. |
0.5
|
num_instances
|
int
|
Instances per size. |
1
|
seed
|
int | None
|
Random seed. |
None
|
Returns:
| Type | Description |
|---|---|
GraphColoringCollection
|
Collection of generated instances. |