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

Need to seed/randomize the `find_subgraph` function #243

Open kevinchern opened 9 months ago

kevinchern commented 9 months ago

I cannot randomize nor fix the seed used in minorminer.subgraph.find_subgraph find_subgraph(subgraph, big_graph, value_ordering='random') always gives the same result

jackraymond commented 9 months ago

A workaround you might try is to perform a graph automorphism or relabeling of the graph. Another guaranteed workaround is to break the source graph with respect to subgraphs you don't want to see (removing any subset of the edges or nodes [from a known subgraph] from the graph will force an alternative subgraph). This can be generalized to a branch and bound method to enumerate all cases (albeit inefficiently in most applications).

I agree, would be useful to have option to randomize, or to have a generator of unique subgraphs, built in.

kevinchern commented 9 months ago

relabeling of the graph.

there's a slight problem with this approach (pointed out to me by @boothby), because the variable names are changed but the node list order is the same. Node list order is used in the find_subgraph method. So another workaround is to recreate a graph by randomizing the node order.

jackraymond commented 2 weeks ago

Yes, you need to regenerate the graph with permuted edge order (and/or permuted node order). It was pointed out to be me by @arcondello that subgraph is a function only of the edge order though, so node order only matters in so far as it impacts edge order. There is a related [pathological case] bug (that isolated nodes are ignored by find_subgraph). https://github.com/dwavesystems/minorminer/issues/254