From d00d4896955c38818685802de42b4e79e6ef933c Mon Sep 17 00:00:00 2001
From: Jaron Kent-Dobias <jaron@kent-dobias.com>
Date: Mon, 23 Sep 2019 15:43:17 -0400
Subject: started migration away from boost algorithms is the backbone trimming
 code

---
 lib/include/clusters.hpp | 52 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 52 insertions(+)
 create mode 100644 lib/include/clusters.hpp

(limited to 'lib/include/clusters.hpp')

diff --git a/lib/include/clusters.hpp b/lib/include/clusters.hpp
new file mode 100644
index 0000000..4cc9073
--- /dev/null
+++ b/lib/include/clusters.hpp
@@ -0,0 +1,52 @@
+
+#include <vector>
+#include "graph.hpp"
+
+class ClusterTree {
+private:
+  std::vector<signed> p;
+  std::vector<unsigned> o;
+
+public:
+  std::vector<unsigned> c;
+
+  ClusterTree(unsigned n) : p(n, -1), o(n, 1), c(n, 0) { c[0] = n; }
+
+  unsigned findroot(unsigned i) {
+    if (p[i] < 0)
+      return i;
+    else
+      return p[i] = this->findroot(p[i]);
+  }
+
+  void join(unsigned i, unsigned j) {
+    c[o[i] - 1]--;
+    c[o[j] - 1]--;
+
+    if (o[i] < o[j]) {
+      p[i] = j;
+      o[j] += o[i];
+      c[o[j] - 1]++;
+    } else {
+      p[j] = i;
+      o[i] += o[j];
+      c[o[i] - 1]++;
+    }
+  }
+
+  void add_bond(const graph::edge& b) {
+    unsigned i = this->findroot(b.v[0]);
+    unsigned j = this->findroot(b.v[1]);
+
+    if (i != j) {
+      this->join(i, j);
+    }
+  }
+
+  bool same_component(unsigned v0, unsigned v1) {
+    unsigned i = this->findroot(v0);
+    unsigned j = this->findroot(v1);
+
+    return i == j;
+  }
+};
-- 
cgit v1.2.3-70-g09d2