search

dwavesystems / minorminer

minorminer is a heuristic tool for minor embedding: given a minor and target graph, it tries to find a mapping that embeds the minor into the target.
https://docs.ocean.dwavesys.com/en/stable/docs_minorminer/source/sdk_index.html
Apache License 2.0
48 stars 40 forks source link

readme

.. image:: https://img.shields.io/pypi/v/minorminer.svg :target: https://pypi.org/project/minorminer

.. image:: https://img.shields.io/pypi/pyversions/minorminer.svg :target: https://pypi.python.org/pypi/minorminer

.. image:: https://circleci.com/gh/dwavesystems/minorminer.svg?style=svg :target: https://circleci.com/gh/dwavesystems/minorminer

.. image:: https://img.shields.io/badge/arXiv-1406.2741-b31b1b.svg :target: https://arxiv.org/abs/1406.2741

.. image:: https://img.shields.io/badge/arXiv-1507.04774-b31b1b.svg :target: https://arxiv.org/abs/1507.04774

.. index-start-marker

========== minorminer

minorminer is a heuristic tool for minor embedding: given a minor and target graph, it tries to find a mapping that embeds the minor into the target.

.. index-end-marker

.. general-embedding-start-marker

The primary utility function, find_embedding(), is an implementation of the heuristic algorithm described in [1]. It accepts various optional parameters used to tune the algorithm's execution or constrain the given problem.

This implementation performs on par with tuned, non-configurable implementations while providing users with hooks to easily use the code as a basic building block in research.

[1] https://arxiv.org/abs/1406.2741

Another function, find_clique_embedding(), can be used to find clique embeddings for Chimera, Pegasus, and Zephyr graphs in polynomial time. It is an implementation of the algorithm described in [2]. There are additional utilities for finding biclique embeddings as well.

[2] https://arxiv.org/abs/1507.04774

.. general-embedding-end-marker

Python

Installation

.. install-python-start

pip installation is recommended for platforms with precompiled wheels posted to pypi. Source distributions are provided as well.

.. code-block:: bash

pip install minorminer

To install from this repository, you will need to first fetch the submodules

git submodule init
git submodule update

and then run the setuptools script.

.. code-block:: bash

pip install -r requirements.txt
python setup.py install
# optionally, run the tests to check your build
pip install -r test_requirements.txt
python -m pytest .

.. install-python-end

Examples

.. code-block:: python

from minorminer import find_embedding

# A triangle is a minor of a square.
triangle = [(0, 1), (1, 2), (2, 0)]
square = [(0, 1), (1, 2), (2, 3), (3, 0)]

# Find an assignment of sets of square variables to the triangle variables
embedding = find_embedding(triangle, square, random_seed=10)
print(len(embedding))  # 3, one set for each variable in the triangle
print(embedding)
# We don't know which variables will be assigned where, here are a
# couple possible outputs:
# [[0, 1], [2], [3]]
# [[3], [1, 0], [2]]

.. code-block:: python

# We can insist that variable 0 of the triangle will always be assigned to [2]
embedding = find_embedding(triangle, square, fixed_chains={0: [2]})
print(embedding)
# [[2], [3, 0], [1]]
# [[2], [1], [0, 3]]
# And more, but all of them start with [2]

.. code-block:: python

# If we didn't want to force variable 0 to stay as [2], but we thought that
# was a good start we could provide it as an initialization hint instead.
embedding = find_embedding(triangle, square, initial_chains={0: [2]})
print(embedding)
# [[2], [0, 3], [1]]
# [[0], [3], [1, 2]]
# Output where variable 0 has switched to something else is possible again.

.. code-block:: python

import networkx as nx

# An example on some less trivial graphs
# We will try to embed a fully connected graph with 6 nodes, into a
# random regular graph with degree 3.
clique = nx.complete_graph(6).edges()
target_graph = nx.random_regular_graph(d=3, n=30).edges()

embedding = find_embedding(clique, target_graph)

print(embedding)
# There are many possible outputs for this, sometimes it might even fail
# and return an empty list

A more fleshed out example can be found under examples/fourcolor.py

.. code-block:: bash

cd examples
pip install -r requirements.txt
python fourcolor.py

Matlab (Deprecated)

Matlab support is deprecated as of vesion 0.2.8, and we will not accept bug reports in later versions. The matlab interface has been broken for the entire 0.2 series, and more than a year passed before this was discovered. It will be fixed in the 0.2.8 release, but the matlab support infrastructure will be removed entirely in May 2023, unless community developers volunteer to maintain it.

Installation

.. install-matlab-start

The mex bindings for this library will work with some versions of 2013 and earlier, and versions from 2016b an onward. An example build command used in Ubuntu is found in the makefile matlab/make.m.

If you run make in the matlab directory on Ubuntu it should generate find_embedding.mexa64, which can be added to the MATLAB path.

.. install-matlab-end

Examples

.. code-block:: matlab

% A triangle is a minor of a square.
triangle = triu(ones(3),1);
square = sparse([1,2,3,4],[2,3,4,1],[1,1,1,1],4,4);

% Find an assignment of sets of square variables to the triangle variables
options = struct('random_seed',10);
embedding = find_embedding_matlab_wrapper(triangle, square, options)
% typically in matlab we use indices starting at one rather than 0:
embedding = cellfun(@(x)x+1,embedding,'UniformOutput',false);
embedding{:}

.. code-block:: matlab

% We can insist that variable 0 of the triangle will always be assigned to
% [2] (zero-indexed)
chains = cell(1);
chains{1} = 2;
options = struct();
options.fixed_chains = chains;
embedding = find_embedding(triangle, square, options)
embedding{:}

.. code-block:: matlab

% If we didn't want to force variable 0 to stay as [2], but we thought that
% was a good start we could provide it as an initialization hint instead.
options = struct();
options.initial_chains = chains;
embedding = find_embedding(triangle, square, options)
embedding{:}

C++

Installation

.. install-c-start

The CMakeLists.txt in the root of this repo will build the library and optionally run a series of tests. On Linux, the commands would be something like this:

.. code-block:: bash

mkdir build; cd build
cmake ..
make

To build the tests, turn the CMake option MINORMINER_BUILD_TESTS on. The command line option for CMake to do this would be -DMINORMINER_BUILD_TESTS=ON.

Library Usage

C++11 programs should be able to use this as a header-only library. If your project is using CMake, this library can be used fairly simply; if you have checked out this repo as externals/minorminer in your project, you would need to add the following lines to your CMakeLists.txt

.. code-block:: CMake

add_subdirectory(externals/minorminer)

# After your target is defined
target_link_libraries(your_target minorminer pthread)

.. install-c-end

Examples

A minimal buildable example can be found in this repo under examples/example.cpp.

.. code-block:: bash

cd examples
g++ example.cpp -std=c++11 -o example -pthread

This can also be built using the included CMakeLists.txt along with the main library build by turning the CMake option MINORMINER_BUILD_EXAMPLES on. The command line option for CMake to do this would be -DMINORMINER_BUILD_EXAMPLES=ON.

License

Released under the Apache License 2.0. See <LICENSE>_ file.

Contributing

Ocean's contributing guide <https://docs.ocean.dwavesys.com/en/stable/contributing.html>_ has guidelines for contributing to Ocean packages.

If you're interested in adding or modifying parameters of the find_embedding primary utility function, please see the <parameter_checklist.txt>_ file.