summaryrefslogtreecommitdiff
path: root/biroli-mezard.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'biroli-mezard.cpp')
-rw-r--r--biroli-mezard.cpp100
1 files 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);