MaxCutInstance

MaxCutInstance#

class iqm.applications.maxcut.MaxCutInstance(graph, break_z2=False, allow_custom_var_names=False)[source]#

Bases: QUBOInstance

The maxcut instance class.

This class is initialized with a graph whose maxcut we try to find. A maxcut is a division of the graph nodes into two groups, such that the number of edges connecting nodes from different groups is maximized. The optional break_z2 variable indicates whether the \(\mathbb{Z}_2\) symmetry of the problem is to be broken by pre-assigning one of the nodes to one of the groups.

Parameters:

  • graph (Graph) – The Graph describing the maxcut problem.

  • break_z2 (bool) – Boolean variable indicating whether the \(\mathbb{Z}_2\) symmetry of the problem should be artificially broken, reducing the number of problem variables by 1.

  • allow_custom_var_names (bool)

Raises:

ValueError – If the input graph’s nodes aren’t labelled by integers starting from 0.

Attributes

graph

The graph of the problem.

Methods

cut_size(bit_str)

Calculates the cut size of a solution represented by a bitstring.

draw_problem([solution_bitstring, seed, ...])

The method to draw an instance of maxcut, with the solution highlighted.
property graph: Graph#

The graph of the problem.

Equals the graph that was given on initialization of MaxCutInstance and shouldn’t be modified. Instead of modifying the graph, the user should instantiate a new object of MaxCutInstance.

cut_size(bit_str)[source]#

Calculates the cut size of a solution represented by a bitstring.

The calculation simply iterates over edges of the graph and adds +1 for each edge cut according to the bitstring. Since it uses the original graph, the input bitstring needs to have the same length as the graph has nodes.

Parameters:

bit_str (str) – A string of 0’s and 1’s (or any two distinct characters) representing the division of the graph into two sets.

Returns:

The number of edges cut.

Raises:

  • ValueError – If the length of the input bitstring isn’t equal to the number of nodes of _graph.

  • ValueError – If the bitstring contains more than 2 different characters (it doesn’t have to be 0’s and 1’s).

Return type:

int

draw_problem(solution_bitstring=None, seed=None, highlight_edge_by_node_count=frozenset({1}))[source]#

The method to draw an instance of maxcut, with the solution highlighted.

Parameters:

  • solution_bitstring (str | None) – A bitstring representing a solution to the problem. Selected nodes are represented as 1’s, the other nodes are represented as 0’s. This skips nodes that have been fixed, e.g., by breaking the Z2 symmetry. The full bitstring including the fixed nodes is restored internally by calling restore_fixed_variables_bitstring().

  • seed (int | None) – The seed to derandomize the layout of the graph.

  • highlight_edge_by_node_count (frozenset[int]) – How many of the endnodes of an edge need to be highlighted to also make the edge highlighted. For maxcut, this should be frozenset({1}) so that cut edges are highlighted.

Return type:

None

Contents