From 352e1be1bf05de2ba75f93b8375ac52036c8203e Mon Sep 17 00:00:00 2001
From: Jaron Kent-Dobias <jaron@kent-dobias.com>
Date: Tue, 4 Oct 2022 12:37:14 +0200
Subject: Refactored base code and added new utility to measure the order
 paremeter.

---
 rbmp.hpp | 106 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 106 insertions(+)
 create mode 100644 rbmp.hpp

(limited to 'rbmp.hpp')

diff --git a/rbmp.hpp b/rbmp.hpp
new file mode 100644
index 0000000..571fb05
--- /dev/null
+++ b/rbmp.hpp
@@ -0,0 +1,106 @@
+#include <cmath>
+#include <functional>
+#include <random>
+#include <vector>
+#include <limits>
+
+#include "randutils/randutils.hpp"
+#include "pcg-cpp/include/pcg_random.hpp"
+
+#include "blossom5-v2.05.src/PerfectMatching.h"
+
+using Rng = randutils::random_generator<pcg32>;
+
+class Edge;
+class HalfEdge;
+
+class Coordinate {
+  std::array<int, 2> r;
+  public:
+  void operator=(const std::array<int, 2>& rp) {
+    r = rp;
+  }
+  void operator+=(const Coordinate& x) {
+    r[0] += x.r[0];
+    r[1] += x.r[1];
+  }
+  void operator-=(const Coordinate& x) {
+    r[0] -= x.r[0];
+    r[1] -= x.r[1];
+  }
+  int operator[](unsigned i) const {
+    return r[i];
+  }
+};
+
+class Vertex {
+public:
+  unsigned index;
+  std::vector<std::reference_wrapper<HalfEdge>> neighbors;
+  Coordinate coordinate;
+
+  void addEdge(HalfEdge& e) {
+    neighbors.push_back(e);
+  }
+};
+
+class HalfEdge {
+private:
+  Vertex* tail;
+  Vertex* head;
+
+public:
+  const Edge& edge;
+
+  HalfEdge(const Edge& e) : edge(e) {}
+  void setVertices(Vertex& vt, Vertex& vh) {
+    tail = &vt;
+    head = &vh;
+  }
+  const Vertex& getHead() const {
+    return *head;
+  }
+  const Vertex& getTail() const {
+    return *tail;
+  }
+};
+
+class Edge {
+public:
+  std::array<HalfEdge, 2> halfedges;
+  double weight;
+
+  Edge() : halfedges{*this, *this} {};
+  void setVertices(Vertex& red, Vertex& blue) {
+    halfedges[0].setVertices(red, blue);
+    halfedges[1].setVertices(blue, red);
+    red.addEdge(halfedges[0]);
+    blue.addEdge(halfedges[1]);
+  }
+};
+
+class Graph {
+public:
+  std::vector<Vertex> vertices;
+  std::vector<Edge> edges;
+
+  Graph(int n, Rng& r) : vertices(2 * n * (n + 1)), edges(pow(2 * n, 2)) {
+    unsigned M = vertices.size() / 2;
+    for (int i = 0; i < M; i++) {
+      vertices[i].index = i;
+      vertices[i].coordinate = {2 * (i % (n + 1)), 2 * (i / (n + 1)) + 1};
+      vertices[M + i].index = M + i;
+      vertices[M + i].coordinate = {2 * (i % n) + 1, 2 * (i / n)};
+    }
+    for (unsigned i = 0; i < edges.size(); i++) {
+      Vertex& redVertex = vertices[(1 + (i % (2 * n))) / 2 + (n + 1) * ((i / 4) / n)];
+      Vertex& blueVertex = vertices[M + (i % (2 * n)) / 2 + n * (((i + 2 * n) / 4) / n)];
+      edges[i].setVertices(redVertex, blueVertex);
+      edges[i].weight = r.variate<double, std::exponential_distribution>(1);
+    }
+  }
+};
+
+bool edgeMatched(PerfectMatching& pm, const Edge& e) {
+  return e.halfedges[0].getTail().index == pm.GetMatch(e.halfedges[0].getHead().index);
+}
-- 
cgit v1.2.3-70-g09d2