diff --git a/cpp/switchchain.cpp b/cpp/switchchain.cpp index 442b4b280f94c9bd1a03a978aab5b9eac04f4295..8636b77157077b6bc1007496077d998cd1e1ab31 100644 --- a/cpp/switchchain.cpp +++ b/cpp/switchchain.cpp @@ -16,7 +16,10 @@ bool edgeConflicts(const Edge& e1, const Edge& e2) { class SwitchChain { public: - SwitchChain() : mt(std::random_device{}()), permutationDistribution(0, 2) { + SwitchChain() + : mt(std::random_device{}()), permutationDistribution(0.5) + // permutationDistribution(0, 2) + { // random_device uses hardware entropy if available // std::random_device rd; // mt.seed(rd()); @@ -33,38 +36,53 @@ class SwitchChain { } bool doMove() { - Edge e1 = g.getEdge(edgeDistribution(mt)); - Edge e2 = g.getEdge(edgeDistribution(mt)); - // Keep regenerating while conflicting edges + Edge e1, e2; + int e1index, e2index; int timeout = 0; - while (edgeConflicts(e1, e2)) { - e1 = g.getEdge(edgeDistribution(mt)); - e2 = g.getEdge(edgeDistribution(mt)); + // Keep regenerating while conflicting edges + do { + e1index = edgeDistribution(mt); + e2index = edgeDistribution(mt); + e1 = g.getEdge(e1index); + e2 = g.getEdge(e2index); ++timeout; if (timeout % 100 == 0) { std::cerr << "Warning: sampled " << timeout << " random edges but they keep conflicting.\n"; } - } + } while (edgeConflicts(e1, e2)); + // 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 // Note that it might be that these new edges already exist - // in which case we also reject the move - // This is checked in exchangeEdges + // in which case we reject the move + bool switchType = permutationDistribution(mt); + if (switchType) { + if (g.hasEdge({e1.u, e2.u}) || g.hasEdge({e1.v, e2.v})) + return false; // conflicting edges + } else { + if (g.hasEdge({e1.u, e2.v}) || g.hasEdge({e1.v, e2.u})) + return false; // conflicting edges + } - int perm = permutationDistribution(mt); - if (perm == 0) // Original permutation - return false; - return g.exchangeEdges(e1, e2, perm == 1); + // TODO + // rest of the switching process + + // int perm = permutationDistribution(mt); + // if (perm == 0) // Original permutation + // return false; + // return g.exchangeEdges(e1, e2, perm == 1); + return g.exchangeEdges(e1, e2, switchType); } Graph g; std::mt19937 mt; std::uniform_int_distribution<> edgeDistribution; - std::uniform_int_distribution<> permutationDistribution; + //std::uniform_int_distribution<> permutationDistribution; + std::bernoulli_distribution permutationDistribution; }; int main() { @@ -76,7 +94,7 @@ int main() { // 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.35f, 2.5f, 2.65f, 2.8f}; + float tauValues[] = {2.1f, 2.2f, 2.3f, 2.4f, 2.5f, 2.6f, 2.7f, 2.8f}; Graph g; @@ -114,11 +132,10 @@ int main() { return 1; } - std::cout << "Starting switch Markov chain with n = " - << numVertices << ", tau = " << tau << ". \t" - << std::flush; + std::cout << "Running n = " << numVertices << ", tau = " << tau + << ". \t" << std::flush; - constexpr int mixingTime = 30000; + constexpr int mixingTime = 40000; constexpr int measureTime = 20000; constexpr int measureSkip = 200; // Take a sample every ... steps