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

Allow finding imbalanced chain embedding. #185

Open joseppinilla opened 3 years ago

joseppinilla commented 3 years ago

Feature Request The biclique embedding method in busgraph_cache doesn't provide an option for chain_imbalance=(None or int) like the one found in the polynomialembedder for tightestNativeBiClique and largestNativeBiClique. The new feature would allow:

P = 6
M,N = 4,32
G = dnx.pegasus_graph(P)
cache = minorminer.busclique.busgraph_cache(G)
embedding = cache.find_biclique_embedding(M,N,chain_imbalance=None)

The alternative right now means that the cache functionality and faster implementation in busgraph is only limited to balanced chains. And this is how it would look for Pegasus.

Using polynomialembedder

_embedder, _converter = helper(P, G)
helper = minorminer.utils.pegasus._pegasus_fragment_helper
_left,_right = _embedder.tightestNativeBiClique(M,N,chain_imbalance=None)
left,right = _converter(range(M),_left),_converter(range(N),_right)
embedding = {**left,**{k+M:v for k,v in right.items()}}