Skip to content

Maximum Cut Problem (MaxCut) API Reference

Data

Data model for Maxcut use case.

MaxcutData

Bases: UcData

Data for the Maximum Cut (MaxCut) use case.

This class encapsulates all necessary information to define and solve a MaxCut instance. The MaxCut problem is a classic combinatorial optimization problem where the goal is to partition the vertices of a graph into two sets such that the total weight of edges between the two sets is maximized.

The MaxCut problem is NP-hard and has applications in statistical physics, circuit design, clustering, and network analysis.

Attributes:

  • name (Literal['maxcut']) –

    A constant identifier for this data type, always set to "maxcut". Used for registration and type identification in the use case registry.

  • node_names (list[str | int]) –

    A list of node identifiers (strings or integers) representing all nodes in the graph. The order in this list corresponds to rows/columns in the adjacency_matrix. Example: ["A", "B", "C", "D"] or [0, 1, 2, 3]

  • adjacency_matrix (AdjMatrix) –

    A 2D NumPy array representing the weighted adjacency matrix of the graph. The element at [i, j] represents the weight of the edge between node i and node j. For undirected graphs, this matrix is symmetric. Shape must be (n_nodes, n_nodes) where n_nodes = len(node_names). Diagonal elements should be 0 (no self-loops).

  • node_position ((dict[str, tuple[float, float]] | None, optional)) –

    Optional dictionary mapping each node identifier to its (x, y) coordinates in 2D space. Useful for:

    • Visualizing the graph instance and its solution
    • Spatial analysis of the partition
    • Plotting the cut

    If None, positions are not available for visualization. Example: {"A": (0.0, 0.0), "B": (1.0, 0.0), "C": (0.5, 0.87)}

Examples:

Create a simple 4-node MaxCut instance:

>>> maxcut = MaxcutData(
...     name="maxcut",
...     node_names=["A", "B", "C", "D"],
...     adjacency_matrix=np.array([[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 0]]),
...     node_position={"A": (0, 0), "B": (1, 0), "C": (1, 1), "D": (0, 1)},
... )

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

Plot the MaxCut graph instance.

Draws nodes and weighted edges using NetworkX. Node positions are taken from node_position when available, otherwise computed via nx.spring_layout.

Parameters:

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Print the data.

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

Create MaxcutData from a NetworkX graph.

Parameters:

  • graph (Graph) –

    A NetworkX graph with optional edge weights.

Returns:

from_adjacency_matrix(adjacency_matrix: np.ndarray, node_names: list[int | str], node_position: dict[str, tuple[float, float]] | None = None) -> MaxcutData staticmethod

Create MaxcutData from an adjacency matrix.

Parameters:

  • adjacency_matrix (ndarray) –

    The weighted adjacency matrix of the graph.

  • node_names (list[str | int]) –

    List of node identifiers.

  • node_position (dict[str, tuple[float, float]] | None, default: None ) –

    Optional positions for visualization.

Returns:

Formulation

Formulation for Maxcut use case.

MaxcutFormulation

Bases: UcFormulation[MaxcutData, MaxcutSolution]

Formulation for the Maximum Cut (MaxCut) use case.

This formulation creates a QUBO (Quadratic Unconstrained Binary Optimization) model for the MaxCut problem. Each node is assigned a binary variable (0 or 1) representing which partition it belongs to.

The objective is to maximize the total weight of edges between the two partitions.

to_string(data: MaxcutData) -> str staticmethod

Format the formulation as a string.

Parameters:

Returns:

  • str –

    Formatted description of the MaxCut formulation.

formulate(data: MaxcutData) -> Model staticmethod

Formulate the MaxCut problem as a quantum optimization model.

The MaxCut problem is formulated as a QUBO where we want to maximize: sum_{i<j} w_{ij} * (x_i + x_j - 2x_ix_j)

This equals the sum of edge weights where endpoints are in different partitions.

Parameters:

  • data (MaxcutData) –

    The MaxCut problem data containing the graph structure.

Returns:

  • Model –

    The quantum optimization model.

interpret(solution: Solution, data: MaxcutData) -> MaxcutSolution staticmethod

Interpret the quantum solution.

Parameters:

  • solution (Solution) –

    The quantum solution object.

  • data (MaxcutData) –

    The original MaxCut problem data.

Returns:

  • MaxcutSolution –

    The interpreted MaxCut solution with partition and cut value.

Solution

Solution model for Maxcut use case.

MaxcutSolution

Bases: UcSolution

Solution for the Maximum Cut (MaxCut) use case.

This class represents a solution to the MaxCut problem, which partitions the nodes of a graph into two sets to maximize the total weight of edges between the two sets.

Attributes:

  • name (Literal['maxcut']) –

    A constant identifier for this solution type, always set to "maxcut".

  • partition (dict[str | int, int]) –

    A dictionary mapping each node to its partition (0 or 1). Nodes in partition 0 are in one set, nodes in partition 1 are in the other. Example: {"A": 0, "B": 1, "C": 0, "D": 1} means nodes A and C are in one set, while B and D are in the other.

  • cut_value (float) –

    The total weight of edges crossing between the two partitions. This is the objective value that was maximized.

  • is_valid (bool) –

    Whether the solution is valid (all nodes are assigned to a partition).

