iqm.applications.maxcut

This module contains the maxcut problem instance class and related functions.

Contains the iterator function maxcut_generator() which yields random instances of MaxCutInstance, useful for applications such as calculating the Q-score. Also contains two classical solvers for maxcut problems:

• A simple and fast greedy algorithm.

• A solver based on the standard Goemans-Williamson [1], fast and with a performance guarantee.

Example

from iqm.applications.maxcut import MaxCutInstance
from iqm.applications.maxcut import maxcut_generator
from iqm.applications.maxcut import goemans_williamson
from iqm.applications.maxcut import greedy_maxcut

for my_instance in maxcut_generator(graph_size, n_instances):  # Generates problem instances.
    gw_solution = goemans_williamson(my_instance)  # Solution bitstring obtained from GW.
    greedy_solution = greedy_maxcut(my_instance)  # Solution bitstring obtained from greedy.
    my_instance.cut_size(gw_solution)  # Check the GW solution cut size.

my_maxcut_instance = MaxCutInstance(my_graph)  # Problem instance from a graph.

Functions

goemans_williamson(max_cut_problem)	Runs the Goemans-Williamson algorithm for maxcut, returning a solution bitstring.
greedy_max_cut(max_cut_problem)	Standard greedy algorithm for maxcut problem class.
maxcut_generator(n, n_instances, *[, ...])	The generator function for generating random maxcut problem instances.

Classes

MaxCutInstance(graph[, break_z2])	The maxcut instance class.
WeightedMaxCutInstance(graph[, break_z2])	The weighted maxcut instance class.

Inheritance