From 82b8dddfef6b453d364b4cf1b97a07a735d5ff41 Mon Sep 17 00:00:00 2001
From: Jaron Kent-Dobias <jaron@kent-dobias.com>
Date: Mon, 18 May 2020 16:51:57 -0400
Subject: Switched to Newman-Ziff, it's much faster.

---
 grown_networks.cpp | 80 ++++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 59 insertions(+), 21 deletions(-)

diff --git a/grown_networks.cpp b/grown_networks.cpp
index bacbb71..ea4deae 100644
--- a/grown_networks.cpp
+++ b/grown_networks.cpp
@@ -8,12 +8,57 @@
 #include "pcg-cpp/include/pcg_random.hpp"
 #include "randutils/randutils.hpp"
 
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/connected_components.hpp>
-
 using Rng = randutils::random_generator<pcg32>;
 
-typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> Graph;
+class ClusterTree {
+private:
+  std::vector<signed> p;
+  std::vector<unsigned> o;
+
+  unsigned findroot(unsigned i) {
+    if (p[i] < 0)
+      return i;
+    else
+      return p[i] = this->findroot(p[i]);
+  }
+
+  void join(unsigned i, unsigned j) {
+    if (o[i] < o[j]) {
+      p[i] = j;
+      o[j] += o[i];
+    } else {
+      p[j] = i;
+      o[i] += o[j];
+    }
+  }
+
+public:
+  ClusterTree(unsigned n) : p(n, -1), o(n, 1) {}
+
+  void add_bond(unsigned v0, unsigned v1) {
+    unsigned i = this->findroot(v0);
+    unsigned j = this->findroot(v1);
+
+    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;
+  }
+
+  signed pointer(unsigned i) const {
+    return p[i];
+  }
+
+  unsigned size(unsigned i) const {
+    return o[i];
+  }
+};
 
 int main(int argc, char* argv[]) {
   unsigned N = 10;
@@ -46,34 +91,27 @@ int main(int argc, char* argv[]) {
   std::vector<uint64_t> nS(T);
 
   for (unsigned i = 0; i < N; i++) {
-    Graph G(T);
+    ClusterTree G(T);
 
     for (unsigned t = 0; t < T; t++) {
       if (rng.uniform(0.0, 1.0) < δ) {
-        boost::add_edge(rng.uniform((unsigned)0, t), rng.uniform((unsigned)0, t), G);
+        G.add_bond(rng.uniform<unsigned>(0, t), rng.uniform<unsigned>(0, t));
       }
     }
 
-    std::vector<unsigned> components(T);
-    unsigned nc = boost::connected_components(G, &components[0]);
-
-    std::vector<unsigned> s(nc);
-
-    for (unsigned j : components) {
-      s[j]++;
-    }
-
-    unsigned j_max = 0;
+    unsigned maxSize = 0;
 
-    for (unsigned j : s) {
-      ns[j - 1]++;
+    for (unsigned j = 0; j < T; j++) {
+      if (G.pointer(j) < 0) {
+        ns[G.size(j) - 1]++;
 
-      if (j > j_max) {
-        j_max = j;
+        if (G.size(j) > maxSize) {
+          maxSize= G.size(j);
+        }
       }
     }
 
-    nS[j_max - 1]++;
+    nS[maxSize - 1]++;
   }
 
   std::string filename = "ns_" + std::to_string(δ) + "_" + std::to_string(T) + ".dat";
-- 
cgit v1.2.3-54-g00ecf