Examples:

>>> solution = MaxcutSolution(
...     name="maxcut",
...     partition={"A": 0, "B": 1, "C": 0, "D": 1},
...     cut_value=5.0,
...     is_valid=True,
... )

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

Plot the MaxCut solution on the problem graph.

Nodes are colored by partition assignment and edges are colored to distinguish cut edges from non-cut edges.

Parameters:

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

    Problem data used to reconstruct the graph. Required -- a ValueError is raised when None.

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

Raises:

to_string() -> str

Print the solution.

Instance

Instance model for Maxcut use case.

MaxcutInstance

Bases: UcInstance[MaxcutData, MaxcutFormulation, MaxcutSolution]

Instance combining data and formulation for Maxcut.

Collection

Collection of Maxcut instances.

MaxcutCollection

Bases: UcInstanceCollection[MaxcutInstance]

Collection of MaxCut instances generated from random graphs.

This collection provides methods to generate random graph instances for the MaxCut problem using various NetworkX graph models.

from_random_erdos_renyi(min_num_nodes: int, max_num_nodes: int, min_density: float = 0.3, max_density: float = 0.7, num_instances: int = 1, *, weighted: bool = True, min_weight: float = 1.0, max_weight: float = 10.0, seed: int | None = None) -> MaxcutCollection classmethod

Generate MaxCut instances using Erdős-Rényi random graphs.

The Erdős-Rényi model creates a graph by connecting each pair of nodes with a probability (density). This is one of the most common random graph models.

Parameters:

  • min_num_nodes (int) –

    Minimum number of nodes per instance.

  • max_num_nodes (int) –

    Maximum number of nodes per instance.

  • min_density (float, default: 0.3 ) –

    Minimum edge probability (graph density), by default 0.3. Must be between 0 and 1.

  • max_density (float, default: 0.7 ) –

    Maximum edge probability (graph density), by default 0.7. Must be between 0 and 1.

  • num_instances (int, default: 1 ) –

    Number of instances to generate for each node count, by default 1.

  • weighted (bool, default: True ) –

    Whether to add random weights to edges, by default True. If False, all edges have weight 1.

  • min_weight (float, default: 1.0 ) –

    Minimum edge weight, by default 1.0.

  • max_weight (float, default: 10.0 ) –

    Maximum edge weight, by default 10.0.

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

    Random seed for reproducible results, by default None.

Returns:

Examples:

>>> collection = MaxcutCollection.from_random_erdos_renyi(
...     min_num_nodes=5,
...     max_num_nodes=10,
...     min_density=0.3,
...     max_density=0.7,
...     num_instances=3,
...     seed=42,
... )

from_random_regular(min_num_nodes: int, max_num_nodes: int, degree: int, num_instances: int = 1, *, weighted: bool = True, min_weight: float = 1.0, max_weight: float = 10.0, seed: int | None = None) -> MaxcutCollection classmethod

Generate MaxCut instances using random regular graphs.

A random regular graph is a graph where every node has exactly the same degree (number of connections). This creates more structured instances compared to Erdős-Rényi graphs.

Parameters:

  • min_num_nodes (int) –

    Minimum number of nodes per instance.

  • max_num_nodes (int) –

    Maximum number of nodes per instance.

  • degree (int) –

    Degree of each node (must be less than num_nodes).

  • num_instances (int, default: 1 ) –

    Number of instances to generate for each node count, by default 1.

  • weighted (bool, default: True ) –

    Whether to add random weights to edges, by default True.

  • min_weight (float, default: 1.0 ) –

    Minimum edge weight, by default 1.0.

  • max_weight (float, default: 10.0 ) –

    Maximum edge weight, by default 10.0.

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

    Random seed for reproducible results, by default None.

Returns:

Notes

For a regular graph to exist, n * degree must be even and degree < n.

Examples:

>>> collection = MaxcutCollection.from_random_regular(
...     min_num_nodes=6,
...     max_num_nodes=10,
...     degree=3,
...     num_instances=2,
...     seed=42,
... )

from_complete_graph(min_num_nodes: int, max_num_nodes: int, *, weighted: bool = True, min_weight: float = 1.0, max_weight: float = 10.0, seed: int | None = None) -> MaxcutCollection classmethod

Generate MaxCut instances using complete graphs.

A complete graph has an edge between every pair of nodes. These are the densest possible graphs and provide challenging MaxCut instances.

Parameters:

  • min_num_nodes (int) –

    Minimum number of nodes per instance.

  • max_num_nodes (int) –

    Maximum number of nodes per instance.

  • weighted (bool, default: True ) –

    Whether to add random weights to edges, by default True.

  • min_weight (float, default: 1.0 ) –

    Minimum edge weight, by default 1.0.

  • max_weight (float, default: 10.0 ) –

    Maximum edge weight, by default 10.0.

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

    Random seed for reproducible results, by default None.

Returns:

Examples:

>>> collection = MaxcutCollection.from_complete_graph(
...     min_num_nodes=4,
...     max_num_nodes=8,
...     weighted=True,
...     seed=42,
... )