WeightedMaxCutInstance

class iqm.applications.maxcut.WeightedMaxCutInstance(graph, break_z2=False)

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.

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.

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)

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