diff --git a/cpp/Makefile b/cpp/Makefile index 0a5064bf92997966049497679c05f956bc3607c8..3ad5ef833ea4c2af43b198f29dbf8238b17a74a1 100644 --- a/cpp/Makefile +++ b/cpp/Makefile @@ -14,6 +14,7 @@ TARGETS += switchchain TARGETS += switchchain_canonical_creationfreqs TARGETS += switchchain_canonical_mixingtime TARGETS += switchchain_canonical_properties +TARGETS += switchchain_canonical_timeevol TARGETS += switchchain_ccm_constructionrate TARGETS += switchchain_ccm_cputime TARGETS += switchchain_ccm_initialtris diff --git a/cpp/switchchain_canonical_mixingtime.cpp b/cpp/switchchain_canonical_mixingtime.cpp index 77d47dd39c6ae922e1b1a0b9f80c7e50052101a0..31e2ef690fde93856529d961936300272108b687 100644 --- a/cpp/switchchain_canonical_mixingtime.cpp +++ b/cpp/switchchain_canonical_mixingtime.cpp @@ -13,9 +13,9 @@ int main(int argc, char* argv[]) { // Simulation parameters - const int numVerticesMin = 2000; - const int numVerticesMax = 5000; - const int numVerticesStep = 1000; + const int numVerticesMin = 10000; + const int numVerticesMax = 20000; + const int numVerticesStep = 10000; float tauValues[] = {2.1f, 2.3f, 2.5f, 2.7f, 2.9f}; @@ -52,7 +52,7 @@ int main(int argc, char* argv[]) { outfile << "tauValues: " << tauValues << std::endl; outfile << "Canonical degree sequence.\n"; outfile << "sample runs: " << sampleRuns << std::endl; - outfile << "time stamps: {0.1 n, 0.2 n, ... , 20.0 n}\n"; + outfile << "time stamps: {0.2 n, 0.4 n, 0.6 n, ... , 40.0 n}\n"; outfile << "For uniform samples:\n"; outfile << "mixingTime: 50 * (50 - 5 (tau - 2)) n\n"; outfile << "measurements: 100000\n"; @@ -103,7 +103,7 @@ int main(int argc, char* argv[]) { outfile << '}'; #else std::vector> samples; - for (int i = 1; i <= 200; i++) { + for (int i = 2; i <= 400; i += 2) { samples.push_back({(i * numVertices / 10), Histogram()}); } diff --git a/cpp/switchchain_canonical_timeevol.cpp b/cpp/switchchain_canonical_timeevol.cpp new file mode 100644 index 0000000000000000000000000000000000000000..78b5bc39b054e639b348337144e75385b4c54bb4 --- /dev/null +++ b/cpp/switchchain_canonical_timeevol.cpp @@ -0,0 +1,89 @@ +#include "exports.hpp" +#include "graph.hpp" +#include "graph_powerlaw.hpp" +#include "graph_spectrum.hpp" +#include "histogram.hpp" +#include "switchchain.hpp" +#include +#include +#include +#include +#include +#include + +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.3f, 2.5f, 2.7f, 2.9f}; + + auto getMeasurements = [](int n, float tau) { + (void)n; + (void)tau; + return 50000; + }; + + // Output file + std::ofstream outfile; + if (argc >= 2) + outfile.open(argv[1]); + else + outfile.open("graphdata_canonical_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 << "Canonical degree sequence.\n"; + outfile << "10 runs per starting point.\n"; + outfile << "Measurements: 50000\n"; + outfile << "data:\n"; + outfile << "1: {n,tau}\n"; + outfile << "2: {triangles}\n"; + outfile << "*)" << std::endl; + + // Mathematica does not accept normal scientific notation + outfile << std::fixed; + outfile << '{' << '\n'; + bool outputComma = false; + + SwitchChain chain; + Graph g; + for (int numVertices = numVerticesMin; numVertices <= numVerticesMax; + numVertices += numVerticesStep) { + for (float tau : tauValues) { + DegreeSequence ds; + generateCanonicalPowerlawGraph(numVertices, tau, g, ds); + + std::cout << "Running (n,tau) = (" << numVertices << ',' << tau + << "). " << std::flush; + + for (int j = 0; j < 10; ++j) { + std::vector triangles; + chain.initialize(g, true); + int measurements = getMeasurements(numVertices, tau); + for (int i = 0; i < measurements; ++i) { + chain.doMove(true); + triangles.push_back(chain.g.getTrackedTriangles()); + } + + if (outputComma) + outfile << ',' << '\n'; + outputComma = true; + outfile << '{' << '{' << numVertices << ',' << tau << '}'; + outfile << ',' << triangles; + outfile << '}' << std::flush; + } + std::cout << std::endl; + } + } + outfile << '\n' << '}'; + return 0; +} diff --git a/triangle_canonical_mixingtime.m b/triangle_canonical_mixingtime.m index 08f52fab664f79e78f60d1b5a0117648398ddca5..542bbb0a3d715960df30a4debf1de7155d1a790c 100644 --- a/triangle_canonical_mixingtime.m +++ b/triangle_canonical_mixingtime.m @@ -1,6 +1,6 @@ (* ::Package:: *) -gsraw=Import[NotebookDirectory[]<>"data/graphdata_canonical_mixingtime_histogram.m"]; +gsraw=Import[NotebookDirectory[]<>"data/graphdata_canonical_mixingtime_histogram_merged.m"]; gdata=GatherBy[gsraw,{#[[1,2]]&}]; (* Data format: *) (* gdata[[ tau index, n index, datatype index ]] *) @@ -48,9 +48,10 @@ FrameLabel->{"triangles","probability"} ], ListPlot[normalize[run[[3]]],Joined->True,PlotRange->plotrange,PlotLegends->Placed[{"uniform"},Scaled[{0.7,0.7}]],PlotStyle->{Thick,Black}]]] -plot1=makeHistogram[gdata[[1,-1]],{{3500,7800},{0,0.005}},{10,50,100}] -plot2=makeHistogram2[gdata[[3,-1]],{{50,300},{0,0.04}},{10,20,30}] -plot3=makeHistogram2[gdata[[5,-1]],{{0,70},{0,0.18}},{5,10,20}] +plot1=makeHistogram[gdata[[1,5]],{{3500,7800},{0,0.005}},{10,50,100}] +plot2=makeHistogram2[gdata[[3,5]],{{50,300},{0,0.04}},{10,20,30}] +plot3=makeHistogram2[gdata[[5,5]],{{0,70},{0,0.18}},{5,10,20}] +plot4=makeHistogram[gdata[[1,-1]],Automatic,{50,100,150,200}] Export[NotebookDirectory[]<>"plots/triangle_distributions_over_time.pdf",plot2] @@ -79,8 +80,10 @@ m=Min[hist1[[1,1]],hist2[[1,1]]]; M=Max[hist1[[-1,1]],hist2[[-1,1]]]; probs=ConstantArray[0,M-m+1]; probs1=hist1[[All,2]]; +(* probs1=GaussianFilter[probs1,10]; (* test *) *) probs1=probs1/Total[probs1]; probs2=hist2[[All,2]]; +(* probs2=GaussianFilter[probs2,10]; (* test *) *) probs2=probs2/Total[probs2]; probs[[1+hist1[[1,1]]-m;;1+hist1[[-1,1]]-m]]+=probs1; probs[[1+hist2[[1,1]]-m;;1+hist2[[-1,1]]-m]]-=probs2; @@ -105,18 +108,20 @@ ratios=Map[getRatios,gdata,{2}]; (*Map[ListPlot[#[[All,2]],Joined->True,PlotMarkers->Automatic,PlotRange->(1+{-0.15,+0.15}),PlotLegends->#[[All,1]],ImageSize->300]&,ratios]*) (*Map[ListPlot[#[[All,3]],Joined->True,PlotMarkers->Automatic,PlotRange->(0+{-1,+1}),PlotLegends->#[[All,1]],ImageSize->300]&,ratios]*) *) -getTVDs[run_]:=Module[{scalefactor}, -scalefactor=1/(run[[1,1]]*Log[2,run[[1,1]]]^(1*(4-run[[1,2]]))); -{"\[Tau] = "<>ToString[run[[1,2]]], -Map[{#[[1]]*scalefactor,getTVDistance2[#[[2]],run[[3]]]}&,run[[2]]]} +getTVDs[run_]:=Module[{scaling}, +scaling[step_,n_,tau_]:=step/(n*Log[n]^(4-tau)); +{"n = "<>ToString[run[[1,1]]],"\[Tau] = "<>ToString[run[[1,2]]], +Map[{scaling[#[[1]],run[[1,1]],run[[1,2]]],getTVDistance2[#[[2]],run[[3]]]}&,run[[2]]]} ] TVDs=Map[getTVDs,gdata,{2}]; -Map[Show[ListPlot[#[[All,2]], +Map[Show[ListPlot[#[[All,3]], Joined->True,(*PlotMarkers->Automatic,*) -PlotLegends->#[[All,1]],ImageSize->500, -PlotRange->{0,1},Frame->True,FrameLabel->{"steps / (n (\!\(\*SubscriptBox[\(log\), \(2\)]\)n\!\(\*SuperscriptBox[\()\), \(4 - \[Tau]\)]\))","TV distance"}], +PlotLegends->Placed[#[[All,1]],Center],ImageSize->500, +PlotRange->{0,1},Frame->True,FrameLabel->{"steps / (n (\!\(\*SubscriptBox[\(log\), \(2\)]\)n\!\(\*SuperscriptBox[\()\), \(4 - \[Tau]\)]\))","TV distance"}, +PlotLabel->#[[1,2]] +], Plot[{0.1,0.05},{x,0,20},PlotStyle->Directive[Black,Dashed]] ]&,TVDs] @@ -139,8 +144,9 @@ While[i<=Length[run[[2]]], mixingtimes=Map[getMixingTime,gdata,{2}]; -scaling[n_,tau_]:=n*Log[n]^(4-tau); +scaling[n_,tau_]:=n*Log[2,n]^(4-tau); scaling[n_,tau_]:=n; +scaling[n_,tau_]:=n*Log[2,n]^1.5; plotData=Map[{#[[1]],#[[4]]/scaling[#[[1]],#[[2]]]}&,mixingtimes,{2}]~Join~Map[{#[[1]],#[[3]]/scaling[#[[1]],#[[2]]]}&,mixingtimes,{2}]; fillings={1->{6},2->{7},3->{8},4->{9},5->{10}}; taulabels=Map["\[Tau] = "<>ToString[#[[1,2]]]&,mixingtimes];