.. _general_embedding:
=================
General Embedding
=================
General embedding refers to embedding that may be useful for any type of graph.
.. include:: ../README.rst
:start-after: general-embedding-start-marker
:end-before: general-embedding-end-marker
.. autofunction:: minorminer.find_embedding
....
Examples
========
This example minor embeds a triangular source K3 graph onto a square target graph.
.. 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]]
.. figure:: ../_images/Embedding_TriangularSquare.png
:name: Embedding_TriangularSquare
:scale: 60 %
:alt: Embedding a triangular source graph into a square target graph
Embedding a :math:`K_3` source graph into a square target graph by chaining two
target nodes to represent one source node.
....
This minorminer execution of the example requires that source variable 0 always
be assigned to target node 2.
.. code-block:: python
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]
....
This minorminer execution of the example suggests that source variable 0 be
assigned to target node 2 as a starting point for finding an embedding.
.. code-block:: python
embedding = find_embedding(triangle, square, initial_chains={0: [2]})
print(embedding)
# [[2], [0, 3], [1]]
# [[0], [3], [1, 2]]
# Output where source variable 0 has switched to a different target node is possible.
....
This example minor embeds a fully connected K6 graph into a 30-node random
regular graph of degree 3.
.. code-block:: python
import networkx as nx
clique = nx.complete_graph(6).edges()
target_graph = nx.random_regular_graph(d=3, n=30).edges()
embedding = find_clique_embedding(clique, target_graph)
print(embedding)
# There are many possible outputs, and sometimes it might fail
# and return an empty list
# One run returned the following embedding:
{0: [10, 9, 19, 8],
1: [18, 7, 0, 12, 27],
2: [1, 17, 22],
3: [16, 28, 4, 21, 15, 23, 25],
4: [11, 24, 13],
5: [2, 14, 26, 5, 3]}
.. figure:: ../_images/Embedding_K6Random3.png
:name: Embedding_K6Random3
:scale: 80 %
:alt: Embedding a K6 graph into a 30-node random graph
Embedding a :math:`K_6` source graph (upper left) into a 30-node random target graph of
degree 3 (upper right) by chaining several target nodes to represent one source node (bottom).
The graphic of the embedding clusters chains representing nodes in the source graph: the
cluster of red nodes is a chain of target nodes that represent source node 0, the orange
nodes represent source node 1, and so on.