AENC/switchchain Changeset - 1b3f095f886f · Centrum Wiskunde & Informatica (CWI)

Changeset - 1b3f095f886f

Parent rev.

Child rev.

[Not reviewed]

0 4 0

Tom Bannink - 8 years ago 2017-07-03 16:06:50
tombannink@gmail.com

Add computation of delta-triangles to switchchain

3 files changed with 89 insertions and 45 deletions:

cpp/graph.hpp

cpp/switchchain.hpp

cpp/switchchain_mixingtime.cpp

0 comments (0 inline, 0 general)

cpp/graph.hpp

➞

Show inline comments

@@ @@ -145,7 +145,8 @@ class Graph { @@
     // There are two possible edge exchanges
     // switchType indicates which one is desired
     // Returns false if the switch is not possible
     bool exchangeEdges(unsigned int e1index, unsigned int e2index, bool switchType) {
     bool exchangeEdges(unsigned int e1index, unsigned int e2index,
                        bool switchType, bool trackTriangles = false) {
         StoredEdge &se1 = edges[e1index];
         StoredEdge &se2 = edges[e2index];
         const Edge &e1 = se1.e;
@@ @@ -165,6 +166,11 @@ class Graph { @@
         if (hasEdge({e1.u, e2.u}) || hasEdge({e1.v, e2.v}))
             return false; // conflicting edges
         if (trackTriangles) {
             trackedTriangles -= countTriangles(e1);
             trackedTriangles -= countTriangles(e2);
+        }
         // Clear old edges
         badj[e1.u][e1.v] = false;
         badj[e1.v][e1.u] = false;
@@ @@ -183,11 +189,30 @@ class Graph { @@
         badj[e1.v][e1.u] = true;
         badj[e2.u][e2.v] = true;
         badj[e2.v][e2.u] = true;
         if (trackTriangles) {
             trackedTriangles += countTriangles(e1);
             trackedTriangles += countTriangles(e2);
+        }
         return true;
+    }
     int countTriangles() const {
         int triangles = 0;
     // Assumes edge exists
     // Used for computing triangle-delta's after switch move
     unsigned int countTriangles(Edge e) const {
         auto triangles = 0u;
         if (adj[e.u].size() > adj[e.v].size())
             std::swap(e.u, e.v);
         for (auto w : adj[e.u]) {
             if (hasEdge({w, e.v}))
                 ++triangles;
+        }
         return triangles;
+    }
     unsigned int countTriangles() const {
         auto triangles = 0u;
         for (auto& v : adj) {
             for (unsigned int i = 0; i < v.size(); ++i) {
                 for (unsigned int j = i + 1; j < v.size(); ++j) {
@@ @@ -201,6 +226,8 @@ class Graph { @@
         return triangles / 3;
+    }
     unsigned int& getTrackedTriangles() { return trackedTriangles; }
     // Should return zero
     int consistencyCheck() const {
         // Check if info in 'edges' is present
@@ @@ -254,5 +281,6 @@ class Graph { @@
     std::vector<std::vector<unsigned int>> adj;
     std::vector<std::vector<bool>> badj; // symmetric binary matrix
     std::vector<StoredEdge> edges;
     unsigned int trackedTriangles;
 };

cpp/switchchain.hpp

➞

Show inline comments

@@ @@ -21,16 +21,18 @@ class SwitchChain { @@
+    }
     ~SwitchChain() {}
     bool initialize(const Graph& gstart) {
+    bool initialize(const Graph& gstart, bool trackTriangles = false) {
         if (gstart.edgeCount() == 0)
             return false;
         g = gstart;
         edgeDistribution.param(
             std::uniform_int_distribution<>::param_type(0, g.edgeCount() - 1));
         if (trackTriangles)
             g.getTrackedTriangles() = g.countTriangles();
         return true;
+    }
     bool doMove() {
+    bool doMove(bool trackTriangles = false) {
         int e1index, e2index;
         int timeout = 0;
         // Keep regenerating while conflicting edges
@@ @@ -48,7 +50,7 @@ class SwitchChain { @@
         // 2) e1.u - e2.u and e1.v - e2.v
         // 3) e1.u - e2.v and e1.v - e2.u
         bool switchType = permutationDistribution(mt);
         return g.exchangeEdges(e1index, e2index, switchType);
+        return g.exchangeEdges(e1index, e2index, switchType, trackTriangles);
+    }
     Graph g;

cpp/switchchain_mixingtime.cpp

➞

Show inline comments

@@ @@ -11,91 +11,104 @@ @@
 #include <vector>
 int main(int argc, char* argv[]) {
     // Generate a random degree sequence
     std::mt19937 rng(std::random_device{}());
     // Simulation parameters
     const int numVerticesMin = 1000;
     const int numVerticesMax = 4000;
     const int numVerticesStep = 500;
     // Goal:
     // Degrees follow a power-law distribution with some parameter tau
     // Expect:  #tri = const * n^{ something }
     // The goal is to find the 'something' by finding the number of triangles
     // for different values of n and tau
     //float tauValues[] = {2.5f};
     float tauValues[] = {2.1f, 2.2f, 2.3f, 2.4f, 2.5f, 2.6f, 2.7f, 2.8f, 2.9f};
     Graph g;
     Graph g1;
     Graph g2;
     const int totalDegreeSamples = 200;
     std::ofstream outfile;
     auto getMixingTime = [](int n, float tau) {
         (void)n;
         (void)tau;
         return 0;
         //return int(50.0f * (50.0f - 30.0f * (tau - 2.0f)) * n);
     };
     constexpr int measurements = 100000;
     constexpr int measureSkip = 1; // Take a sample every ... steps
     // Output file
     std::ofstream outfile;
     if (argc >= 2)
         outfile.open(argv[1]);
     else
         outfile.open("graphdata_etmt.m");
     if (!outfile.is_open()) {
         std::cout << "ERROR: Could not open output file.\n";
         return 1;
+    }
     // Output Mathematica-style comment to indicate file contents
     outfile << "(*\n";
     outfile << "n from " << numVerticesMin << " to " << numVerticesMax
             << " step " << numVerticesStep << std::endl;
     outfile << "tauValues: " << tauValues << std::endl;
     outfile << "degreeSamples: " << totalDegreeSamples << std::endl;
     outfile << "mixingTime: 50 * (50 - 30 (tau - 2)) n\n";
     outfile << "data:\n";
     outfile << "1: {n,tau}\n";
     outfile << "2: avgTriangles\n";
     outfile << "3: edges\n";
     outfile << "4: etmt\n";
     outfile << "*)" << std::endl;
     // Mathematica does not accept normal scientific notation
     outfile << std::fixed;
     outfile << '{';
     bool outputComma = false;
     for (int numVertices = 100; numVertices <= 1000; numVertices += 100) {
     // Generate a random degree sequence
     std::mt19937 rng(std::random_device{}());
     Graph g;
     Graph g1;
     Graph g2;
     for (int numVertices = numVerticesMin; numVertices <= numVerticesMax;
          numVertices += numVerticesStep) {
         for (float tau : tauValues) {
             // For a single n,tau take samples over several instances of
             // the degree distribution.
             for (int degreeSample = 0; degreeSample < 200; ++degreeSample) {
             for (int degreeSample = 0; degreeSample < totalDegreeSamples;
                  ++degreeSample) {
                 DegreeSequence ds;
                 generatePowerlawGraph(numVertices, tau, g, ds, rng);
                 // Multiple runs from the same degree sequence
                 for (int i = 0; i < 5; ++i) {
                 SwitchChain chain;
                 if (!chain.initialize(g)) {
+                if (!chain.initialize(g, true)) {
                     std::cerr << "Could not initialize Markov chain.\n";
                     return 1;
+                }
                 std::cout << "Running n = " << numVertices << ", tau = " << tau
                           << ". \t" << std::flush;
                 //int mixingTime = (32.0f - 26.0f*(tau - 2.0f)) * numVertices; //40000;
                 //constexpr int measurements = 50;
                 //constexpr int measureSkip =
                 //    200; // Take a sample every ... steps
                 int mixingTime = 0;
                 constexpr int measurements = 50000;
                 constexpr int measureSkip = 1;
                 std::cout << "Running (n,tau) = (" << numVertices << ','
                           << tau << "). " << std::flush;
                 int movesTotal = 0;
                 int movesSuccess = 0;
                 int triangles[measurements];
                 // Mix
                 int mixingTime = getMixingTime(numVertices, tau);
                 for (int i = 0; i < mixingTime; ++i) {
                     ++movesTotal;
                     if (chain.doMove()) {
                         ++movesSuccess;
+                    }
                     chain.doMove();
+                }
                 // Measure
                 for (int i = 0; i < measurements; ++i) {
                     for (int j = 0; j < measureSkip; ++j) {
                         ++movesTotal;
                         if (chain.doMove()) {
+                        if (chain.doMove(true)) {
                             ++movesSuccess;
+                        }
+                    }
-                    triangles[i] = chain.g.countTriangles();
+                    triangles[i] = chain.g.getTrackedTriangles();
+                }
                 std::cout << '('
                           << 100.0f * float(movesSuccess) / float(movesTotal)
                           << "% successrate). " << std::flush;
                 // std::cout << std::endl;
                 std::cout << "Measuring done. " << std::flush;
                 // Take the average over the last 20%
                 auto trianglesTotal = 0uL;
@@ @@ -119,12 +132,13 @@ int main(int argc, char* argv[]) { @@
                     outfile << ',' << '\n';
                 outputComma = true;
                 std::sort(ds.begin(), ds.end());
                 outfile << '{' << '{' << numVertices << ',' << tau << '}';
                 outfile << ',' << trianglesAvg;
                 outfile << ',' << g.edgeCount();
                 outfile << ',' << ETMT;
                 outfile << '}' << std::flush;
                 std::cout << std::endl;
+                std::cout << "Output done. " << std::endl;
+                }
+            }
+        }

0 comments (0 inline, 0 general)