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

Changeset - f8cbbd135cc1

Parent rev.

Child rev.

[Not reviewed]

0 4 0

Tom Bannink - 9 years ago 2017-02-02 18:30:09
tombannink@gmail.com

Add triangle counting

4 files changed with 30 insertions and 5 deletions:

cpp/exports.hpp

cpp/graph.hpp

cpp/showgraphs.m

cpp/switchchain.cpp

0 comments (0 inline, 0 general)

cpp/exports.hpp

➞

Show inline comments

 #pragma once
 #include <iostream>
 #include "graph.hpp"
 std::ostream &operator<<(std::ostream &s, const Edge &e) {

cpp/graph.hpp

➞

Show inline comments

 #pragma once
 #include <cassert>
 #include <numeric>
 #include <vector>
@@ @@ -35,7 +36,6 @@ class Graph { @@
     unsigned int edgeCount() const { return edges.size(); }
     Edge &getEdge(unsigned int i) { return edges[i]; }
     const Edge &getEdge(unsigned int i) const { return edges[i]; }
     bool createFromDegreeSequence(const DegreeSequence &d) {
@@ @@ -178,6 +178,21 @@ class Graph { @@
         return true;
+    }
     int countTriangles() const {
         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 (hasEdge({v[i], v[j]})) {
                         ++triangles;
+                    }
+                }
+            }
+        }
         assert(triangles % 3 == 0);
         return triangles / 3;
+    }
   private:
     // Graph is saved in two formats for speed
     // The two should be kept consistent at all times

cpp/showgraphs.m

➞

Show inline comments

@@ @@ -3,8 +3,11 @@ @@
 gsraw=Import[NotebookDirectory[]<>"graphdata.m"];
 gs=Map[Graph[#,GraphLayout->"CircularEmbedding"]&,gsraw];
 gs2=Map[Graph[#,GraphLayout->Automatic]&,gsraw];
 ListPlot[gsraw[[2]],Joined->True,PlotRange->All,AxesLabel->{"Step","Triangles"}]
 gs=Map[Graph[#,GraphLayout->"CircularEmbedding"]&,gsraw[[1]]];
 gs2=Map[Graph[#,GraphLayout->Automatic]&,gsraw[[1]]];
 Grid[Partition[gs,10],Frame->All]

cpp/switchchain.cpp

➞

Show inline comments

@@ @@ -104,18 +104,24 @@ int main() { @@
+    }
     std::ofstream outfile("graphdata.m");
     outfile << '{';
     outfile << '{' << g;
     std::cout << "Starting switch Markov chain" << std::endl;
     int movesDone = 0;
     int movesTotal = 100000;
     constexpr int movesTotal = 10000;
     int triangles[movesTotal];
     for (int i = 0; i < movesTotal; ++i) {
         if (chain.doMove())
             ++movesDone;
         triangles[i] = chain.g.countTriangles();
         if (i % (movesTotal / 50) == (movesTotal / 50 - 1))
             outfile << ',' << chain.g;
+    }
     outfile << '}';
     outfile << '}' << ',' << '{' << triangles[0];
     for (int i = 1; i < movesTotal; ++i)
         outfile << ',' << triangles[i];
     outfile << '}' << '}';
     std::cout << movesDone << '/' << movesTotal << " moves succeeded."
               << std::endl;

0 comments (0 inline, 0 general)