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] - 2*x[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 LunaModel 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 | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> GraphPartitioningCollection` `classmethod`

Generate random graph partitioning instances.

Parameters:

Name	Type	Description	Default
`min_nodes`	`int \| None`	Minimum number of nodes (even values only).	`None`
`max_nodes`	`int \| None`	Maximum number of nodes.	`None`
`edge_prob`	`float`	Edge probability.	`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. `[10, 50, 100]`, instead of a range. Mutually exclusive with `min_nodes`/`max_nodes`, by default None.	`None`

Returns:

Type	Description
`GraphPartitioningCollection`	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: `True` where the instance was kept, `False` where it was removed.

Raises:

Type	Description
`ValueError`	If `max_runtime` is not positive.

Graph Partitioning API Reference

Data

GraphPartitioningData

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

to_string() -> str

from_graph(graph: nx.Graph) -> GraphPartitioningData staticmethod

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

generate_random(n_nodes: int = 6, edge_prob: float = 0.5, seed: int | None = None) -> GraphPartitioningData staticmethod

Formulation

GraphPartitioningFormulation

to_string(data: GraphPartitioningData) -> str staticmethod

formulate(data: GraphPartitioningData) -> Model staticmethod

interpret(solution: Solution, data: GraphPartitioningData) -> GraphPartitioningSolution staticmethod

Solution

GraphPartitioningSolution

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

to_string() -> str

Instance

GraphPartitioningInstance

Collection

GraphPartitioningCollection

from_random(min_nodes: int | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> GraphPartitioningCollection classmethod

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

`GraphPartitioningData`

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

`to_string() -> str`

`from_graph(graph: nx.Graph) -> GraphPartitioningData` `staticmethod`

`from_adjacency_matrix(adjacency_matrix: np.ndarray | list[list[float]], node_names: list[int | str]) -> GraphPartitioningData` `staticmethod`

`generate_random(n_nodes: int = 6, edge_prob: float = 0.5, seed: int | None = None) -> GraphPartitioningData` `staticmethod`

`GraphPartitioningFormulation`

`to_string(data: GraphPartitioningData) -> str` `staticmethod`

`formulate(data: GraphPartitioningData) -> Model` `staticmethod`

`interpret(solution: Solution, data: GraphPartitioningData) -> GraphPartitioningSolution` `staticmethod`

`GraphPartitioningSolution`

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

`to_string() -> str`

`GraphPartitioningInstance`

`GraphPartitioningCollection`

`from_random(min_nodes: int | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> GraphPartitioningCollection` `classmethod`

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