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

find_clique_embedding(..., use_cache=False) is nondeterministic in deterministic regime #193

Closed boothby closed 3 years ago

boothby commented 3 years ago

Description This occurred in randomized testing: rarely, in testing problems with supposedly deterministic results, we see a mismatch in chainlength.

To Reproduce

import dwave_networkx as dnx, networkx as nx
from minorminer.busclique import find_clique_embedding
c4 = dnx.chimera_graph(4)
c4.remove_nodes_from([1, 119, 34, 6, 46, 117])
c4.remove_edges_from([
    (119, 127), (56, 62), (43, 46), (41, 46), (113, 117), (46, 54), (50, 82),
    (121, 127), (34, 37), (115, 117), (1, 6), (111, 119), (6, 14), (98, 100),
    (47, 55), (1, 33), (3, 6), (84, 92), (112, 117), (38, 46), (114, 117), 
    (113, 119), (42, 74), (1, 5), (34, 36), (40, 46), (34, 39), (115, 119),
    (19, 20), (80, 112), (117, 125), (34, 66), (18, 21), (2, 34), (42, 46),
    (112, 119), (1, 4), (114, 119), (0, 6), (34, 38), (1, 7), (2, 6), 
    (109, 117), (16, 23)
])
emb0 = find_clique_embedding(11, c4, use_cache = False)
emb1 = find_clique_embedding(11, c4, use_cache = True)
assert max(map(len, emb0.values())) == max(map(len, emb1.values())) #boom
assert emb0 == emb1 #boom

Expected behavior The embeddings should be identical.

Environment: minorminer 0.2.5