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.

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

Python

Installation

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

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.

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

Examples

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]]

# 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]

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

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

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

C++

Installation

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:

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

add_subdirectory(externals/minorminer)

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

Examples

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

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

Release Notes

minorminer makes use of reno to manage its release notes.

When making a contribution to minorminer that will affect users, create a new release note file by running

reno new your-short-descriptor-here

You can then edit the file created under releasenotes/notes/. Remove any sections not relevant to your changes. Commit the file along with your changes.

See reno's user guide for details.