#include "exports.hpp" #include "graph.hpp" #include "graph_powerlaw.hpp" #include "switchchain.hpp" #include #include #include #include #include #include double getDSTN(const DegreeSequence& ds) { std::vector> vals(ds.size()); for (auto& v : vals) { v.resize(ds.size(), 0); } auto D = 0u; for (auto d : ds) D += d; double factor = 1.0 / double(D); for (auto i = 0u; i < ds.size(); ++i) { for (auto j = i + 1; j < ds.size(); ++j) { vals[i][j] = 1.0 - std::exp(-(ds[i] * ds[j] * factor)); } } double result = 0.0; for (auto i = 0u; i < ds.size(); ++i) { for (auto j = i + 1; j < ds.size(); ++j) { for (auto k = j + 1; k < ds.size(); ++k) { result += vals[i][j] * vals[j][k] * vals[i][k]; } } } return result; } int main(int argc, char* argv[]) { // Simulation parameters const int numVerticesMin = 100; const int numVerticesMax = 1000; const int numVerticesStep = 100; float tauValues[] = {2.1f, 2.2f, 2.3f, 2.4f, 2.5f, 2.6f, 2.7f, 2.8f, 2.9f}; const int totalDegreeSamples = 2000; 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 // Output file std::ofstream outfile; if (argc >= 2) outfile.open(argv[1]); else outfile.open("graphdata_dsp.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: 30 * (50 - 30 (tau - 2)) n\n"; outfile << "data:\n"; outfile << "1: {n,tau}\n"; outfile << "2: avgTriangles\n"; outfile << "3: dstn\n"; outfile << "*)" << std::endl; 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); SwitchChain chain; if (!chain.initialize(g)) { std::cerr << "Could not initialize Markov chain.\n"; return 1; } std::cout << "Running n = " << numVertices << ", tau = " << tau << ". \t" << std::flush; int movesDone = 0; int mixingTime = getMixingTime(numVertices,tau); long long trianglesTotal = 0; for (int i = 0; i < mixingTime; ++i) { if (chain.doMove()) ++movesDone; } for (int i = 0; i < measurements; ++i) { for (int j = 0; j < measureSkip; ++j) if (chain.doMove()) ++movesDone; trianglesTotal += chain.g.countTriangles(); } float avgTriangles = float(trianglesTotal) / float(measurements); std::cout << movesDone << '/' << mixingTime + measurements * measureSkip << " moves succeeded (" << 100.0f * float(movesDone) / float(mixingTime + measurements * measureSkip) << "%)."; std::cout << std::flush; if (outputComma) outfile << ',' << '\n'; outputComma = true; outfile << '{' << '{' << numVertices << ',' << tau << '}'; outfile << ',' << avgTriangles; outfile << ',' << getDSTN(ds); outfile << '}' << std::flush; std::cout << std::endl; } } } outfile << '}'; return 0; }