diff --git a/cpp/switchchain.cpp b/cpp/switchchain.cpp index ee360658dcd8328924f7605304c2ddf2eda8a255..1871aab3959c58061aacb964393eab7fa2c222a5 100644 --- a/cpp/switchchain.cpp +++ b/cpp/switchchain.cpp @@ -63,8 +63,11 @@ class SwitchChain { std::bernoulli_distribution permutationDistribution; }; -bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, auto& rng) { - // Same as Havel-Hakimi but instead of pairing up with the highest ones +// +// Assumes degree sequence does NOT contain any zeroes! +// +bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, auto& rng, bool method2) { + // Similar to Havel-Hakimi but instead of pairing up with the highest ones // that remain, simply pair up with random ones unsigned int n = ds.size(); @@ -74,47 +77,79 @@ bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, auto& rng) { degrees[i].first = ds[i]; degrees[i].second = i; } - std::vector available; - available.reserve(n); // Clear the graph g.reset(n); - std::uniform_int_distribution<> distr(1, n - 1); - while (!degrees.empty()) { + std::shuffle(degrees.begin(), degrees.end(), rng); // Get the highest degree: + // If there are multiple highest ones, we pick a random one, + // ensured by the shuffle. + // The shuffle is needed anyway for the remaining part unsigned int dmax = 0; - unsigned int u = 0; - auto maxIter = degrees.begin(); + auto uIter = degrees.begin(); for (auto iter = degrees.begin(); iter != degrees.end(); ++iter) { if (iter->first >= dmax) { dmax = iter->first; - u = iter->second; - maxIter = iter; + uIter = iter; } } - // Take the highest degree out of the vector - degrees.erase(maxIter); - - available.clear(); - for (auto iter = degrees.begin(); iter != degrees.end(); ++iter) { - if (iter->first) - available.push_back(iter); - } - if (dmax > available.size()) + if (dmax > degrees.size() - 1) return false; - std::shuffle(available.begin(), available.end(), rng); - - // Now assign randomly to the remaining vertices - // Pick 'cmax' distinct integers between 1 and degrees.size() - for (unsigned int i = 0; i < dmax; ++i) { - if (!g.addEdge({u,available[i]->second})) { - std::cerr << "ERROR. Could not add edge in greedy configuration model.\n"; + unsigned int u = uIter->second; + + if (method2) { + // Take the highest degree out of the vector + degrees.erase(uIter); + + // Now assign randomly to the remaining vertices + // Since its shuffled, we can pick the first 'dmax' ones + auto vIter = degrees.begin(); + while (dmax--) { + if (vIter->first == 0) + std::cerr << "ERROR in GCM2.\n"; + if (!g.addEdge({u, vIter->second})) + std::cerr << "ERROR. Could not add edge in GCM2.\n"; + vIter->first--; + if (vIter->first == 0) + vIter = degrees.erase(vIter); + else + vIter++; + } + } else { + // Pair with a random vertex that is not u itself + std::uniform_int_distribution<> distr(0, degrees.size() - 2); + auto vIter = degrees.begin() + distr(rng); + if (vIter == uIter) + vIter++; + // pair u to v + if (vIter->first == 0) + std::cerr << "ERROR in GCM1.\n"; + if (!g.addEdge({uIter->second, vIter->second})) + std::cerr << "ERROR. Could not add edge in GCM1.\n"; + // Purge anything with degree zero + // Be careful with invalidating the other iterator! + // Degree of u is always greater or equal to the degree of v + if (dmax == 1) { + // Remove both + if (vIter > uIter) { + degrees.erase(vIter); + degrees.erase(uIter); + } else { + degrees.erase(uIter); + degrees.erase(vIter); + } + } else { + // Remove only v if it reaches zero + vIter->first--; + if (vIter->first == 0) + degrees.erase(vIter); } - available[i]->first--; + //degrees.erase(std::remove_if(degrees.begin(), degrees.end(), + // [](auto x) { return x.first == 0; })); } } return true; @@ -132,6 +167,7 @@ int main() { float tauValues[] = {2.1f, 2.2f, 2.3f, 2.4f, 2.5f, 2.6f, 2.7f, 2.8f}; Graph g; + Graph g2; std::ofstream outfile("graphdata.m"); outfile << '{'; @@ -160,19 +196,8 @@ int main() { ds.back()++; } - // Option 1: - if (g.createFromDegreeSequence(ds)) { - // Test option 2: - //int good = 0; - //for (int i = 0; i < 100; ++i) { - // if (greedyConfigurationModel(ds, g, rng)) - // ++good; - //} - //std::cerr << "Greedy configuration model success rate: " << good << "%\n"; - - //g.createFromDegreeSequence(ds); + if (g.createFromDegreeSequence(ds)) break; - } // When 10 tries have not worked, output a warning if (i % 10 == 0) { @@ -181,6 +206,18 @@ int main() { } } + // + // Test the greedy configuration model success rate + // + std::vector greedyTriangles; + int successrate = 0; + for (int i = 0; i < 100; ++i) { + if (greedyConfigurationModel(ds, g2, rng, true)) { + ++successrate; + greedyTriangles.push_back(g2.countTriangles()); + } + } + SwitchChain chain; if (!chain.initialize(g)) { std::cerr << "Could not initialize Markov chain.\n"; @@ -190,10 +227,15 @@ int main() { 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 = (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 = 10000; + constexpr int measureSkip = 1; + + int movesDone = 0; int triangles[measurements]; @@ -221,7 +263,8 @@ int main() { std::sort(ds.begin(), ds.end()); outfile << '{' << '{' << numVertices << ',' << tau << '}'; - outfile << ',' << triangles << ',' << ds << '}' << std::flush; + outfile << ',' << triangles << ',' << ds; + outfile << ',' << greedyTriangles << '}' << std::flush; } } }