graphtools: graph tools

qecsim.graphtools

This module contains a simple graph object and functions for minimum weight perfect matching with a choice of backend.

Possible matching backends are the NetworkX Python library and the Blossom V C++ library.

See also qecsim.graphtools.blossom5

class qecsim.graphtools.SimpleGraph

Extension of dict with add_edge() method that prevents duplicate reversed edges as keys.

add_edge(node_a, node_b, weight)

Add item (node_a, node_b): weight and remove the reversed key if it exists.

qecsim.graphtools.mwpm(graph)

Minimum weight perfect matching over a graph.

Notes:

  • Attempts to use Blossom V C++ library but, if unavailable, falls back to NetworkX Python library.

  • Behaviour is undefined if the graph contains the same edge in reverse order.

Parameters

graph (dict of (object, object) edges to float or int weights.) – Graph of weighted edges between nodes, as {(a_node, b_node): weight, …}.

Returns

Matching between nodes as (a_node, b_node).

Return type

set of (object, object)

qecsim.graphtools.mwpm_blossom5(graph)

Minimum weight perfect matching over a graph (using Blossom V C++ library).

Notes:

  • Behaviour is undefined if the graph contains the same edge in reverse order.

Parameters

graph (dict of (object, object) edges to float or int weights.) – Graph of weighted edges between nodes, as {(a_node, b_node): weight, …}.

Returns

Matching between nodes as (a_node, b_node).

Return type

set of (object, object)

Raises

OSError – if Blossom V library cannot be loaded.

qecsim.graphtools.mwpm_networkx(graph)

Minimum weight perfect matching over a graph (using NetworkX Python library).

Notes:

  • Behaviour is undefined if the graph contains the same edge in reverse order.

Parameters

graph (dict of (object, object) edges to float or int weights.) – Graph of weighted edges between nodes, as {(a_node, b_node): weight, …}.

Returns

Matching between nodes as (a_node, b_node).

Return type

set of (object, object)

qecsim.graphtools.blossom5

This module provides a somewhat low-level Python interface for Blossom V, a fast C++ implementation of minimum-weight perfect matching in a graph, due to Vladimir Kolmogorov. (Typically, this module is not invoked directly, see rather the functions of qecsim.graphtools.)

Vladimir Kolmogorov. “Blossom V: A new implementation of a minimum cost perfect matching algorithm.” In Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.

The licence for Blossom V does not permit public redistribution of the code or its derivatives (see the Blossom V site http://pub.ist.ac.at/~vnk/software.html and the Blossom V README.TXT file for full details of the license and citation requirements). Therefore, Blossom V is not packaged with qecsim.

If your use case satisfies the license requirements of Blossom V, see section Fast matching library (optional) for details on how to configure qecsim to use Blossom V. When performance is not a concern, the Python package NetworkX, https://networkx.github.io/, may be sufficient and is already installed as a qecsim dependency.

The functions in this module assume the presence of a C++ library libpypm.so in one of the locations searched by qecsim.util.load_clib(). All functions, except available() will fail with an OSError if the library cannot be loaded.

qecsim.graphtools.blossom5.available()
Returns

Availability of Blossom V library.

Return type

bool

qecsim.graphtools.blossom5.infty()

Integer that represents infinity (Blossom V algorithm).

Note:

  • This can be useful when converting float to int weights for MWPM.

Returns

Value that represents infinity.

Return type

int

Raises

OSError – if Blossom V library cannot be loaded.

qecsim.graphtools.blossom5.mwpm(edges)

Minimum Weight Perfect Matching using node objects (Blossom V algorithm).

Parameters

edges (list of (object, object, int)) – Edges as [(node, node, weight), …].

Returns

Set of matches as {(node, node), …}.

Return type

set of (object, object)

Raises

OSError – if Blossom V library cannot be loaded.

qecsim.graphtools.blossom5.mwpm_ids(edges)

Minimum Weight Perfect Matching using node ids (Blossom V algorithm).

Notes:

  • Node ids are assumed to form a contiguous set of non-negative integers starting at zero, e.g. {0, 1, …}.

  • All nodes are assumed to participate in at least one edge.

Parameters

edges (list of (int, int, int)) – Edges as [(node_id, node_id, weight), …].

Returns

Set of matches as {(node_id, node_id), …}. (Each tuple is sorted.)

Return type

set of (int, int)

Raises

OSError – if Blossom V library cannot be loaded.

qecsim.graphtools.blossom5.weight_to_int_fn(weights)

Given an iterable of weights, return a function that scales all weights by a multiplicative factor and rounds to integers such that the largest (absolute) weight is an order of magnitude smaller than infty().

Notes:

  • The returned function is useful to convert float weights to ints for the Blossom V implementation.

  • If all weights are integers and the largest (absolute) weight is at least an order of magnitude smaller than infty() then the identity function is returned.

  • If the scaling function would scale the smallest (absolute) non-zero weight to zero or less than 3 significant figures, then a warning is logged.

Parameters

weights (iterable of int or float) – Weights (positive and/or negative)

Returns

Function with signature weight_to_int(float or int) -> int

Return type

function

Raises

OSError – if Blossom V library cannot be loaded.