From 1b3f095f886fbe09d322385e7c0340df86157257 2017-07-03 16:06:50 From: Tom Bannink Date: 2017-07-03 16:06:50 Subject: [PATCH] Add computation of delta-triangles to switchchain --- diff --git a/cpp/graph.hpp b/cpp/graph.hpp index 6585dbd12d79407616158c9bd3d7108ed08eef51..13f997a413f3e565161162a31b8808f43b32d99d 100644 --- a/cpp/graph.hpp +++ b/cpp/graph.hpp @@ -145,7 +145,8 @@ class Graph { // There are two possible edge exchanges // switchType indicates which one is desired // Returns false if the switch is not possible - bool exchangeEdges(unsigned int e1index, unsigned int e2index, bool switchType) { + bool exchangeEdges(unsigned int e1index, unsigned int e2index, + bool switchType, bool trackTriangles = false) { StoredEdge &se1 = edges[e1index]; StoredEdge &se2 = edges[e2index]; const Edge &e1 = se1.e; @@ -165,6 +166,11 @@ class Graph { if (hasEdge({e1.u, e2.u}) || hasEdge({e1.v, e2.v})) return false; // conflicting edges + if (trackTriangles) { + trackedTriangles -= countTriangles(e1); + trackedTriangles -= countTriangles(e2); + } + // Clear old edges badj[e1.u][e1.v] = false; badj[e1.v][e1.u] = false; @@ -183,11 +189,30 @@ class Graph { badj[e1.v][e1.u] = true; badj[e2.u][e2.v] = true; badj[e2.v][e2.u] = true; + + if (trackTriangles) { + trackedTriangles += countTriangles(e1); + trackedTriangles += countTriangles(e2); + } + return true; } - int countTriangles() const { - int triangles = 0; + // Assumes edge exists + // Used for computing triangle-delta's after switch move + unsigned int countTriangles(Edge e) const { + auto triangles = 0u; + if (adj[e.u].size() > adj[e.v].size()) + std::swap(e.u, e.v); + for (auto w : adj[e.u]) { + if (hasEdge({w, e.v})) + ++triangles; + } + return triangles; + } + + unsigned int countTriangles() const { + auto triangles = 0u; for (auto& v : adj) { for (unsigned int i = 0; i < v.size(); ++i) { for (unsigned int j = i + 1; j < v.size(); ++j) { @@ -201,6 +226,8 @@ class Graph { return triangles / 3; } + unsigned int& getTrackedTriangles() { return trackedTriangles; } + // Should return zero int consistencyCheck() const { // Check if info in 'edges' is present @@ -254,5 +281,6 @@ class Graph { std::vector> adj; std::vector> badj; // symmetric binary matrix std::vector edges; + unsigned int trackedTriangles; }; diff --git a/cpp/switchchain.hpp b/cpp/switchchain.hpp index 34e511d1c602394689504f56908bb64795eec7a8..49849d43f591842b92196b374857f4677b1c65aa 100644 --- a/cpp/switchchain.hpp +++ b/cpp/switchchain.hpp @@ -21,16 +21,18 @@ class SwitchChain { } ~SwitchChain() {} - bool initialize(const Graph& gstart) { + bool initialize(const Graph& gstart, bool trackTriangles = false) { if (gstart.edgeCount() == 0) return false; g = gstart; edgeDistribution.param( std::uniform_int_distribution<>::param_type(0, g.edgeCount() - 1)); + if (trackTriangles) + g.getTrackedTriangles() = g.countTriangles(); return true; } - bool doMove() { + bool doMove(bool trackTriangles = false) { int e1index, e2index; int timeout = 0; // Keep regenerating while conflicting edges @@ -48,7 +50,7 @@ class SwitchChain { // 2) e1.u - e2.u and e1.v - e2.v // 3) e1.u - e2.v and e1.v - e2.u bool switchType = permutationDistribution(mt); - return g.exchangeEdges(e1index, e2index, switchType); + return g.exchangeEdges(e1index, e2index, switchType, trackTriangles); } Graph g; 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; } } } diff --git a/cpp/switchchain_properties.cpp b/cpp/switchchain_properties.cpp index ef2e27771dacb5f93dec3dd8860bd37714dcfe6c..7f8f24c08ddd01da5386dd1b976ac2250b9434bc 100644 --- a/cpp/switchchain_properties.cpp +++ b/cpp/switchchain_properties.cpp @@ -159,7 +159,7 @@ int main(int argc, char* argv[]) { for (auto& f : avgLspectrum) f /= float(measurements); - std::cout << "Measuring done." << std::flush; + std::cout << "Measuring done. " << std::flush; if (outputComma) outfile << ',' << '\n';