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

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: GraphPartitioningData) -> Model staticmethod

Formulate the graph partitioning problem.

Parameters:

Returns:

  • Model –

    A Luna Model 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, max_nodes: int, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> GraphPartitioningCollection classmethod

Generate random graph partitioning instances.

Parameters:

  • min_nodes (int) –

    Minimum number of nodes (even values only).

  • max_nodes (int) –

    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.

Returns: