minorminer icon indicating copy to clipboard operation
minorminer copied to clipboard

Allow finding imbalanced chain embedding.

Open joseppinilla opened this issue 3 years ago • 0 comments

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()}}

joseppinilla avatar Aug 30 '21 23:08 joseppinilla