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

Changeset - efc6996e97a2

Parent rev.

Child rev.

[Not reviewed]

0 2 0

Tom Bannink - 8 years ago 2017-03-13 17:28:41
tom.bannink@cwi.nl

Add adaptive mixing time

2 files changed with 49 insertions and 22 deletions:

cpp/switchchain.cpp

showgraphs.m

0 comments (0 inline, 0 general)

cpp/switchchain.cpp

➞

Show inline comments

@@ @@ -33,27 +33,23 @@ class SwitchChain { @@
         edgeDistribution.param(
             std::uniform_int_distribution<>::param_type(0, g.edgeCount() - 1));
         return true;
+    }
     bool doMove() {
         Edge e1, e2;
         int e1index, e2index;
         int timeout = 0;
         // Keep regenerating while conflicting edges
         do {
             e1index = edgeDistribution(mt);
             e2index = edgeDistribution(mt);
             e1 = g.getEdge(e1index);
             e2 = g.getEdge(e2index);
             ++timeout;
             if (timeout % 100 == 0) {
             if (++timeout % 100 == 0) {
                 std::cerr << "Warning: sampled " << timeout
                           << " random edges but they keep conflicting.\n";
+            }
-        } while (edgeConflicts(e1, e2));
+        } while (edgeConflicts(g.getEdge(e1index), g.getEdge(e2index)));
         // Consider one of the three possible permutations
         // 1) e1.u - e1.v and e2.u - e2.v (original)
         // 2) e1.u - e2.u and e1.v - e2.v
         // 3) e1.u - e2.v and e1.v - e2.u
         bool switchType = permutationDistribution(mt);
@@ @@ -114,35 +110,36 @@ int main() { @@
                     return 1;
+                }
                 std::cout << "Running n = " << numVertices << ", tau = " << tau
                           << ". \t" << std::flush;
                 constexpr int mixingTime = 40000;
                 constexpr int measureTime = 20000;
                 int mixingTime = (32.0f - 26.0f*(tau - 2.0f)) * numVertices; //40000;
                 constexpr int measurements = 50;
                 constexpr int measureSkip =
 ; // Take a sample every ... steps
                 constexpr int measurements =
                     (measureTime - 1) / measureSkip + 1;
                 int movesDone = 0;
                 int triangles[measurements];
                 for (int i = 0; i < mixingTime; ++i) {
                     if (chain.doMove())
                         ++movesDone;
+                }
                 for (int i = 0; i < measureTime; ++i) {
                 for (int i = 0; i < measurements; ++i) {
                     for (int j = 0; j < measureSkip; ++j)
                         if (chain.doMove())
                             ++movesDone;
                     if (i % measureSkip == 0)
                         triangles[i / measureSkip] = chain.g.countTriangles();
                     triangles[i] = chain.g.countTriangles();
+                }
                 std::cout << movesDone << '/' << mixingTime + measureTime
                           << " moves succeeded." << std::endl;
                 std::cout << movesDone << '/' << mixingTime + measurements * measureSkip
                           << " moves succeeded ("
                           << 100.0f * float(movesDone) /
                                  float(mixingTime + measurements * measureSkip)
                           << "%)." << std::endl;
                 if (outputComma)
                     outfile << ',';
                 outputComma = true;
                 std::sort(ds.begin(), ds.end());

showgraphs.m

➞

Show inline comments

@@ @@ -61,13 +61,13 @@ Grid[Partition[gs,10],Frame->All] @@
 (* ::Subsection:: *)
 (*Data import and data merge*)
-gsraw=Import[NotebookDirectory[]<>"data/graphdata_merged.m"];
+gsraw=Import[NotebookDirectory[]<>"data/graphdata2.m"];
 gsraw=SortBy[gsraw,#[[1,1]]&]; (* Sort by n *)
 gdata=GatherBy[gsraw,{#[[1,2]]&,#[[1,1]]&}];
 (* gdata[[ tau index, n index, run index , {ntau, #tris, ds} ]] *)
@@ @@ -106,51 +106,81 @@ tmp=Table[1.-Exp[-ds[[i]]ds[[j]]],{i,1,n-1},{j,i+1,n}]; @@
 Sum[tmp[[i,j-i]]*tmp[[j,k-j]]*tmp[[i,k-i]],{i,1,n-2},{j,i+1,n-1},{k,j+1,n}]
 *)
 ];
 (* gdata[[ tau index, n index, run index , {ntau, #tris, ds} ]] *)
-avgAndProp=ParallelMap[{getProperty[#[[3]]],Mean[#[[2,1;;-1]]]}&,gdata[[2,4,1;;100]]];
+avgAndProp=ParallelMap[{getProperty[#[[3]]],Mean[#[[2,1;;-1]]]}&,gdata[[2,2,1;;100]]];
 Show[ListPlot[avgAndProp,AxesOrigin->{0,0},AxesLabel->{"degree-sequence-property","<#triangles>"},AspectRatio->1],Plot[x,{x,1,1000}]]
 (* ::Subsection:: *)
 (*Plot triangle count over "time" in Markov chain instances*)
 numPlots=20;
-selectedData=gsraw[[-numPlots;;-1]];
+selectedData=gdata[[5,-1]][[-numPlots;;-1]];
 minCount=Min[Map[Min[#[[2]]]&,selectedData]];
 maxCount=Max[Map[Max[#[[2]]]&,selectedData]];
 maxTime=Max[Map[Length[#[[2]]]&,selectedData]];
 skipPts=Max[1,Round[maxTime/100]]; (* Plotting every point is slow. Plot only once per `skipPts` timesteps *)
 coarseData=Map[#[[2,1;;-1;;skipPts]]&,selectedData];
 labels=Map["{n,tau} = "<>ToString[#[[1]]]&,selectedData];
 ListPlot[coarseData,Joined->True,PlotRange->{minCount,maxCount},DataRange->{0,maxTime},PlotLegends->labels]
+ListPlot[coarseData,Joined->True,PlotRange->{minCount,maxCount},DataRange->{0,200*maxTime},PlotLegends->labels]
 (* Map[ListPlot[#,Joined->True,PlotRange\[Rule]{minCount,maxCount},DataRange\[Rule]{0,maxTime}]&,coarseData] *)
 (* ::Subsection:: *)
 (*Compute 'mixing time'*)
 (* Compute average of last part and check when the value drops below that for the first time *)
 getMixingTime[values_]:=Module[{avg},
     (* average over the last 20 percent *)
     avg=Mean[values[[-Round[Length[values]/5];;-1]]];
     FirstPosition[values,_?(#<=avg&)][[1]]
+]
 (* gdata[[ tau index, n index, run index , {ntau, #tris, ds} ]] *)
 mixingTimes=Map[{#[[1,1]],(1/#[[1,1]])200 * getMixingTime[#[[2]]]}&,gdata,{3}];
 mixingTimesBars=Map[
     {{#[[1,1]],Mean[#[[All,2]]]},ErrorBar[StandardDeviation[#[[All,2]]]/Sqrt[Length[#]]]}&
 ,mixingTimes,{2}];
 ErrorListPlot[mixingTimesBars,Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","~~mixing time divided by n"},PlotLegends->taulabels]
 (* For n fixed, look at function of tau *)
 mixingTimes=Map[{#[[1,2]],(1/#[[1,1]])200 * getMixingTime[#[[2]]]}&,gdata,{3}];
 mixingTimesBars=Map[
     {{#[[1,1]],Mean[#[[All,2]]]},ErrorBar[StandardDeviation[#[[All,2]]]]}&
 ,mixingTimes[[All,-1]],{1}];
 Show[
 ErrorListPlot[mixingTimesBars,Joined->True,PlotMarkers->Automatic,AxesLabel->{"tau","~~mixing time divided by n, for n = 1000"},PlotRange->{{2,3},{0,30}}]
 ,Plot[(32-26(tau-2)),{tau,2,3}]]
 (* ::Subsection:: *)
 (*Plot average #triangles vs n*)
 averages=Map[{#[[1]],Mean[#[[2,1;;-1]]]}&,gsraw];
 (* averages=SortBy[averages,#[[1,1]]&]; (* Sort by n *) *)
 averagesGrouped=GatherBy[averages,{#[[1,2]]&,#[[1,1]]&}]; (* Split by n,tau *)
 (* 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]]];
 averagesErrorBars=Map[
 {{#[[1,1,1]],Mean[#[[All,2]]]},
-ErrorBar[StandardDeviation[#[[All,2]]]/Sqrt[Length[#]]]
 ErrorBar[StandardDeviation[#[[All,2]]]]
 }&,averagesGrouped,{2}];
 ErrorListPlot[averagesErrorBars,Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels]
+ErrorListPlot[averagesErrorBars,Joined->True,PlotMarkers->Automatic,PlotRange->All,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels]
 ListLogLogPlot[averagesErrorBars[[All,All,1]],Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels]
 (* ::Subsection:: *)
@@ @@ -163,13 +193,13 @@ fits=Map[Fit[#,{1,logn},logn]&,loglogdata]; @@
 Show[ListLogLogPlot[averagesErrorBars[[All,All,1]],PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels],Plot[fits,{logn,1,2000}]]
 tauValues=averagesGrouped[[All,1,1,1,2]];
 exponents=Transpose[{tauValues,fits[[All,2,1]]}];
 Show[ListPlot[exponents,Joined->True,PlotMarkers->Automatic,AxesLabel->{"tau","triangle-law-exponent"}],Plot[3/2(3-tau),{tau,2,3}]]
+Show[ListPlot[exponents,Joined->True,PlotMarkers->Automatic,AxesLabel->{"tau","triangle-law-exponent"},PlotRange->{{2,3},{0,1.6}}],Plot[3/2(3-tau),{tau,2,3}]]
 (* ::Subsection:: *)
 (*Plot #triangles distribution for specific (n,tau)*)

0 comments (0 inline, 0 general)