diff --git a/cpp/Makefile b/cpp/Makefile index a1c8f513fb29425116eb8aa2c5b159a61e887bad..452b979d4981bbf23fd0d533c5221afbc9680a93 100644 --- a/cpp/Makefile +++ b/cpp/Makefile @@ -11,7 +11,7 @@ CXXFLAGS += -DNDEBUG CXXFLAGS += -Wno-int-in-bool-context TARGETS += switchchain -TARGETS += switchchain_dsp +TARGETS += switchchain_properties TARGETS += switchchain_exponent TARGETS += switchchain_initialtris TARGETS += switchchain_mixingtime diff --git a/cpp/exports.hpp b/cpp/exports.hpp index 58a682ccb6d467bfddd064669fd7f762dbffb095..5ffee273d0ffcfd4d78c849830e69d484b1e361f 100644 --- a/cpp/exports.hpp +++ b/cpp/exports.hpp @@ -1,7 +1,8 @@ #pragma once +#include "graph.hpp" +#include #include #include -#include "graph.hpp" std::ostream &operator<<(std::ostream &s, const Edge &e) { s << '{' << e.u << ',' << e.v << '}'; @@ -23,36 +24,37 @@ std::ostream &operator<<(std::ostream &s, const Graph &g) { return s; } -template -std::ostream& operator<<(std::ostream& s, const std::vector& v) { - if (v.empty()) { +template +std::ostream& output_array(std::ostream& s, FwdIterator begin, + FwdIterator end) { + if (begin == end) { s << '{' << '}'; return s; } - auto iter = v.begin(); - s << '{' << *iter++; - for (; iter != v.end(); ++iter) { - s << ',' << *iter; + s << '{' << *begin++; + for (; begin != end; ++begin) { + s << ',' << *begin; } s << '}'; return s; } -// Mathematica style export for arrays +template +std::ostream& operator<<(std::ostream& s, const std::vector& v) { + return output_array(s, std::begin(v), std::end(v)); +} + +// Mathematica style export for normal arrays // SFINAE to disable char arrays since it will mess up // things of the form s << "some string"; template < typename T, std::size_t N, - typename = typename std::enable_if::value, T>::type> + typename = typename std::enable_if::value>::type> std::ostream& operator<<(std::ostream& s, const T (&v)[N]) { - if (N == 0) { - s << '{' << '}'; - return s; - } - s << '{' << v[0]; - for (size_t i = 1; i < N; ++i) - s << ',' << v[i]; - s << '}'; - return s; + return output_array(s, std::begin(v), std::end(v)); } +template +std::ostream& operator<<(std::ostream& s, const std::array& v) { + return output_array(s, std::begin(v), std::end(v)); +} diff --git a/cpp/switchchain_dsp.cpp b/cpp/switchchain_properties.cpp similarity index 58% rename from cpp/switchchain_dsp.cpp rename to cpp/switchchain_properties.cpp index 845a31981bada3d777c1fdcd7a74f7a478790fb5..cafcbe09348e69e91718241cb8caa30124755cf0 100644 --- a/cpp/switchchain_dsp.cpp +++ b/cpp/switchchain_properties.cpp @@ -1,6 +1,7 @@ #include "exports.hpp" #include "graph.hpp" #include "graph_powerlaw.hpp" +#include "graph_spectrum.hpp" #include "switchchain.hpp" #include #include @@ -51,15 +52,15 @@ int main(int argc, char* argv[]) { auto getMixingTime = [](int n, float tau) { return int(30.0f * (50.0f - 30.0f * (tau - 2.0f)) * n); }; - constexpr int measurements = 50; - constexpr int measureSkip = 200; // Take a sample every ... steps + constexpr int measurements = 10; + constexpr int measureSkip = 1000; // Take a sample every ... steps // Output file std::ofstream outfile; if (argc >= 2) outfile.open(argv[1]); else - outfile.open("graphdata_dsp.m"); + outfile.open("graphdata_properties.m"); if (!outfile.is_open()) { std::cout << "ERROR: Could not open output file.\n"; return 1; @@ -75,9 +76,15 @@ int main(int argc, char* argv[]) { outfile << "data:\n"; outfile << "1: {n,tau}\n"; outfile << "2: avgTriangles\n"; - outfile << "3: dstn\n"; + outfile << "3: edges\n"; + outfile << "4: dstn\n"; + outfile << "5: { HH A, HH L, average A, average L } where for each there is (average of) {lambda1 , lambda1 - lambda2, lambda1/lambda2}\n"; + outfile << "6: switching successrate after mixing\n"; + outfile << "7: initial HH triangles\n"; outfile << "*)" << std::endl; + // Mathematica does not accept normal scientific notation + outfile << std::fixed; outfile << '{'; bool outputComma = false; @@ -99,34 +106,60 @@ int main(int argc, char* argv[]) { return 1; } - std::cout << "Running n = " << numVertices << ", tau = " << tau - << ". \t" << std::flush; - - int movesDone = 0; - int mixingTime = getMixingTime(numVertices,tau); - - long long trianglesTotal = 0; + std::cout << "Running (n,tau) = (" << numVertices << ',' + << tau << "). " << std::flush; + // Mix + int mixingTime = getMixingTime(numVertices, tau); for (int i = 0; i < mixingTime; ++i) { - if (chain.doMove()) - ++movesDone; + chain.doMove(); } + + std::cout << "Mixing done. " << std::flush; + + std::array HHAspectrum; + std::array HHLspectrum; + std::array avgAspectrum; + std::array avgLspectrum; + + auto getSpectralValues = [](const std::vector& s) -> std::array { + auto l1 = s[s.size()-1]; + auto l2 = s[s.size()-2]; + return {l1, l1 - l2, l1/l2}; + }; + + GraphSpectrum gs_start(g); + GraphSpectrum gs(chain.g); + + HHAspectrum = getSpectralValues(gs_start.computeAdjacencySpectrum()); + HHLspectrum = getSpectralValues(gs_start.computeLaplacianSpectrum()); + + long long trianglesTotal = 0; + int movesDone = 0; + avgAspectrum.fill(0); + avgLspectrum.fill(0); for (int i = 0; i < measurements; ++i) { for (int j = 0; j < measureSkip; ++j) if (chain.doMove()) ++movesDone; trianglesTotal += chain.g.countTriangles(); + auto sA = getSpectralValues(gs.computeAdjacencySpectrum()); + auto sL = getSpectralValues(gs.computeLaplacianSpectrum()); + for (auto i = 0u; i < 3; ++i) { + avgAspectrum[i] += sA[i]; + avgLspectrum[i] += sL[i]; + } } float avgTriangles = float(trianglesTotal) / float(measurements); + float successrate = + float(movesDone) / float(measurements * measureSkip); + for (auto& f : avgAspectrum) + f /= float(measurements); + for (auto& f : avgLspectrum) + f /= float(measurements); - std::cout << movesDone << '/' - << mixingTime + measurements * measureSkip - << " moves succeeded (" - << 100.0f * float(movesDone) / - float(mixingTime + measurements * measureSkip) - << "%)."; - std::cout << std::flush; + std::cout << "Measuring done." << std::flush; if (outputComma) outfile << ',' << '\n'; @@ -134,10 +167,18 @@ int main(int argc, char* argv[]) { outfile << '{' << '{' << numVertices << ',' << tau << '}'; outfile << ',' << avgTriangles; + outfile << ',' << g.edgeCount(); outfile << ',' << getDSTN(ds); + outfile << ',' << '{' << HHAspectrum; + outfile << ',' << HHLspectrum; + outfile << ',' << avgAspectrum; + outfile << ',' << avgLspectrum; + outfile << '}'; + outfile << ',' << successrate; + outfile << ',' << g.countTriangles(); outfile << '}' << std::flush; - std::cout << std::endl; + std::cout << "Output done." << std::endl; } } }