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