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

Changeset - 2c86fdd4152e

Parent rev.

Child rev.

[Not reviewed]

2 5 3

Tom Bannink - 8 years ago 2017-07-10 18:38:29
tombannink@gmail.com

Add start of ccm time evol

9 files changed with 336 insertions and 128 deletions:

cpp/Makefile

cpp/graph_ccm.hpp

cpp/switchchain.cpp

cpp/switchchain_ccm_initialtris.cpp

150

cpp/switchchain_ccm_timeevol.cpp

154

cpp/switchchain_initialtris.cpp

115

cpp/switchchain_spectrum.cpp

plots/triangle_exponent.pdf

bin+mod

triangle_exponent_plots.m

0 comments (0 inline, 0 general)

cpp/Makefile

➞

Show inline comments

@@ @@ -12,10 +12,11 @@ CXXFLAGS += -Wno-int-in-bool-context @@
 TARGETS += switchchain
 TARGETS += switchchain_canonical_properties
 TARGETS += switchchain_ccm_initialtris
 TARGETS += switchchain_ccm_timeevol
 TARGETS += switchchain_properties
 TARGETS += switchchain_exponent
 TARGETS += switchchain_exponent_new
 TARGETS += switchchain_initialtris
 TARGETS += switchchain_mixingtime
 TARGETS += switchchain_spectrum
 TARGETS += switchchain_successrates

cpp/graph_ccm.hpp

➞

Show inline comments

@@ file renamed from cpp/graph_gcm.hpp to cpp/graph_ccm.hpp @@
@@ @@ -10,7 +10,7 @@ @@
 // method2 = true  -> take highest degree and finish its pairing completely
 // method2 = false -> take new highest degree after every pairing
 template <typename RNG>
-bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, RNG& rng, bool method2) {
+bool constrainedConfigurationModel(DegreeSequence& ds, Graph& g, RNG& rng, bool method2) {
     // Similar to Havel-Hakimi but instead of pairing up with the highest ones
     // that remain, simply pair up with random ones
     unsigned int n = ds.size();
             return false;
         if (dmax == 0) {
-            std::cerr << "ERROR 1 in GCM.\n";
+            std::cerr << "ERROR 1 in CCM.\n";
+        }
         unsigned int u = uIter->second;
             auto vIter = degrees.begin();
             while (dmax--) {
                 if (vIter->first == 0)
-                    std::cerr << "ERROR in GCM2.\n";
+                    std::cerr << "ERROR in CCM2.\n";
                 if (!g.addEdge({u, vIter->second}))
-                    std::cerr << "ERROR. Could not add edge in GCM2.\n";
+                    std::cerr << "ERROR. Could not add edge in CCM2.\n";
                 vIter->first--;
                 if (vIter->first == 0)
                     vIter = degrees.erase(vIter);
             auto vIter = available[distr(rng)];
             // pair u to v
             if (vIter->first == 0)
-                std::cerr << "ERROR 2 in GCM1.\n";
+                std::cerr << "ERROR 2 in CCM1.\n";
             if (!g.addEdge({u, vIter->second}))
-                std::cerr << "ERROR. Could not add edge in GCM1.\n";
+                std::cerr << "ERROR. Could not add edge in CCM1.\n";
             // Purge anything with degree zero
             // Be careful with invalidating the other iterator!
             // Degree of u is always greater or equal to the degree of v

cpp/switchchain.cpp

➞

Show inline comments

 #include "switchchain.hpp"
 #include "exports.hpp"
 #include "graph.hpp"
-#include "graph_gcm.hpp"
+#include "graph_ccm.hpp"
 #include "graph_powerlaw.hpp"
 #include "graph_spectrum.hpp"
 #include <algorithm>

cpp/switchchain_ccm_initialtris.cpp

➞

Show inline comments

@@ new file 100644 @@
 #include "exports.hpp"
 #include "graph.hpp"
 #include "graph_ccm.hpp"
 #include "graph_powerlaw.hpp"
 #include "switchchain.hpp"
 #include <algorithm>
 #include <fstream>
 #include <iostream>
 #include <numeric>
 #include <random>
 #include <vector>
 int main(int argc, char* argv[]) {
     // Simulation parameters
     const int numVerticesMin = 200;
     const int numVerticesMax = 2000;
     const int numVerticesStep = 400;
     float tauValues[] = {2.1f, 2.2f, 2.3f, 2.4f, 2.5f, 2.6f, 2.7f, 2.8f, 2.9f};
     //float tauValues[] = {2.1f, 2.3f, 2.5f, 2.7f, 2.9f};
     const int totalDegreeSamples = 200;
     auto getMixingTime = [](int n, float tau) {
         return int(50.0f * (50.0f - 30.0f * (tau - 2.0f)) * n);
     };
     auto getMeasurements = [](int n, float tau) {
         (void)n;
         (void)tau;
         return 100;
     };
     auto getMeasureSkip = [](int n, float tau) {
         (void)tau;
         return 10 * n; // Take a sample every ... steps
     };
     // Output file
     std::ofstream outfile;
     if (argc >= 2)
         outfile.open(argv[1]);
     else
         outfile.open("graphdata_ccm_initialtris.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 << "measurements: 100\n";
     outfile << "measureSkip: 10 n\n";
     outfile << "data:\n";
     outfile << "1: {n,tau}\n";
     outfile << "2: avgTriangles\n";
     outfile << "3: {ccmTris1, ccmsrate1} \n";
     outfile << "4: {ccmTris2, ccmsrate2} \n";
     outfile << "*)" << std::endl;
     // Mathematica does not accept normal scientific notation
     outfile << std::fixed;
     outfile << '{';
     bool outputComma = false;
     std::mt19937 rng(std::random_device{}());
     Graph g;
     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 < totalDegreeSamples;
                  ++degreeSample) {
                 DegreeSequence ds;
                 generatePowerlawGraph(numVertices, tau, g, ds, rng);
                 std::cout << "Running (n,tau) = (" << numVertices << ',' << tau
                           << "). " << std::flush;
                 //
                 // Test the GCM1 and GCM2 success rate
                 //
                 long long gcmTris1 = 0;
                 long long gcmTris2 = 0;
                 int successrate1 = 0;
                 int successrate2 = 0;
                 for (int i = 0; i < 100; ++i) {
                     Graph gtemp;
                     // Take new highest degree every time
                     if (constrainedConfigurationModel(ds, gtemp, rng, false)) {
                         ++successrate1;
                         gcmTris1 += gtemp.countTriangles();
+                    }
                     // Finish all pairings of highest degree first
                     if (constrainedConfigurationModel(ds, gtemp, rng, true)) {
                         ++successrate2;
                         gcmTris2 += gtemp.countTriangles();
+                    }
+                }
                 SwitchChain chain;
                 if (!chain.initialize(g)) {
                     std::cerr << "Could not initialize Markov chain.\n";
                     return 1;
+                }
                 long long trianglesTotal = 0;
                 std::cout << " Finished CCM generation." << std::flush;
                 int mixingTime = getMixingTime(numVertices, tau);
                 for (int i = 0; i < mixingTime; ++i) {
                     chain.doMove();
+                }
                 chain.g.getTrackedTriangles() = chain.g.countTriangles();
                 int measurements = getMeasurements(numVertices, tau);
                 int measureSkip = getMeasureSkip(numVertices, tau);
                 for (int i = 0; i < measurements; ++i) {
                     for (int j = 0; j < measureSkip; ++j)
                         chain.doMove(true);
                     trianglesTotal += chain.g.getTrackedTriangles();
+                }
                 std::cout << " Finished mixing and measurements." << std::flush;
                 if (outputComma)
                     outfile << ',' << '\n';
                 outputComma = true;
                 float avgTriangles =
                     float(trianglesTotal) / float(measurements);
                 outfile << '{';
                 outfile << '{' << numVertices << ',' << tau << '}';
                 outfile << ',' << avgTriangles;
                 outfile << ',' << '{' << gcmTris1 << ',' << successrate1 << '}';
                 outfile << ',' << '{' << gcmTris2 << ',' << successrate2 << '}';
                 outfile << '}' << std::flush;
                 std::cout << std::endl;
+            }
+        }
+    }
     outfile << '}';
     return 0;
+}

cpp/switchchain_ccm_timeevol.cpp

➞

Show inline comments

@@ new file 100644 @@
 #include "exports.hpp"
 #include "graph.hpp"
 #include "graph_ccm.hpp"
 #include "graph_powerlaw.hpp"
 #include "switchchain.hpp"
 #include <algorithm>
 #include <fstream>
 #include <iostream>
 #include <numeric>
 #include <random>
 #include <vector>
 int main(int argc, char* argv[]) {
     // Simulation parameters
     const int numVerticesMin = 1000;
     const int numVerticesMax = 1000;
     const int numVerticesStep = 1000;
     //float tauValues[] = {2.1f, 2.2f, 2.3f, 2.4f, 2.5f, 2.6f, 2.7f, 2.8f, 2.9f};
     float tauValues[] = {2.1f, 2.3f, 2.5f, 2.7f, 2.9f};
     const int totalDegreeSamples = 10;
     auto getMixingTime = [](int n, float tau) {
         return int(1.0f * (50.0f - 10.0f * (tau - 2.0f)) * n);
     };
     // Output file
     std::ofstream outfile;
     if (argc >= 2)
         outfile.open(argv[1]);
     else
         outfile.open("graphdata_ccm_timeevol.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 << "canonical ds" << std::endl;
     outfile << "mixingTime: 0.5 * (50 - 10 (tau - 2)) n\n";
     outfile << "measurements: full time evol\n";
     outfile << "data:\n";
     outfile << "1: {n,tau}\n";
     outfile << "2: edges\n";
     outfile << "3: HH triangle seq\n";
     outfile << "4: {ccm1 failed attempts, triangle seq}\n";
     outfile << "5: {ccm2 failed attempts, triangle seq}\n";
     outfile << "*)" << std::endl;
     // Mathematica does not accept normal scientific notation
     outfile << std::fixed;
     outfile << '{' << '\n';
     bool outputComma = false;
     std::mt19937 rng(std::random_device{}());
     Graph g;
     for (int numVertices = numVerticesMin; numVertices <= numVerticesMax;
          numVertices += numVerticesStep) {
         for (float tau : tauValues) {
             int mixingTime = getMixingTime(numVertices, tau);
             // For a single n,tau take samples over several instances of
             // the degree distribution.
             for (int degreeSample = 0; degreeSample < totalDegreeSamples;
                  ++degreeSample) {
                 DegreeSequence ds;
                 //generatePowerlawGraph(numVertices, tau, g, ds, rng);
                 generateCanonicalPowerlawGraph(numVertices, tau, g, ds);
                 std::cout << "Running (n,tau) = (" << numVertices << ',' << tau
                           << "). " << std::flush;
                 SwitchChain chain;
                 if (!chain.initialize(g, true)) {
                     std::cerr << "Could not initialize Markov chain.\n";
                     return 1;
+                }
                 std::vector<int> triangleSeq(mixingTime);
                 for (int i = 0; i < mixingTime; ++i) {
                     chain.doMove(true);
                     triangleSeq[i] = chain.g.getTrackedTriangles();
+                }
                 std::cout << " Finished HH time evol." << std::flush;
                 if (outputComma)
                     outfile << ',' << '\n';
                 outputComma = true;
                 outfile << '{';
                 outfile << '{' << numVertices << ',' << tau << '}';
                 outfile << ',' << g.edgeCount();
                 outfile << ',' << triangleSeq;
                 for (int ccmType = 1; ccmType <= 2; ++ccmType) {
                     bool ccmMethod = (ccmType == 1 ? false : true);
 #if 0
                     outfile << ',' << '{';
                     for (int i = 0; i < 10; ++i) {
                         if (i != 0)
                             outfile << ',';
                         Graph gtemp;
                         if (constrainedConfigurationModel(ds, gtemp, rng,
                                                           ccmMethod)) {
                             chain.initialize(gtemp, true);
                             for (int i = 0; i < mixingTime; ++i) {
                                 chain.doMove(true);
                                 triangleSeq[i] = chain.g.getTrackedTriangles();
+                            }
                             outfile << triangleSeq;
                         } else {
                             outfile << '{' << '}';
+                        }
+                    }
                     outfile << '}';
 #endif
                     bool failed = true;
                     for (int i = 0; i < 50; ++i) {
                         Graph gtemp;
                         if (constrainedConfigurationModel(ds, gtemp, rng,
                                                           ccmMethod)) {
                             chain.initialize(gtemp, true);
                             for (int i = 0; i < mixingTime; ++i) {
                                 chain.doMove(true);
                                 triangleSeq[i] = chain.g.getTrackedTriangles();
+                            }
                             outfile << ',' << '{' << i << ',' << triangleSeq << '}';
                             failed = false;
                             break;
+                        }
+                    }
                     if (failed)
                         outfile << ",{50,{}}";
+                }
                 outfile << '}' << std::flush;
                 std::cout << " Finished CCM time evols." << std::flush;
                 std::cout << std::endl;
+            }
+        }
+    }
     outfile << '\n' << '}';
     return 0;
+}

cpp/switchchain_initialtris.cpp

➞

Show inline comments

deleted file

cpp/switchchain_spectrum.cpp

➞

Show inline comments

 #include "switchchain.hpp"
 #include "exports.hpp"
 #include "graph.hpp"
-#include "graph_gcm.hpp"
+#include "graph_ccm.hpp"
 #include "graph_spectrum.hpp"
 #include "graph_powerlaw.hpp"
 #include <algorithm>

plots/triangle_exponent.pdf

➞

Show inline comments

binary diff not shown

triangle_exponent_plots.m

➞

Show inline comments

@@ @@ -20,11 +20,17 @@ Needs["ErrorBarPlots`"] @@
 (* graphdata_exponent_highN.m *)
 (* graphdata_properties2.m *)
 (* graphdata_canonical_properties.m *)
-gsraw=Import[NotebookDirectory[]<>"data/graphdata_exponent_mix32.m"];
+gsraw=Import[NotebookDirectory[]<>"data/graphdata_exponent_hightau.m"];
 gsraw=SortBy[gsraw,#[[1,1]]&]; (* Sort by n *)
 averagesGrouped=GatherBy[gsraw,{#[[1,2]]&,#[[1,1]]&}];
 gsraw2=Import[NotebookDirectory[]<>"data/graphdata_canonical_properties2.m"];
 gsraw2=SortBy[gsraw2,#[[1,1]]&]; (* Sort by n *)
 averagesGrouped2=GatherBy[gsraw2,{#[[1,2]]&,#[[1,1]]&}];
 canonicalDatapoints=Map[{#[[1,1,1]],Mean[#[[All,2]]]}&,averagesGrouped2,{2}];
 (* averagesGrouped[[ tau index, n index, run index , {ntau, avgtri} ]] *)
 nlabels=Map["n = "<>ToString[#]&,averagesGrouped[[1,All,1,1,1]]];
 taulabels=Map["tau = "<>ToString[#]&,averagesGrouped[[All,1,1,1,2]]];
@@ @@ -61,6 +67,10 @@ mediansFits=Map[Fit[#,{1,logn},logn]&,mediansLoglogdata]; @@
 mediansFitsExtra=Map[LinearModelFit[#,logn,logn]&,mediansLoglogdata];
 canonicalloglogdata=Log[canonicalDatapoints[[All,nRange]]];
 canonicalFitsExtra=Map[LinearModelFit[#,logn,logn]&,canonicalloglogdata];
 averagesFitsExtra[[1]]["ParameterConfidenceIntervalTable"]
 averagesFitsExtra[[1]]["BestFitParameters"]
 averagesFitsExtra[[1]]["ParameterErrors"]
 (* For visual, shift the tau values slightly left or right to distinguish the two datasets *)
 tauValues=averagesGrouped[[All,1,1,1,2]];
 averagesExponentsErrorBars=Map[{{#[[1]],#[[2]]["BestFitParameters"][[2]]},ErrorBar[#[[2]]["ParameterConfidenceIntervals"][[2]]-#[[2]]["BestFitParameters"][[2]]]}&,
-Transpose[{tauValues-0.001,averagesFitsExtra}]];
+Transpose[{tauValues-0.003,averagesFitsExtra}]];
 mediansExponentsErrorBars=Map[{{#[[1]],#[[2]]["BestFitParameters"][[2]]},ErrorBar[#[[2]]["ParameterConfidenceIntervals"][[2]]-#[[2]]["BestFitParameters"][[2]]]}&,
 Transpose[{tauValues+0.001,mediansFitsExtra}]];
 plot2=Show[ErrorListPlot[{averagesExponentsErrorBars,mediansExponentsErrorBars},Joined->True,PlotMarkers->Automatic,Frame->True,FrameLabel->{"tau","triangle exponent"},PlotRange->{{2,3},{0,1.6}},ImageSize->300],Plot[3/2(3-tau),{tau,2,3},PlotStyle->{Dashed}]]
 Transpose[{tauValues+0.003,mediansFitsExtra}]];
 canonicalExponentsErrorBars=Map[{{#[[1]],#[[2]]["BestFitParameters"][[2]]},ErrorBar[#[[2]]["ParameterConfidenceIntervals"][[2]]-#[[2]]["BestFitParameters"][[2]]]}&,
 Transpose[{tauValues+0.000,canonicalFitsExtra}]];
 plot2=Show[
 ErrorListPlot[{averagesExponentsErrorBars,mediansExponentsErrorBars,canonicalExponentsErrorBars},
 Joined->True,PlotMarkers->Automatic,
 Frame->True,FrameLabel->{"tau","triangle exponent"},
 PlotRange->{{2,3},{0,1.6}},
 ImageSize->300],
 Plot[3/2(3-tau),{tau,2,3},PlotStyle->{Black,Dashed}]]
 Export[NotebookDirectory[]<>"plots/triangle_exponent.pdf",plot2]

0 comments (0 inline, 0 general)