Skip to content

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 (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:

  • 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 data.

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

Create data from a NetworkX graph.

Parameters:

  • graph (Graph) –

    A NetworkX graph with optional edge weights.

Returns:

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

Create data from an adjacency matrix.

Parameters:

  • adjacency_matrix (ndarray | list[list[float]]) –

    Symmetric weighted adjacency matrix.

  • node_names (list[int | str]) –

    Node identifiers.

Returns:

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

Generate a random graph partitioning instance.

Parameters:

  • n_nodes (int, default: 6 ) –

    Number of nodes (should be even for equal partition).

  • edge_prob (float, default: 0.5 ) –

    Probability of an edge between any two nodes.

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

    Random seed for reproducibility.

Returns:

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:

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: GraphPartitioningData) -> Model staticmethod

Formulate the graph partitioning problem.

Parameters:

Returns:

  • Model –

    A LunaModel ready to be solved.

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

Extract the graph partitioning solution.

Parameters:

Returns:

Solution

Solution model for Graph Partitioning use case.

GraphPartitioningSolution

Bases: UcSolution

Solution for the Graph Partitioning use case.

Attributes:

  • 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:

  • data (GraphPartitioningData | None, default: None ) –

    Problem data. 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 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:

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

    Minimum number of nodes (even values only).

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

    Maximum number of nodes.

  • edge_prob (float, default: 0.5 ) –

    Edge probability.

  • 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: