Introduction¶

Examples¶

This example minor embeds a triangular source K4 graph onto a square target graph.

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


This minorminer execution of the example requires that source variable 0 always be assigned to target node 2.

embedding = find_embedding(triangle, square, fixed_chains={0: [2]})
print(embedding)
# [[2], [3, 0], [1]]
# [[2], [1], [0, 3]]


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.

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.

import networkx as nx

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