diff --git a/cpp/switchchain.cpp b/cpp/switchchain.cpp index f04edcc8adb2969cddb286f0b1183810f3345c5f..3b85a8cbcacfa7d6af9f5bab490f4f207c2a0c7d 100644 --- a/cpp/switchchain.cpp +++ b/cpp/switchchain.cpp @@ -1,15 +1,15 @@ +#include "exports.hpp" +#include "graph.hpp" #include #include #include #include #include #include -#include "graph.hpp" -#include "exports.hpp" // Its assumed that u,v are distinct. // Check if all four vertices are distinct -bool edgeConflicts(const Edge &e1, const Edge &e2) { +bool edgeConflicts(const Edge& e1, const Edge& e2) { return (e1.u == e2.u || e1.u == e2.v || e1.v == e2.u || e1.v == e2.v); } @@ -22,7 +22,7 @@ class SwitchChain { } ~SwitchChain() {} - bool initialize(const Graph &gstart) { + bool initialize(const Graph& gstart) { if (gstart.edgeCount() == 0) return false; g = gstart; @@ -67,64 +67,88 @@ class SwitchChain { }; int main() { + // 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 + Graph g; - // Generate a random degree sequence - std::mt19937 gen(std::random_device{}()); - - // 50 nodes with average degree 12 - DegreeSequence ds(50); - std::poisson_distribution<> degDist(7); - - // 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; - } - } - if (!validGraph) { - std::cerr << "Could not create graph from degree sequence.\n"; - return 1; - } - std::sort(ds.begin(), ds.end()); + std::ofstream outfile("graphdata.m"); + 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; + } + } + 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; + //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::ofstream outfile("graphdata.m"); - outfile << '{'; - outfile << '{' << g; - - std::cout << "Starting switch Markov chain" << std::endl; - int movesDone = 0; - constexpr int movesTotal = 10000; - int triangles[movesTotal]; - for (int i = 0; i < movesTotal; ++i) { - if (chain.doMove()) - ++movesDone; - triangles[i] = chain.g.countTriangles(); - if (i % (movesTotal / 50) == (movesTotal / 50 - 1)) - outfile << ',' << chain.g; - } - outfile << '}' << ',' << '{' << triangles[0]; - for (int i = 1; i < movesTotal; ++i) - outfile << ',' << triangles[i]; - outfile << '}' << '}'; + std::cout << "Starting switch Markov chain" << std::endl; + + constexpr int mixingTime = 15000; + constexpr int measureTime = 5000; + int movesDone = 0; - std::cout << movesDone << '/' << movesTotal << " moves succeeded." - << std::endl; + 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(); + } + + if (outputComma) + outfile << ','; + outputComma = true; + outfile << '{' << numVertices << ',' << '{'; + outfile << triangles[0]; + for (int i = 1; i < measureTime; ++i) + outfile << ',' << triangles[i]; + outfile << '}' << '}'; + + std::cout << movesDone << '/' << mixingTime + measureTime + << " moves succeeded." << std::endl; + } + } + outfile << '}'; return 0; }