From 4d4eb2d57ab6076acdc4d1e8d6dcbe94ced704c6 Mon Sep 17 00:00:00 2001
From: Jaron Kent-Dobias <jaron@kent-dobias.com>
Date: Wed, 24 Mar 2021 14:20:26 +0100
Subject: Fixed problem by cycling over all visited neighbors until end, but
 this is still slow...

---
 biroli-mezard.cpp | 100 +++++++++++++++++++++++++++++++++---------------------
 1 file changed, 61 insertions(+), 39 deletions(-)

diff --git a/biroli-mezard.cpp b/biroli-mezard.cpp
index 58c1e6a..13f3b3f 100644
--- a/biroli-mezard.cpp
+++ b/biroli-mezard.cpp
@@ -457,61 +457,83 @@ public:
     }
   }
 
-  unsigned flipClusterHelper(const Transformation<D>& R, Vertex<D>& v, bool initial = false) {
+  unsigned flipCluster(const Transformation<D>& R, Vertex<D>& v0) {
     unsigned n = 0;
 
-    if (!v.marked && (!overlaps(v).empty() || initial)) {
-      v.marked = true;
-      Vertex<D>& vNew = vertices[vectorToIndex(R.apply(v.position))];
+    Vertex<D>& v0New = vertices[vectorToIndex(R.apply(v0.position))];
 
-      if (&vNew != &v) {
-        vNew.marked = true;
+    if (&v0New != &v0) {
+      std::queue<std::reference_wrapper<Vertex<D>>> q;
 
-        swap(v, vNew);
-        /*
-        while (!overlaps({v, vNew}).empty()) {
-          for (Vertex<D>& vn : overlaps({v, vNew})) {
-            flipClusterHelper(R, vn);
-          }
+      v0.marked = true;
+      v0New.marked = true;
+
+      swap(v0, v0New);
+
+      for (Vertex<D>& vn : v0.neighbors) {
+        if ((!vn.marked && !vn.visited) && !vn.empty()) {
+          q.push(vn);
+          vn.visited = true;
         }
-        */
-        for (Vertex<D>& vn : overlaps({v, vNew})) {
-          if (!vn.marked) {
-            n += flipClusterHelper(R, vn);
-          }
+      }
+      for (Vertex<D>& vn : v0New.neighbors) {
+        if ((!vn.marked && !vn.visited) && !vn.empty()) {
+          q.push(vn);
+          vn.visited = true;
         }
-
-        n += 2;
-      } else {
-        n += 1;
       }
-    } else {
-    }
 
-    return n;
-  }
+      unsigned last_unsatisfied = 0;
 
-  unsigned flipCluster(const Transformation<D>& R, Vertex<D>& v0) {
-    unsigned n = flipClusterHelper(R, v0, true);
-
-    bool badVertex = true;
-    while (badVertex) {
-      badVertex = false;
-      for (Vertex<D>& vv : vertices) {
-        if (!vv.marked && !overlaps(vv).empty()) {
-          std::cerr << "Found bad vertex." << std::endl;
-          n += flipClusterHelper(R, vv);
-          badVertex = true;
+      while (!q.empty() && last_unsatisfied < q.size()) {
+        Vertex<D>& v = q.front();
+        q.pop();
+
+        if (!v.marked) {
+          if (!overlaps(v).empty()) {
+            last_unsatisfied = 0;
+            v.marked = true;
+            Vertex<D>& vNew = vertices[vectorToIndex(R.apply(v.position))];
+
+            if (&vNew != &v) {
+              vNew.marked = true;
+
+              swap(v, vNew);
+
+              for (Vertex<D>& vn : v.neighbors) {
+                if ((!vn.marked && !vn.visited) && !vn.empty()) {
+                  q.push(vn);
+                  vn.visited = true;
+                }
+              }
+              for (Vertex<D>& vn : vNew.neighbors) {
+                if ((!vn.marked && !vn.visited) && !vn.empty()) {
+                  q.push(vn);
+                  vn.visited = true;
+                }
+              }
+
+              n += 2;
+            } else {
+            }
+          } else {
+            q.push(v);
+            last_unsatisfied++;
+          }
+          n += 1;
         }
       }
-    } 
+    } else {
+      n = 1;
+    }
 
-    if (n > occupancy() / 2) {
+    if (n > size() / 2) {
       orientation = R.apply(orientation);
     }
 
     for (Vertex<D>& v : vertices) {
       v.marked = false;
+      v.visited = false;
     }
 
     return n;
@@ -581,7 +603,7 @@ int main() {
     }
     unsigned nn = s.flipCluster(Transformation<D>(L, ms, r), r.pick(s.vertices));
     nC += nn;
-    clusterDist[nn]++;
+//    clusterDist[nn]++;
     //s.sweepLocal(r);
     //nC += s.size();
     //s.sweepSwap(r);
-- 
cgit v1.2.3-70-g09d2