diff --git a/cpp/Makefile b/cpp/Makefile index 0c4f0e46df1871d2d1630ec3d3dde19c2a8e542c..e483772e885c75174db4c6d6fab570683d3d3803 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_cputime TARGETS += switchchain_ccm_initialtris TARGETS += switchchain_ccm_timeevol TARGETS += switchchain_properties diff --git a/cpp/exports.hpp b/cpp/exports.hpp index 5ffee273d0ffcfd4d78c849830e69d484b1e361f..261f9fda3374aeb1ea5e43aabaebbefda9cedfcb 100644 --- a/cpp/exports.hpp +++ b/cpp/exports.hpp @@ -24,6 +24,12 @@ std::ostream &operator<<(std::ostream &s, const Graph &g) { return s; } +template +std::ostream &operator<<(std::ostream &s, const std::pair& p) { + s << '{' << p.first << ',' << p.second << '}'; + return s; +} + template std::ostream& output_array(std::ostream& s, FwdIterator begin, FwdIterator end) { diff --git a/cpp/graph.hpp b/cpp/graph.hpp index 987d9a89ddf802d397f3af178816d475e21f92ec..976589eda84764818941fa30e876f41fdf9fe8c2 100644 --- a/cpp/graph.hpp +++ b/cpp/graph.hpp @@ -30,6 +30,30 @@ class DiDegree { typedef std::vector DegreeSequence; typedef std::vector DiDegreeSequence; +template< class RandomIt, class Compare > +void insertionSort( RandomIt first, RandomIt last, Compare comp ) { + for (RandomIt next = first;;) { + RandomIt a = next; + next++; + if (next == last) + break; + RandomIt b = next; + auto newvalue = *next; + // next + // 1 2 3 4 5 6 4 + // a b + // a b + // a b + // a b + while (b != first && comp(newvalue, *a)) { // if newvalue < *a + *b = *a; + a--; + b--; + } + *b = newvalue; + } +} + class Graph { public: Graph() {} @@ -79,12 +103,10 @@ class Graph { reset(n); while (!degrees.empty()) { - // Construction will find maximum triangles only if sort is stable - // and does NOT sort on vertex id - std::stable_sort(degrees.begin(), degrees.end(), - [](const auto &p1, const auto &p2) { - return p1.first < p2.first; - }); + insertionSort(degrees.begin(), degrees.end(), + [](const auto& p1, const auto& p2) { + return p1.first < p2.first; + }); // Highest degree is at back of the vector // Take it out unsigned int degree = degrees.back().first; diff --git a/cpp/switchchain_ccm_cputime.cpp b/cpp/switchchain_ccm_cputime.cpp new file mode 100644 index 0000000000000000000000000000000000000000..430bbe9ddb79c213cf34b8f5857785958c8824f0 --- /dev/null +++ b/cpp/switchchain_ccm_cputime.cpp @@ -0,0 +1,152 @@ +#include "exports.hpp" +#include "graph.hpp" +#include "graph_ccm.hpp" +#include "graph_powerlaw.hpp" +#include "switchchain.hpp" +#include +#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.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; + const int totalDegreeSamples = 1; + + 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_cputime.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 timed triangle seq\n"; + outfile << "4: {ccm1 failed attempts, timed triangle seq}\n"; + outfile << "5: {ccm2 failed attempts, timed 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> triangleSeq(mixingTime); + { + // record start time + auto start = std::chrono::high_resolution_clock::now(); + // Incorporate Havel-Hakimi time + g.createFromDegreeSequence(ds); + for (int i = 0; i < mixingTime; ++i) { + auto now = std::chrono::high_resolution_clock::now(); + std::chrono::duration dt = now - start; + triangleSeq[i] = + std::make_pair(dt.count(), chain.g.getTrackedTriangles()); + chain.doMove(true); + } + } + + std::cout << " Finished timed 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); + + // record start time + auto start = std::chrono::high_resolution_clock::now(); + + bool failed = true; + for (int i = 0; i < 1000; ++i) { + Graph gtemp; + if (constrainedConfigurationModel(ds, gtemp, rng, + ccmMethod)) { + chain.initialize(gtemp, true); + for (int i = 0; i < mixingTime; ++i) { + auto now = + std::chrono::high_resolution_clock::now(); + std::chrono::duration dt = now - start; + triangleSeq[i] = std::make_pair( + dt.count(), chain.g.getTrackedTriangles()); + chain.doMove(true); + } + outfile << ',' << '{' << i << ',' << triangleSeq << '}'; + failed = false; + break; + } + } + if (failed) + outfile << ",{1000,{}}"; + } + + outfile << '}' << std::flush; + + std::cout << " Finished timed CCM time evols." << std::flush; + + std::cout << std::endl; + } + } + } + outfile << '\n' << '}'; + return 0; +} diff --git a/triangle_ccm_timeevol_plots.m b/triangle_ccm_timeevol_plots.m index d5503103d7f7cfbdba0d45d48149f385b376d783..fbdee3c7622fddbb0c8ce4bcc4664ee86345f213 100644 --- a/triangle_ccm_timeevol_plots.m +++ b/triangle_ccm_timeevol_plots.m @@ -7,7 +7,7 @@ Needs["ErrorBarPlots`"] (*Plot successrate over time*) -gsraw=Import[NotebookDirectory[]<>"data/graphdata_ccm_timeevol.m"]; +gsraw=Import[NotebookDirectory[]<>"data/graphdata_ccm_cputime.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. *) *) @@ -113,4 +113,39 @@ Export[NotebookDirectory[]<>"plots/timeevol_ccm.pdf",plot1] Export[NotebookDirectory[]<>"plots/timeevol_ccm_log.pdf",plot1log] +(* ::Subsection:: *) +(*New code with CPU time*) + + +getCombinedTimeData[run_]:=Module[{maxTime,skipPts,hhData,ccm1Data,ccm2Data}, +maxTime=Length[run[[3]]]; +skipPts=Max[1,Round[maxTime/500]]; + +hhData= {{0,run[[3,1,2]]}}~Join~run[[3,1;;-1;;skipPts]]; +ccm1Data={{0,run[[4,2,1,2]]}}~Join~run[[4,2,1;;-1;;skipPts]]; +ccm2Data={{0,run[[5,2,1,2]]}}~Join~run[[5,2,1;;-1;;skipPts]]; + +{Legended[hhData,"\[Tau] = "<>ToString[run[[1,2]]]],ccm1Data,ccm2Data} +] + +dataSets=Map[getCombinedTimeData,gdata,{3}]; + + +dataSetsFlattened=Flatten[dataSets,3]; +colorList=Table[ColorData[97,"ColorList"][[1+Floor[i/3]]],{i,0,Length[dataSetsFlattened]-1}]; + + +ListPlot[dataSetsFlattened[[1;;3]],Joined->True,PlotRange->All] + + +z2 + + +plot1=ListPlot[dataSetsFlattened,Joined->True,PlotRange->{All,All},PlotStyle->colorList,ImageSize->300,PlotLabel->nlabels[[1]],Frame->True,FrameLabel->{"seconds","number of triangles"}] + + +Export[NotebookDirectory[]<>"plots/timeevol_ccm.pdf",plot1] +Export[NotebookDirectory[]<>"plots/timeevol_ccm_log.pdf",plot1log] + +