diff --git a/cpp/switchchain.cpp b/cpp/switchchain.cpp index 3b85a8cbcacfa7d6af9f5bab490f4f207c2a0c7d..cdfa68cea8fdcf7ca0f345b3fd82f9c4e20320c0 100644 --- a/cpp/switchchain.cpp +++ b/cpp/switchchain.cpp @@ -1,5 +1,6 @@ #include "exports.hpp" #include "graph.hpp" +#include "powerlaw.hpp" #include #include #include @@ -67,11 +68,15 @@ class SwitchChain { }; int main() { + // Generate a random degree sequence + std::mt19937 rng(std::random_device{}()); + // Goal: // Degrees follow a power-law distribution with some parameter tau // Expect: #tri = const * n^{ something } // The goal is to find the 'something' by finding the number of triangles // for different values of n and tau + float tauValues[] = {2.2f, 2.5f, 2.8f}; Graph g; @@ -79,74 +84,72 @@ int main() { outfile << '{'; bool outputComma = false; - for (int numVertices = 500; numVertices <= 1000; numVertices += 100) { - // Generate a random degree sequence - std::mt19937 gen(std::random_device{}()); - - // average degree 12 - DegreeSequence ds(numVertices); - std::poisson_distribution<> degDist(12); - - // For a single n, take samples over several instances of - // the degree distribution - for (int degreeSample = 0; degreeSample < 10; ++degreeSample) { - - // Try at most 10 times to generate a valid sequence - bool validGraph = false; - for (int i = 0; i < 10; ++i) { - std::generate(ds.begin(), ds.end(), - [°Dist, &gen] { return degDist(gen); }); - if (g.createFromDegreeSequence(ds)) { - validGraph = true; - break; + for (int numVertices = 200; numVertices <= 2000; numVertices += 200) { + for (float tau : tauValues) { + + DegreeSequence ds(numVertices); + powerlaw_distribution degDist(tau, 2, numVertices); + //std::poisson_distribution<> degDist(12); + + // For a single n,tau take samples over several instances of + // the degree distribution + for (int degreeSample = 0; degreeSample < 200; ++degreeSample) { + // Generate a graph + // might require multiple tries + for (int i = 1; ; ++i) { + std::generate(ds.begin(), ds.end(), + [°Dist, &rng] { return degDist(rng); }); + if (g.createFromDegreeSequence(ds)) + break; + // When 10 tries have not worked, output a warning + if (i % 10 == 0) { + std::cerr << "Warning: could not create graph from " + "degree sequence. Trying again...\n"; + } } - } - if (!validGraph) { - std::cerr << "Could not create graph from degree sequence.\n"; - return 1; - } - std::sort(ds.begin(), ds.end()); - //std::cout << "Degree sequence:"; - //for (auto i : ds) - // std::cout << ' ' << i; - //std::cout << std::endl; + SwitchChain chain; + if (!chain.initialize(g)) { + std::cerr << "Could not initialize Markov chain.\n"; + return 1; + } - SwitchChain chain; - if (!chain.initialize(g)) { - std::cerr << "Could not initialize Markov chain.\n"; - return 1; - } + std::cout << "Starting switch Markov chain with n = " + << numVertices << ", tau = " << tau << ". \t" + << std::flush; - std::cout << "Starting switch Markov chain" << std::endl; + constexpr int mixingTime = 15000; + constexpr int measureTime = 10000; + constexpr int measureSkip = + 100; // Take a sample every 100 steps + constexpr int measurements = + (measureTime - 1) / measureSkip + 1; + int movesDone = 0; - constexpr int mixingTime = 15000; - constexpr int measureTime = 5000; - int movesDone = 0; + int triangles[measurements]; - int triangles[measureTime]; - for (int i = 0; i < mixingTime; ++i) { - if (chain.doMove()) - ++movesDone; - } - for (int i = 0; i < measureTime; ++i) { - if (chain.doMove()) - ++movesDone; - triangles[i] = chain.g.countTriangles(); - } + for (int i = 0; i < mixingTime; ++i) { + if (chain.doMove()) + ++movesDone; + } + for (int i = 0; i < measureTime; ++i) { + if (chain.doMove()) + ++movesDone; + if (i % measureSkip == 0) + triangles[i / measureSkip] = chain.g.countTriangles(); + } - if (outputComma) - outfile << ','; - outputComma = true; + std::cout << movesDone << '/' << mixingTime + measureTime + << " moves succeeded." << std::endl; - outfile << '{' << numVertices << ',' << '{'; - outfile << triangles[0]; - for (int i = 1; i < measureTime; ++i) - outfile << ',' << triangles[i]; - outfile << '}' << '}'; + if (outputComma) + outfile << ','; + outputComma = true; - std::cout << movesDone << '/' << mixingTime + measureTime - << " moves succeeded." << std::endl; + std::sort(ds.begin(), ds.end()); + outfile << '{' << '{' << numVertices << ',' << tau << '}'; + outfile << ',' << triangles << ',' << ds << '}' << std::flush; + } } } outfile << '}';