minorminer

January 27, 2026 · View on GitHub

.. start_minorminer_about

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.

.. start_minorminer_about_general_embedding

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

.. end_minorminer_about

Python

Installation

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

.. code-block:: bash

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 tests/requirements.txt
python -m pytest .

Examples

.. start_minorminer_examples_python

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

.. end_minorminer_examples_python

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:

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

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.dwavequantum.com/en/latest/ocean/contribute.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.

Release Notes

minorminer makes use of reno <https://docs.openstack.org/reno/>_ to manage its release notes.

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

.. code-block:: bash

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 <https://docs.openstack.org/reno/latest/user/usage.html>_ for details.