diff --git a/cpp/switchchain_mixingtime.cpp b/cpp/switchchain_mixingtime.cpp index 419df3207be6ef51f19ee9adf608bb4e9030e971..8433d0f1071a636c0b25590e8b098b518775e5ce 100644 --- a/cpp/switchchain_mixingtime.cpp +++ b/cpp/switchchain_mixingtime.cpp @@ -11,91 +11,104 @@ #include int main(int argc, char* argv[]) { - // Generate a random degree sequence - std::mt19937 rng(std::random_device{}()); + // Simulation parameters + const int numVerticesMin = 1000; + const int numVerticesMax = 4000; + const int numVerticesStep = 500; - // 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.5f}; float tauValues[] = {2.1f, 2.2f, 2.3f, 2.4f, 2.5f, 2.6f, 2.7f, 2.8f, 2.9f}; - Graph g; - Graph g1; - Graph g2; + const int totalDegreeSamples = 200; - std::ofstream outfile; + auto getMixingTime = [](int n, float tau) { + (void)n; + (void)tau; + return 0; + //return int(50.0f * (50.0f - 30.0f * (tau - 2.0f)) * n); + }; + constexpr int measurements = 100000; + constexpr int measureSkip = 1; // Take a sample every ... steps + // Output file + std::ofstream outfile; if (argc >= 2) outfile.open(argv[1]); - else + else outfile.open("graphdata_etmt.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: 50 * (50 - 30 (tau - 2)) n\n"; + outfile << "data:\n"; + outfile << "1: {n,tau}\n"; + outfile << "2: avgTriangles\n"; + outfile << "3: edges\n"; + outfile << "4: etmt\n"; + outfile << "*)" << std::endl; + + // Mathematica does not accept normal scientific notation + outfile << std::fixed; outfile << '{'; bool outputComma = false; - for (int numVertices = 100; numVertices <= 1000; numVertices += 100) { + // Generate a random degree sequence + std::mt19937 rng(std::random_device{}()); + Graph g; + Graph g1; + Graph g2; + 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 < 200; ++degreeSample) { + for (int degreeSample = 0; degreeSample < totalDegreeSamples; + ++degreeSample) { DegreeSequence ds; generatePowerlawGraph(numVertices, tau, g, ds, rng); - // Multiple runs from the same degree sequence for (int i = 0; i < 5; ++i) { SwitchChain chain; - if (!chain.initialize(g)) { + if (!chain.initialize(g, true)) { std::cerr << "Could not initialize Markov chain.\n"; return 1; } - std::cout << "Running n = " << numVertices << ", tau = " << tau - << ". \t" << std::flush; - - //int mixingTime = (32.0f - 26.0f*(tau - 2.0f)) * numVertices; //40000; - //constexpr int measurements = 50; - //constexpr int measureSkip = - // 200; // Take a sample every ... steps - int mixingTime = 0; - constexpr int measurements = 50000; - constexpr int measureSkip = 1; + std::cout << "Running (n,tau) = (" << numVertices << ',' + << tau << "). " << std::flush; int movesTotal = 0; int movesSuccess = 0; int triangles[measurements]; + // Mix + int mixingTime = getMixingTime(numVertices, tau); for (int i = 0; i < mixingTime; ++i) { - ++movesTotal; - if (chain.doMove()) { - ++movesSuccess; - } + chain.doMove(); } + // Measure for (int i = 0; i < measurements; ++i) { for (int j = 0; j < measureSkip; ++j) { ++movesTotal; - if (chain.doMove()) { + if (chain.doMove(true)) { ++movesSuccess; } } - triangles[i] = chain.g.countTriangles(); + triangles[i] = chain.g.getTrackedTriangles(); } - std::cout << '(' - << 100.0f * float(movesSuccess) / float(movesTotal) - << "% successrate). " << std::flush; - // std::cout << std::endl; + std::cout << "Measuring done. " << std::flush; // Take the average over the last 20% auto trianglesTotal = 0uL; @@ -119,12 +132,13 @@ int main(int argc, char* argv[]) { outfile << ',' << '\n'; outputComma = true; - std::sort(ds.begin(), ds.end()); outfile << '{' << '{' << numVertices << ',' << tau << '}'; + outfile << ',' << trianglesAvg; + outfile << ',' << g.edgeCount(); outfile << ',' << ETMT; outfile << '}' << std::flush; - std::cout << std::endl; + std::cout << "Output done. " << std::endl; } } }