WeightedMaxCutInstance

WeightedMaxCutInstance#

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

Bases: QUBOInstance

The weighted maxcut instance class.

The weighted maxcut problem is very similar to the standard maxcut, with the only difference being that the edges of the graph now have weights. Each cut edge contributes its weight to the quality of the cut.

Parameters:

  • graph (Graph) – The Graph describing the weighted maxcut problem. Each edge of the graph needs to have an attribute called weight storing a number.

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

  • ValueError – If the input graph’s edges don’t all have an attribute weight.

  • TypeError – If the weight of any node is a wrong data type (neither float nor int).

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 weighted maxcut, with the solution highlighted.
property graph: Graph#

The graph of the problem.

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

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 the weight of 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 weight 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:

float

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

The method to draw an instance of weighted 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 weighted maxcut, this should be frozenset({1}) so that cut edges are highlighted.

Return type:

None

Contents