From 30d182b86860743472b29422419f63b3c9a71824 2017-08-21 17:49:26 From: Tom Bannink Date: 2017-08-21 17:49:26 Subject: [PATCH] Add better construction successrate measurement --- diff --git a/cpp/Makefile b/cpp/Makefile index e483772e885c75174db4c6d6fab570683d3d3803..37396bb2cfbd58c7594cefd0f8eb46ecec5a6fd9 100644 --- a/cpp/Makefile +++ b/cpp/Makefile @@ -12,6 +12,7 @@ CXXFLAGS += -Wno-int-in-bool-context TARGETS += switchchain TARGETS += switchchain_canonical_properties +TARGETS += switchchain_ccm_constructionrate TARGETS += switchchain_ccm_cputime TARGETS += switchchain_ccm_initialtris TARGETS += switchchain_ccm_timeevol diff --git a/cpp/switchchain_ccm_constructionrate.cpp b/cpp/switchchain_ccm_constructionrate.cpp new file mode 100644 index 0000000000000000000000000000000000000000..1c175afde41f9c7670c1c4b309223f2c7eb3b840 --- /dev/null +++ b/cpp/switchchain_ccm_constructionrate.cpp @@ -0,0 +1,107 @@ +#include "exports.hpp" +#include "graph.hpp" +#include "graph_ccm.hpp" +#include "graph_powerlaw.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 = 500; + + //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.5f, 2.9f}; + + const int totalDegreeSamples = 5000; + const int ccmConstructionAttemps = 200; + + // Output file + std::ofstream outfile; + if (argc >= 2) + outfile.open(argv[1]); + else + outfile.open("graphdata_ccm_constructionrate.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: -\n"; + outfile << "measurements: -\n"; + outfile << "measureSkip: -\n"; + outfile << "ccm construction attemps: " << ccmConstructionAttemps << std::endl; + outfile << "data:\n"; + outfile << "1: {n,tau}\n"; + outfile << "3: CCMdu construction rate \n"; + outfile << "4: CCMd construction rate \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 + // + int successrate1 = 0; + int successrate2 = 0; + for (int i = 0; i < ccmConstructionAttemps; ++i) { + Graph gtemp; + // Take new highest degree every time + if (constrainedConfigurationModel(ds, gtemp, rng, false)) { + ++successrate1; + } + // Finish all pairings of highest degree first + if (constrainedConfigurationModel(ds, gtemp, rng, true)) { + ++successrate2; + } + } + + std::cout << "Done." << std::flush; + + if (outputComma) + outfile << ',' << '\n'; + outputComma = true; + + outfile << '{'; + outfile << '{' << numVertices << ',' << tau << '}'; + outfile << ',' << float(successrate1)/float(ccmConstructionAttemps); + outfile << ',' << float(successrate2)/float(ccmConstructionAttemps); + outfile << '}' << std::flush; + + std::cout << std::endl; + } + } + } + outfile << '}'; + return 0; +} diff --git a/cpp/switchchain_ccm_initialtris.cpp b/cpp/switchchain_ccm_initialtris.cpp index bcd40b917141153b04c16f652d834e00c81c95d3..435181dcde762aeb587ad3c04117d08a924b1e1b 100644 --- a/cpp/switchchain_ccm_initialtris.cpp +++ b/cpp/switchchain_ccm_initialtris.cpp @@ -16,8 +16,8 @@ int main(int argc, char* argv[]) { const int numVerticesMax = 1000; const int numVerticesStep = 500; - 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}; + //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.5f, 2.9f}; const int totalDegreeSamples = 200; diff --git a/triangle_creation_frequency_plots.m b/triangle_creation_frequency_plots.m index 581469c7f211d890807af1dc15ac755376ca7919..33faa20593f5ca3b6421202a3ce17d06ac7f7ef7 100644 --- a/triangle_creation_frequency_plots.m +++ b/triangle_creation_frequency_plots.m @@ -77,3 +77,28 @@ hcol=GraphicsGrid[Transpose[{{h1,h2,h3},{h1zoomed,h2zoomed,h3zoomed}}]] Export[NotebookDirectory[]<>"plots/triangle_creation_frequencies_log.pdf",hcol] + + +(* ::Subsection:: *) +(*Test with 'Callout' labels*) + + +createCalloutPlot[data_]:=Module[{h,hl,bcdata,llp}, +h=Histogram[data,{-20.5,20.5,1},{"Log","Probability"},PlotRange->All,ImageSize->280]; +hl=HistogramList[data,{-20.5,20.5,1},"Probability"]; +bcdata=Map[If[#>=0.01,Callout[#,NumberForm[#,{2,3}]],Clip[#,{10^-5,2}]]&,hl[[2]]]; +llp=ListLogPlot[bcdata,PlotStyle->None,DataRange->{-20,20}]; +Show[h,llp] +] +histograms3=Map[createCalloutPlot[Flatten[#]]&,differences,{2}]; + + +(* TODO: Somehow the values of these histograms do not match the ones above!!! ????? *) + + +Show[histograms3[[2]],PlotLabel->"n=1000, \[Tau]=2.2"] +Show[histograms3[[5]],PlotLabel->"n=1000, \[Tau]=2.5"] +Show[histograms3[[8]],PlotLabel->"n=1000, \[Tau]=2.8"] + + + diff --git a/triangle_gcm_initial_analysis.m b/triangle_gcm_initial_analysis.m index de9515c50247576c6ff3609c7741db1295a718e6..0fc898477bbfe8bdda80c1f049b143089224cba6 100644 --- a/triangle_gcm_initial_analysis.m +++ b/triangle_gcm_initial_analysis.m @@ -24,6 +24,24 @@ nlabels=Map["n = "<>ToString[#]&,gdata[[1,All,1,1,1]]]; taulabels=Map["\[Tau] = "<>ToString[#]&,gdata[[All,1,1,1,2]]]; +(* ::Subsection:: *) +(*New data format import*) + + +gsraw=Import[NotebookDirectory[]<>"data/graphdata_ccm_constructionrate.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. *) *) + + +gdata2=GatherBy[gsraw,{#[[1,2]]&,#[[1,1]]&}]; +(* Data format: *) +(* gdata[[ tau index, n index, run index , datatype index ]] *) +(* datatype index: +1: {n,tau} +3: CCMdu construction rate <-- CCMdu: get new highest degree vertex every time +4: CCMd construction rate <-- CCMd: finish vertex completely +*) + + (* ::Section:: *) (*Greedy configuration model*) @@ -125,29 +143,56 @@ Export[NotebookDirectory[]<>"plots/ccm_construction_successrate9.pdf",plot3] successrates=Map[#[[3,2]]/100&,gdata,{3}]; +successrates[[1,1]]=gdata2[[1,1,All,2]]; (* New datafile test *) +successrates=Map[Clip[#,{0,0.99999}]&,successrates,{3}]; legends=Map["\[Tau] = "<>ToString[#[[1,1,2]]]<>" ; avg = "<>ToString[NumberForm[N[Mean[#[[All,3,2]]/100]],3]]&,gdata,{2}]; datasets={successrates[[1,1]], successrates[[5,1]], successrates[[9,1]]}; selectedLegends={legends[[1,1]],legends[[5,1]],legends[[9,1]]}; -SmoothHistogram[datasets,{0.06,"Gaussian"},"PDF", +plot1=Histogram[datasets,{-0.025,1.025,0.05},"Probability", +PlotRange->{{0,1},{0,1}}, +ChartStyle->Directive[FaceForm[Opacity[0.8]],EdgeForm[Thickness[0.001]]], +ImageSize->300,AxesOrigin->{0,0}, +Frame->True, +FrameLabel->{"successrate of CCMdu construction\n(distribution over sampled degree sequences)","Probability"}, +ChartLegends->Placed[selectedLegends,Center], +PlotLabel->"n = 1000"] + +histogramlist = Map[Last[HistogramList[#,{-0.05,1.05,0.1},"Probability"]]&,datasets]; +histogramlist = Transpose[histogramlist]; +(* labels=ConstantArray["",Ceiling[1/0.05]]; +labels[[2;;-1;;2]]=Map[ToString,Range[0.1,1,0.1]]; *) +labels=Map[ToString,Range[0,1,0.1]]; +plot2=BarChart[histogramlist, +PlotRange->{All,{0,1}}, +BarSpacing->{None,Medium}, +ChartLabels->{labels,None}, +ImageSize->300,AxesOrigin->{0,0}, +Frame->True, +FrameLabel->{"successrate of CCMdu construction\n(distribution over sampled degree sequences)","Probability"}, +ChartLegends->Placed[selectedLegends,Center], +PlotLabel->"n = 1000"] + +plot3=SmoothHistogram[datasets,{0.01,"Gaussian"},"PDF", PlotRange->{{0,1},All}, -(*ChartStyle\[Rule]Directive[FaceForm[Opacity[0.5]],EdgeForm[Thickness[0.007]]],*) ImageSize->300,AxesOrigin->{0,0}, Frame->True, -FrameLabel->{"successrate of CCMdu construction\n over sampled degree sequences","PDF"}, +FrameLabel->{"successrate of CCMdu construction\n(distribution over sampled degree sequences)","PDF"}, PlotLegends->Placed[selectedLegends,Center], PlotLabel->"n = 1000"] +(* Table[ -SmoothHistogram[datasets,{0.06,weightKernel},"PDF", +SmoothHistogram[datasets,{0.01,weightKernel},"PDF", PlotRange->{{0,1},All}, (*ChartStyle\[Rule]Directive[FaceForm[Opacity[0.5]],EdgeForm[Thickness[0.007]]],*) ImageSize->300,AxesOrigin->{0,0}, Frame->True, -FrameLabel->{"successrate of CCMdu construction\n over sampled degree sequences","PDF"}, +FrameLabel->{"successrate of CCMdu construction\n over sampled degree sequences","CDF"}, PlotLegends->Placed[selectedLegends,Center], PlotLabel->"n = 1000"],{weightKernel,{"Biweight","Gaussian","Rectangular","Cosine","SemiCircle"}}] +*) - +Export[NotebookDirectory[]<>"plots/ccm_construction_successrates.pdf",plot2]