Changeset - 1b3f095f886f
[Not reviewed]
0 4 0
Tom Bannink - 8 years ago 2017-07-03 16:06:50
tombannink@gmail.com
Add computation of delta-triangles to switchchain
4 files changed with 91 insertions and 47 deletions:
0 comments (0 inline, 0 general)
cpp/graph.hpp
Show inline comments
 
@@ -142,13 +142,14 @@ class Graph {
 
        return true;
 
    }
 

	
 
    // 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;
 
        const Edge &e2 = se2.e;
 

	
 
        // The new edges configuration is one of these two
 
@@ -162,12 +163,17 @@ class Graph {
 
        }
 

	
 
        // First check if the move is possible
 
        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;
 
        badj[e2.u][e2.v] = false;
 
        badj[e2.v][e2.u] = false;
 

	
 
@@ -180,17 +186,36 @@ class Graph {
 
        std::swap(se1.v2uindex, se2.u2vindex);
 
        // e1 and e2 now contain the NEW edges!!
 
        badj[e1.u][e1.v] = true;
 
        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) {
 
                    if (hasEdge({v[i], v[j]})) {
 
                        ++triangles;
 
                    }
 
@@ -198,12 +223,14 @@ class Graph {
 
            }
 
        }
 
        assert(triangles % 3 == 0);
 
        return triangles / 3;
 
    }
 

	
 
    unsigned int& getTrackedTriangles() { return trackedTriangles; }
 

	
 
    // Should return zero
 
    int consistencyCheck() const {
 
        // Check if info in 'edges' is present
 
        // in adj and badj
 
        for (auto &se : edges) {
 
            if (se.e.u >= adj.size() || se.e.v >= adj.size())
 
@@ -251,8 +278,9 @@ class Graph {
 
  private:
 
    // Graph is saved in three formats for speed
 
    // They should be kept consistent at all times
 
    std::vector<std::vector<unsigned int>> adj;
 
    std::vector<std::vector<bool>> badj; // symmetric binary matrix
 
    std::vector<StoredEdge> edges;
 
    unsigned int trackedTriangles;
 
};
 

	
cpp/switchchain.hpp
Show inline comments
 
@@ -18,22 +18,24 @@ class SwitchChain {
 
        // random_device uses hardware entropy if available
 
        // std::random_device rd;
 
        // mt.seed(rd());
 
    }
 
    ~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
 
        do {
 
            e1index = edgeDistribution(mt);
 
            e2index = edgeDistribution(mt);
 
@@ -45,13 +47,13 @@ class SwitchChain {
 

	
 
        // Consider one of the three possible permutations
 
        // 1) e1.u - e1.v and e2.u - e2.v (original)
 
        // 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;
 
    std::mt19937 mt;
 
    std::uniform_int_distribution<> edgeDistribution;
 
    //std::uniform_int_distribution<> permutationDistribution;
cpp/switchchain_mixingtime.cpp
Show inline comments
 
@@ -8,97 +8,110 @@
 
#include <iostream>
 
#include <numeric>
 
#include <random>
 
#include <vector>
 

	
 
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;
 
                auto count = 0u;
 
                for (int i = measurements - (measurements / 5); i < measurements; ++i) {
 
                    trianglesTotal += triangles[i];
 
@@ -116,18 +129,19 @@ int main(int argc, char* argv[]) {
 
                }
 

	
 
                if (outputComma)
 
                    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;
 
                }
 
            }
 
        }
 
    }
 
    outfile << '}';
 
    return 0;
cpp/switchchain_properties.cpp
Show inline comments
 
@@ -156,13 +156,13 @@ int main(int argc, char* argv[]) {
 
                    float(movesDone) / float(measurements * measureSkip);
 
                for (auto& f : avgAspectrum)
 
                    f /= float(measurements);
 
                for (auto& f : avgLspectrum)
 
                    f /= float(measurements);
 

	
 
                std::cout << "Measuring done." << std::flush;
 
                std::cout << "Measuring done. " << std::flush;
 

	
 
                if (outputComma)
 
                    outfile << ',' << '\n';
 
                outputComma = true;
 

	
 
                outfile << '{' << '{' << numVertices << ',' << tau << '}';
0 comments (0 inline, 0 general)