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	Type	Description
`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:

Name	Type	Description	Default
`ax`	`Axes \| None`	Matplotlib axes to draw on. Creates a new figure if `None`.	`None`

Returns:

Type	Description
`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:

Name	Type	Description	Default
`graph`	`Graph`	A NetworkX graph with optional edge weights.	required

Returns:

Type	Description
`MaxcutData`	The MaxCut data instance.

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

Name	Type	Description	Default
`adjacency_matrix`	`ndarray`	The weighted adjacency matrix of the graph.	required
`node_names`	`list[str \| int]`	List of node identifiers.	required
`node_position`	`dict[str, tuple[float, float]] \| None`	Optional positions for visualization.	`None`

Returns:

Type	Description
`MaxcutData`	The MaxCut data instance.

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:

Name	Type	Description	Default
`data`	`MaxcutData`	The MaxCut problem data.	required

Returns:

Type	Description
`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:

Name	Type	Description	Default
`data`	`MaxcutData`	The MaxCut problem data containing the graph structure.	required

Returns:

Type	Description
`Model`	The quantum optimization model.

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

Interpret the quantum solution.

Parameters:

Name	Type	Description	Default
`solution`	`Solution`	The quantum solution object.	required
`data`	`MaxcutData`	The original MaxCut problem data.	required

Returns:

Type	Description
`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	Type	Description
`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:

Name	Type	Description	Default
`data`	`MaxcutData \| None`	Problem data used to reconstruct the graph. Required -- a `ValueError` is raised when `None`.	`None`
`ax`	`Axes \| None`	Matplotlib axes to draw on. Creates a new figure if `None`.	`None`

Returns:

Type	Description
`Axes`	The axes with the plot.

Raises:

Type	Description
`ValueError`	If data is `None`.

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

Name	Type	Description	Default
`min_num_nodes`	`int`	Minimum number of nodes per instance.	required
`max_num_nodes`	`int`	Maximum number of nodes per instance.	required
`min_density`	`float`	Minimum edge probability (graph density), by default 0.3. Must be between 0 and 1.	`0.3`
`max_density`	`float`	Maximum edge probability (graph density), by default 0.7. Must be between 0 and 1.	`0.7`
`num_instances`	`int`	Number of instances to generate for each node count, by default 1.	`1`
`weighted`	`bool`	Whether to add random weights to edges, by default True. If False, all edges have weight 1.	`True`
`min_weight`	`float`	Minimum edge weight, by default 1.0.	`1.0`
`max_weight`	`float`	Maximum edge weight, by default 10.0.	`10.0`
`seed`	`int \| None`	Random seed for reproducible results, by default None.	`None`

Returns:

Type	Description
`MaxcutCollection`	Collection containing generated MaxCut instances.

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:

Name	Type	Description	Default
`min_num_nodes`	`int`	Minimum number of nodes per instance.	required
`max_num_nodes`	`int`	Maximum number of nodes per instance.	required
`degree`	`int`	Degree of each node (must be less than num_nodes).	required
`num_instances`	`int`	Number of instances to generate for each node count, by default 1.	`1`
`weighted`	`bool`	Whether to add random weights to edges, by default True.	`True`
`min_weight`	`float`	Minimum edge weight, by default 1.0.	`1.0`
`max_weight`	`float`	Maximum edge weight, by default 10.0.	`10.0`
`seed`	`int \| None`	Random seed for reproducible results, by default None.	`None`

Returns:

Type	Description
`MaxcutCollection`	Collection containing generated MaxCut instances.

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:

Name	Type	Description	Default
`min_num_nodes`	`int`	Minimum number of nodes per instance.	required
`max_num_nodes`	`int`	Maximum number of nodes per instance.	required
`weighted`	`bool`	Whether to add random weights to edges, by default True.	`True`
`min_weight`	`float`	Minimum edge weight, by default 1.0.	`1.0`
`max_weight`	`float`	Maximum edge weight, by default 10.0.	`10.0`
`seed`	`int \| None`	Random seed for reproducible results, by default None.	`None`

Returns:

Type	Description
`MaxcutCollection`	Collection containing generated MaxCut instances.

Examples:

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

Maximum Cut Problem (MaxCut) API Reference

Data

MaxcutData

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

to_string() -> str

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

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

Formulation

MaxcutFormulation

to_string(data: MaxcutData) -> str staticmethod

formulate(data: MaxcutData) -> Model staticmethod

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

Solution

MaxcutSolution

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

to_string() -> str

Instance

MaxcutInstance

Collection

MaxcutCollection

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

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

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

`MaxcutData`

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

`to_string() -> str`

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

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

`MaxcutFormulation`

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

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

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

`MaxcutSolution`

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

`to_string() -> str`

`MaxcutInstance`

`MaxcutCollection`

`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`

`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`

`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`