Graph Partitioning API Reference
Data
Data model for Graph Partitioning use case.
GraphPartitioningData
Bases: UcData
Data for the Graph Partitioning use case.
The graph partitioning problem divides nodes into two equal-sized groups while minimizing the number (or weight) of edges crossing between them.
Attributes:
| Name | Type | Description |
|---|---|---|
name |
Literal['graph_partitioning']
|
Identifier for this data type. |
adjacency_matrix |
NumPyArray
|
Symmetric weighted adjacency matrix. |
node_names |
list[int | str]
|
Node identifiers. |
plot(*, ax: Axes | None = None) -> Axes
Plot the graph instance.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
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 data.
from_graph(graph: nx.Graph) -> GraphPartitioningData
staticmethod
Create data from a NetworkX graph.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
graph
|
Graph
|
A NetworkX graph with optional edge weights. |
required |
Returns:
| Type | Description |
|---|---|
GraphPartitioningData
|
The graph partitioning data instance. |
from_adjacency_matrix(adjacency_matrix: np.ndarray | list[list[float]], node_names: list[int | str]) -> GraphPartitioningData
staticmethod
Create data from an adjacency matrix.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
adjacency_matrix
|
ndarray | list[list[float]]
|
Symmetric weighted adjacency matrix. |
required |
node_names
|
list[int | str]
|
Node identifiers. |
required |
Returns:
| Type | Description |
|---|---|
GraphPartitioningData
|
The graph partitioning data instance. |
generate_random(n_nodes: int = 6, edge_prob: float = 0.5, seed: int | None = None) -> GraphPartitioningData
staticmethod
Generate a random graph partitioning instance.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
n_nodes
|
int
|
Number of nodes (should be even for equal partition). |
6
|
edge_prob
|
float
|
Probability of an edge between any two nodes. |
0.5
|
seed
|
int | None
|
Random seed for reproducibility. |
None
|
Returns:
| Type | Description |
|---|---|
GraphPartitioningData
|
A randomly generated data instance. |
Formulation
Formulation for Graph Partitioning use case.
GraphPartitioningFormulation
Bases: UcFormulation[GraphPartitioningData, GraphPartitioningSolution]
Constraint-based formulation for Graph Partitioning.
Mathematical Formulation
Decision Variables: x[i] in {0,1} — 1 if node i in partition 1, else partition 0
Objective: Minimize sum_{(i,j) in edges} w_ij * (x[i] + x[j] - 2x[i]x[j]) (edges crossing between partitions)
Constraints: 1. Equal partition: sum_i x[i] == n // 2
to_string(data: GraphPartitioningData) -> str
staticmethod
Format the formulation as a string.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
GraphPartitioningData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
str
|
Formatted description of the formulation. |
formulate(data: GraphPartitioningData) -> Model
staticmethod
Formulate the graph partitioning problem.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
GraphPartitioningData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
Model
|
A Luna Model ready to be solved. |
interpret(solution: Solution, data: GraphPartitioningData) -> GraphPartitioningSolution
staticmethod
Extract the graph partitioning solution.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
solution
|
Solution
|
The solver solution. |
required |
data
|
GraphPartitioningData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
GraphPartitioningSolution
|
Structured solution with partition assignments. |
Solution
Solution model for Graph Partitioning use case.
GraphPartitioningSolution
Bases: UcSolution
Solution for the Graph Partitioning use case.
Attributes:
| Name | Type | Description |
|---|---|---|
name |
Literal['graph_partitioning']
|
Identifier for this solution type. |
partitions |
list[list[int | str]]
|
Two partitions of node names. |
cut_edges |
int
|
Number of edges crossing between partitions. |
cut_weight |
float
|
Total weight of edges crossing between partitions. |
is_valid |
bool
|
Whether partitions are of equal size. |
plot(data: GraphPartitioningData | None = None, *, ax: Axes | None = None) -> Axes
Plot the graph partitioning solution.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
GraphPartitioningData | None
|
Problem data. 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 GraphPartitioning use case.
GraphPartitioningInstance
Bases: UcInstance[GraphPartitioningData, GraphPartitioningFormulation, GraphPartitioningSolution]
Instance combining data and formulation for Graph Partitioning.
Collection
Collection of Graph Partitioning instances.
GraphPartitioningCollection
Bases: UcInstanceCollection[GraphPartitioningInstance]
Collection of Graph Partitioning instances.
from_random(min_nodes: int, max_nodes: int, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> GraphPartitioningCollection
classmethod
Generate random graph partitioning instances.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
min_nodes
|
int
|
Minimum number of nodes (even values only). |
required |
max_nodes
|
int
|
Maximum number of nodes. |
required |
edge_prob
|
float
|
Edge probability. |
0.5
|
num_instances
|
int
|
Instances per size. |
1
|
seed
|
int | None
|
Random seed. |
None
|
Returns:
| Type | Description |
|---|---|
GraphPartitioningCollection
|
Collection of generated instances. |