Repository: dwavesystems/dimod
Pull request #1343 (2023-06-23 19:28:54)

Fix frustrated_loop()'s handling of graphs with tuple labels
This function really needs an overhaul for performance, but I tried to keep the changes minimal for now.

Closes https://github.com/dwavesystems/dimod/issues/1342


Patch:
diff --git a/dimod/generators/fcl.py b/dimod/generators/fcl.py
index 5a38334d..e69ff152 100644
--- a/dimod/generators/fcl.py
+++ b/dimod/generators/fcl.py
@@ -16,9 +16,8 @@ import warnings
 
 from typing import Callable, Collection, List, Mapping, Optional
 
-import numpy.random
+import numpy as np
 
-from numpy import prod
 from dimod.binary_quadratic_model import BinaryQuadraticModel
 from dimod.decorators import graph_argument
 from dimod.typing import GraphLike, Variable
@@ -108,7 +107,7 @@ def frustrated_loop(graph: GraphLike,
     if max_failed_cycles <= 0:
         raise ValueError("max_failed_cycles should be a positive integer")
     
-    r = numpy.random.RandomState(seed)
+    r = np.random.RandomState(seed)
 
     adj = {v: set() for v in nodes}
     for u, v in edges:
@@ -142,7 +141,7 @@ def frustrated_loop(graph: GraphLike,
         else:
             # randomly select from all frustrated loops (odd number of AFM edges)
             cycle_J = {(cycle[i], cycle[i+1]) : -1 for i in range(len(cycle)-1)}
-            cycle_J[(cycle[-1],cycle[0])] = (1 - 2*(len(cycle_J) & 1))*prod(list(cycle_J.values()))
+            cycle_J[(cycle[-1], cycle[0])] = (1 - 2*(len(cycle_J) & 1))*np.prod(list(cycle_J.values()))
             
         # update the bqm
         bqm.add_interactions_from(cycle_J)
@@ -195,8 +194,13 @@ def _random_cycle(adj, random_state):
             # we've walked into a dead end
             return None
 
+        # in some cases, neighbors will be interpreted as a 2d array by np.random.choice
+        # so let's ensure it's always a 1d
+        arr = np.empty(len(neighbors), dtype=object)
+        arr[:] = neighbors
+
         # get a random neighbor
-        u = random_state.choice(neighbors)
+        u = random_state.choice(arr)
         if u in visited:
             # if we've seen this neighbour, then we have a cycle starting from it
             return walk[visited[u]:]
diff --git a/releasenotes/notes/fix-frustrated-loop-tuple-labels-0ec17b68ee6cfd42.yaml b/releasenotes/notes/fix-frustrated-loop-tuple-labels-0ec17b68ee6cfd42.yaml
new file mode 100644
index 00000000..4ce06494
--- /dev/null
+++ b/releasenotes/notes/fix-frustrated-loop-tuple-labels-0ec17b68ee6cfd42.yaml
@@ -0,0 +1,5 @@
+---
+fixes:
+  - |
+    Fix ``dimod.generators.frustrated_loop()`` to correctly handle graphs with
+    tuple labels. See `#1342 <https://github.com/dwavesystems/dimod/issues/1342>`_.


Test patch:
diff --git a/tests/test_generators.py b/tests/test_generators.py
index 48192467..467bda89 100644
--- a/tests/test_generators.py
+++ b/tests/test_generators.py
@@ -411,6 +411,16 @@ class TestFCL(unittest.TestCase):
         all_ones = {v:1 for v in G}
         self.assertNotEqual(bqm.energy(planted),bqm.energy(all_ones))
 
+    def test_smoke_tuple_labels(self):
+        # https://github.com/dwavesystems/dimod/issues/1342
+        g = nx.erdos_renyi_graph(100, 0.5)
+        tuple_map = dict()
+        for node in g.nodes:
+            tuple_map[node] = (node, node, node)
+        g = nx.relabel_nodes(g, tuple_map)
+        bqm = dimod.generators.frustrated_loop(g, R=3, num_cycles=100)
+
+
 class TestCombinations(unittest.TestCase):
 
     def check_combinations(self, variables, k, bqm, strength):