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

Changeset - 257995a65b71

Parent rev.

Child rev.

[Not reviewed]

0 4 0

Tom Bannink - 8 years ago 2017-05-29 17:11:26
tombannink@gmail.com

Add plots of successrate over time

4 files changed with 94 insertions and 40 deletions:

cpp/Makefile

cpp/switchchain.cpp

cpp/switchchain_initialtris.cpp

triangle_analysis.m

0 comments (0 inline, 0 general)

cpp/Makefile

➞

Show inline comments

 #CXX=clang++
 INCLUDES += -I.
 CXXFLAGS += -std=c++14 -O3 -Wall -Wextra -Wfatal-errors -Wno-deprecated-declarations $(INCLUDES)
+CXXFLAGS += -std=c++14 -O3 -Wall -Wextra -Wfatal-errors -Werror -pedantic -Wno-deprecated-declarations $(INCLUDES)
 all: switchchain switchchain_exponent switchchain_initialtris

cpp/switchchain.cpp

➞

Show inline comments

@@ @@ -73,8 +73,8 @@ void getTriangleDegrees(const Graph& g) { @@
             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::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);
+                }
@@ @@ -90,7 +90,8 @@ void getTriangleDegrees(const Graph& g) { @@
 //
 // 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) {
 template <typename RNG>
 bool greedyConfigurationModel(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 true;
+}
 int main() {
+int main(int argc, char* argv[]) {
     // Generate a random degree sequence
     std::mt19937 rng(std::random_device{}());
@@ @@ -209,11 +210,22 @@ int main() { @@
     Graph g1;
     Graph g2;
     std::ofstream outfile("graphdata.m");
     std::ofstream outfile;
     if (argc >= 2)
         outfile.open(argv[1]);
     else
         outfile.open("graphdata.m");
     if (!outfile.is_open()) {
         std::cout << "ERROR: Could not open output file.\n";
         return 1;
+    }
     outfile << '{';
     bool outputComma = false;
-    for (int numVertices = 200; numVertices <= 2000; numVertices += 400) {
+    for (int numVertices = 500; numVertices <= 500; numVertices += 1000) {
         for (float tau : tauValues) {
             DegreeSequence ds(numVertices);
@@ @@ -223,7 +235,7 @@ int main() { @@
             // 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 < 1; ++degreeSample) {
+            for (int degreeSample = 0; degreeSample < 5; ++degreeSample) {
                 // Generate a graph
                 // might require multiple tries
                 for (int i = 1; ; ++i) {
@@ @@ -247,6 +259,7 @@ int main() { @@
+                    }
+                }
 #if 0
                 //
                 // Test the GCM1 and GCM2 success rate
                 //
@@ @@ -269,6 +282,9 @@ int main() { @@
                         g2 = gtemp;
+                    }
+                }
 #endif
                 for (int i = 1; i < 5; ++i) {
                 SwitchChain chain;
                 if (!chain.initialize(g)) {
@@ @@ -276,17 +292,6 @@ int main() { @@
                     return 1;
+                }
                 SwitchChain chain1, chain2;
                 bool do1 = true, do2 = true;
                 if (!chain1.initialize(g1)) {
                     std::cerr << "Could not initialize Markov chain.\n";
                     do1 = false;
+                }
                 if (!chain2.initialize(g2)) {
                     std::cerr << "Could not initialize Markov chain.\n";
                     do2 = false;
+                }
                 std::cout << "Running n = " << numVertices << ", tau = " << tau
                           << ". \t" << std::flush;
@@ @@ -299,27 +304,40 @@ int main() { @@
                 constexpr int measureSkip = 1;
                 int movesDone = 0;
                 int movesTotal = 0;
                 int movesSuccess = 0;
                 int triangles[measurements];
                 for (int i = 0; i < mixingTime; ++i) {
                     if (chain.doMove())
                         ++movesDone;
                     ++movesTotal;
                     if (chain.doMove()) {
                         ++movesSuccess;
+                    }
+                }
                 std::vector<int> successRates;
                 successRates.reserve(measurements * measureSkip);
                 int successrate = 0;
                 for (int i = 0; i < measurements; ++i) {
                     for (int j = 0; j < measureSkip; ++j)
                         if (chain.doMove())
                             ++movesDone;
                     for (int j = 0; j < measureSkip; ++j) {
                         ++movesTotal;
                         if (chain.doMove()) {
                             ++movesSuccess;
                             ++successrate;
+                        }
+                    }
                     triangles[i] = chain.g.countTriangles();
                     if ((i+1) % 100 == 0) {
                         successRates.push_back(successrate);
                         successrate = 0;
+                    }
+                }
                 std::cout << movesDone << '/' << mixingTime + measurements * measureSkip
                           << " moves succeeded ("
                           << 100.0f * float(movesDone) /
                                  float(mixingTime + measurements * measureSkip)
                           << "%).";
                 std::cout << '('
                           << 100.0f * float(movesSuccess) / float(movesTotal)
                           << "% successrate). " << std::flush;
                 // std::cout << std::endl;
                 if (outputComma)
@@ @@ -330,10 +348,12 @@ int main() { @@
                 outfile << '{' << '{' << numVertices << ',' << tau << '}';
                 outfile << ',' << triangles;
                 outfile << ',' << ds;
 #if 0
                 outfile << ',' << greedyTriangles1;
                 outfile << ',' << greedyTriangles2;
                 if (do1) {
                 SwitchChain chain1, chain2;
                 if (chain1.initialize(g1)) {
                     movesDone = 0;
                     SwitchChain& c = chain1;
                     for (int i = 0; i < mixingTime; ++i) {
@@ @@ -355,7 +375,7 @@ int main() { @@
                     outfile << ',' << triangles;
+                }
-                if (do2) {
+                if (chain2.initialize(g2)) {
                     movesDone = 0;
                     SwitchChain& c = chain2;
                     for (int i = 0; i < mixingTime; ++i) {
@@ @@ -377,6 +397,9 @@ int main() { @@
                     outfile << ',' << triangles;
+                }
 #endif
                 outfile << ',' << successRates;
                 outfile << '}' << std::flush;
@@ @@ -384,6 +407,7 @@ int main() { @@
+                }
+            }
+        }
+    }
     outfile << '}';
     return 0;
+}

cpp/switchchain_initialtris.cpp

➞

Show inline comments

@@ @@ -68,7 +68,8 @@ class SwitchChain { @@
 //
 // 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) {
 template <typename RNG>
 bool greedyConfigurationModel(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();

triangle_analysis.m

➞

Show inline comments

@@ @@ -71,7 +71,7 @@ Needs["ErrorBarPlots`"] @@
 (*Data import*)
-gsraw=Import[NotebookDirectory[]<>"data/graphdata_partial.m"];
+gsraw=Import[NotebookDirectory[]<>"data/graphdata_temp2.m"];
 (* gsraw=SortBy[gsraw,{#[[1,1]]&,#[[1,2]]&}]; (* Sort by n and then by tau. The {} forces a *stable* sort because otherwise Mathematica sorts also on triangle count and other things. *) *)
 (*Plot triangle count over "time" in Markov chain instances*)
 numPlots=20;
 selectedData=gdata[[4,-1]][[-numPlots;;-1]];
 numPlots=10;
 selectedData=gdata[[1,-1]][[-numPlots;;-1]];
 measureSkip=1;
 minCount=Min[Map[Min[#[[2]]]&,selectedData]];
 maxCount=Max[Map[Max[#[[2]]]&,selectedData]];
 maxTime=Max[Map[Length[#[[2]]]&,selectedData]];
 skipPts=Max[1,Round[maxTime/200]]; (* Plotting every point is slow. Plot only once per `skipPts` timesteps *)
 coarseData=Map[#[[2,1;;-1;;skipPts]]&,selectedData];
 maxTime=30000;
 skipPts=Max[1,Round[maxTime/400]]; (* Plotting every point is slow. Plot only once per `skipPts` timesteps *)
 coarseData=Map[#[[2,1;;maxTime;;skipPts]]&,selectedData];
 labels=Map["{n,tau} = "<>ToString[#[[1]]]&,selectedData];
 ListPlot[coarseData,Joined->True,PlotRange->{minCount,maxCount},DataRange->{0,measureSkip*maxTime},PlotLegends->labels]
+ListPlot[coarseData,Joined->True,PlotRange->{0*minCount,maxCount},DataRange->{0,measureSkip*maxTime},PlotLegends->labels]
 (* Map[ListPlot[#,Joined->True,PlotRange\[Rule]{minCount,maxCount},DataRange\[Rule]{0,maxTime}]&,coarseData] *)
 (* ::Subsection:: *)
 (*Plot success rate over "time"*)
 numPlots=10;
 selectedData=gdata[[1,-1]][[-numPlots;;-1]];
 measureSkip=100;
 maxTime=Max[Map[Length[#[[4]]]&,selectedData]];
 maxTime=10000;
 coarseData=Map[#[[4,1;;maxTime/measureSkip]]&,selectedData];
 labels=Map["{n,tau} = "<>ToString[#[[1]]]&,selectedData];
 ListPlot[coarseData,Joined->True,PlotRange->{0,100},DataRange->{0,maxTime},PlotLegends->labels]
 (* Map[ListPlot[#,Joined->True,PlotRange\[Rule]{minCount,maxCount},DataRange\[Rule]{0,maxTime}]&,coarseData] *)
 (* ::Subsection:: *)
 (*Correlation of avgsuccess rate vs other things*)
 compare1=Map[{Mean[#[[4]]],Mean[#[[2]]]}&,gdata,{3}];
 (* { GCM1 rate, GCM2 rate, mixing time from ErdosGallai } *)
 scatterPlots=Map[ListPlot[#,PlotRange->{{0,100},All},PlotStyle->PointSize[Large]]&,compare1,{2}];
 TableForm[scatterPlots,TableHeadings->{taulabels,nlabels}]
 (* ::Subsection:: *)
 (*Compute 'mixing time'*)

0 comments (0 inline, 0 general)