AENC/switchchain Changeset - 28b33414825e · Centrum Wiskunde & Informatica (CWI)

Changeset - 28b33414825e

Parent rev.

Child rev.

[Not reviewed]

0 2 0

Tom Bannink - 8 years ago 2017-05-15 17:13:00
tombannink@gmail.com

Add initial code for degree-structure-plots

2 files changed with 26 insertions and 1 deletions:

cpp/graph.hpp

cpp/switchchain.cpp

0 comments (0 inline, 0 general)

cpp/graph.hpp

➞

Show inline comments

@@ @@ -53,12 +53,14 @@ class Graph { @@
+    }
     unsigned int edgeCount() const { return edges.size(); }
     const Edge &getEdge(unsigned int i) const { return edges[i].e; }
     const auto& getAdj() const { return adj; }
     // When the degree sequence is not graphics, the Graph can be
     // in any state, it is not neccesarily empty
     bool createFromDegreeSequence(const DegreeSequence &d) {
         // Havel-Hakimi algorithm
         // Based on Erdos-Gallai theorem

cpp/switchchain.cpp

➞

Show inline comments

 #include "exports.hpp"
 #include "graph.hpp"
 #include "powerlaw.hpp"
 #include <algorithm>
 #include <array>
 #include <fstream>
 #include <iostream>
 #include <numeric>
 #include <random>
 #include <vector>
@@ @@ -60,12 +61,33 @@ class SwitchChain { @@
     std::mt19937 mt;
     std::uniform_int_distribution<> edgeDistribution;
     //std::uniform_int_distribution<> permutationDistribution;
     std::bernoulli_distribution permutationDistribution;
 };
 void getTriangleDegrees(const Graph& g) {
     std::vector<std::array<std::size_t,3>> trids;
     const auto& adj = g.getAdj();
     int triangles = 0;
     for (auto& v : adj) {
         for (unsigned int i = 0; i < v.size(); ++i) {
             for (unsigned int j = i + 1; j < v.size(); ++j) {
                 if (g.hasEdge({v[i], v[j]})) {
                     ++triangles;
                     std::array<std::size_t, 3> ds = {v.size(), adj[v[i]].size(),
                                                      adj[v[j]].size()};
                     std::sort(ds.begin(), ds.end());
                     trids.push_back(ds);
+                }
+            }
+        }
+    }
     assert(triangles % 3 == 0);
     return;
+}
 //
 // Assumes degree sequence does NOT contain any zeroes!
 //
 // method2 = true  -> take highest degree and finish its pairing completely
 // method2 = false -> take new highest degree after every pairing
 bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, auto& rng, bool method2) {
@@ @@ -198,13 +220,13 @@ int main() { @@
             powerlaw_distribution degDist(tau, 1, numVertices);
             //std::poisson_distribution<> degDist(12);
             // For a single n,tau take samples over several instances of
             // the degree distribution.
             // 500 samples seems to give reasonable results
-            for (int degreeSample = 0; degreeSample < 200; ++degreeSample) {
+            for (int degreeSample = 0; degreeSample < 1; ++degreeSample) {
                 // Generate a graph
                 // might require multiple tries
                 for (int i = 1; ; ++i) {
                     std::generate(ds.begin(), ds.end(),
                                   [&degDist, &rng] { return degDist(rng); });
                     // First make the sum even
@@ @@ -274,12 +296,13 @@ int main() { @@
                 //    200; // Take a sample every ... steps
                 int mixingTime = 0;
                 constexpr int measurements = 50000;
                 constexpr int measureSkip = 1;
                 int movesDone = 0;
                 int triangles[measurements];
                 for (int i = 0; i < mixingTime; ++i) {
                     if (chain.doMove())

0 comments (0 inline, 0 general)