From ca21806f02498ac314da1a9444aa71ad9dc657c3 2017-09-04 09:34:47
From: Tom Bannink <tom.bannink@cwi.nl>
Date: 2017-09-04 09:34:47
Subject: [PATCH] Add ECM and histogram header files

---

diff --git a/cpp/graph_ecm.hpp b/cpp/graph_ecm.hpp
new file mode 100644
index 0000000000000000000000000000000000000000..4cb88c77b6d42f3485e74eb1605d321aaf9939ba
--- /dev/null
+++ b/cpp/graph_ecm.hpp
@@ -0,0 +1,31 @@
+#include "graph.hpp"
+#include <algorithm>
+#include <iostream>
+#include <random>
+#include <vector>
+
+template <typename RNG>
+bool erasedConfigurationModel(DegreeSequence &ds, Graph &g, RNG &rng) {
+    // List of all half-edges
+    std::vector<unsigned int> halfEdges;
+    for (unsigned int i = 0; i < ds.size(); ++i)
+        halfEdges.insert(halfEdges.end(), ds[i], i);
+
+    // Clear the graph
+    g.reset(ds.size());
+
+    if (halfEdges.size() % 2 != 0)
+        return false;
+
+    std::shuffle(halfEdges.begin(), halfEdges.end(), rng);
+    // pair halfEdges[2*i] with halfEdges[2*i+1]
+    for (auto iter = halfEdges.begin(); iter != halfEdges.end();) {
+        auto u = *iter++;
+        auto v = *iter++;
+        if (u != v)
+            g.addEdge({u, v}); // checks for double edges
+    }
+
+    return true;
+}
+
diff --git a/cpp/histogram.hpp b/cpp/histogram.hpp
new file mode 100644
index 0000000000000000000000000000000000000000..f6e6a02c6a2879d7452f7e60ce601f5c16a6e91c
--- /dev/null
+++ b/cpp/histogram.hpp
@@ -0,0 +1,50 @@
+#pragma once
+#include "exports.hpp"
+#include <algorithm>
+#include <vector>
+
+// Histogram over integers with binsize 1
+class Histogram {
+  public:
+    Histogram() : xmin(0) {}
+    ~Histogram() {}
+
+    void reset() {
+        frequencies.clear();
+        xmin = 0;
+    }
+
+    void add(int sample) {
+        if (frequencies.empty()) {
+            xmin = sample;
+            frequencies.push_back(1);
+            return;
+        }
+        if (sample < xmin) {
+            int extra = xmin - sample;
+            frequencies.insert(frequencies.begin(), extra, 0);
+            xmin = sample;
+            frequencies.front()++;
+            return;
+        }
+        if (sample - xmin >= (int)frequencies.size()) {
+            int extra = sample - xmin - frequencies.size() + 1;
+            frequencies.insert(frequencies.end(), extra, 0);
+            frequencies.back()++;
+            return;
+        }
+        frequencies[sample - xmin]++;
+    }
+
+    // For exports
+    std::vector<std::pair<int, int>> getHistogram() const {
+        std::vector<std::pair<int, int>> histogram;
+        int i = xmin;
+        for (auto f : frequencies)
+            histogram.push_back({i++, f});
+        return histogram;
+    }
+
+    std::vector<int> frequencies;
+    int xmin;
+};