diff --git a/cpp/switchchain_timeevol.cpp b/cpp/switchchain_timeevol.cpp index a69b23d9008771c33259ce7be0ba2cef391cd807..374a466dbe551eda889568394fd95173969b6334 100644 --- a/cpp/switchchain_timeevol.cpp +++ b/cpp/switchchain_timeevol.cpp @@ -1,6 +1,7 @@ #include "exports.hpp" #include "graph.hpp" #include "powerlaw.hpp" +#include "switchchain.hpp" #include #include #include @@ -9,192 +10,6 @@ #include #include -// Its assumed that u,v are distinct. -// Check if all four vertices are distinct -bool edgeConflicts(const Edge& e1, const Edge& e2) { - return (e1.u == e2.u || e1.u == e2.v || e1.v == e2.u || e1.v == e2.v); -} - -class SwitchChain { - public: - 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()); - } - ~SwitchChain() {} - - bool initialize(const Graph& gstart) { - if (gstart.edgeCount() == 0) - return false; - g = gstart; - edgeDistribution.param( - std::uniform_int_distribution<>::param_type(0, g.edgeCount() - 1)); - return true; - } - - bool doMove() { - int e1index, e2index; - int timeout = 0; - // Keep regenerating while conflicting edges - do { - e1index = edgeDistribution(mt); - e2index = edgeDistribution(mt); - if (++timeout % 100 == 0) { - std::cerr << "Warning: sampled " << timeout - << " random edges but they keep conflicting.\n"; - } - } while (edgeConflicts(g.getEdge(e1index), g.getEdge(e2index))); - - // 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); - } - - Graph g; - std::mt19937 mt; - std::uniform_int_distribution<> edgeDistribution; - //std::uniform_int_distribution<> permutationDistribution; - std::bernoulli_distribution permutationDistribution; -}; - -void getTriangleDegrees(const Graph& g) { - std::vector> trids; - const auto& adj = g.getAdj(); - int triangles = 0; - for (auto& v : adj) { - for (unsigned int i = 0; i < v.size(); ++i) { - for (unsigned int j = i + 1; j < v.size(); ++j) { - if (g.hasEdge({v[i], v[j]})) { - ++triangles; - std::array ds = {{v.size(), adj[v[i]].size(), - adj[v[j]].size()}}; - std::sort(ds.begin(), ds.end()); - trids.push_back(ds); - } - } - } - } - assert(triangles % 3 == 0); - return; -} - -// -// Assumes degree sequence does NOT contain any zeroes! -// -// method2 = true -> take highest degree and finish its pairing completely -// method2 = false -> take new highest degree after every pairing -template -bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, RNG& 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(); - - // degree, vertex index - std::vector> degrees(n); - for (unsigned int i = 0; i < n; ++i) { - degrees[i].first = ds[i]; - degrees[i].second = i; - } - - std::vector available; - available.reserve(n); - - // Clear the graph - g.reset(n); - - 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; - auto uIter = degrees.begin(); - for (auto iter = degrees.begin(); iter != degrees.end(); ++iter) { - if (iter->first >= dmax) { - dmax = iter->first; - uIter = iter; - } - } - - if (dmax > degrees.size() - 1) - return false; - - if (dmax == 0) { - std::cerr << "ERROR 1 in GCM.\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 and to which - // u has not paired yet! - available.clear(); - for (auto iter = degrees.begin(); iter != degrees.end(); ++iter) { - if (iter->second != u && !g.hasEdge({u, iter->second})) - available.push_back(iter); - } - if (available.empty()) - return false; - std::uniform_int_distribution<> distr(0, available.size() - 1); - auto vIter = available[distr(rng)]; - // pair u to v - if (vIter->first == 0) - std::cerr << "ERROR 2 in GCM1.\n"; - if (!g.addEdge({u, 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 - // Erasure invalidates all iterators AFTER the erased one - if (vIter > uIter) { - degrees.erase(vIter); - degrees.erase(uIter); - } else { - degrees.erase(uIter); - degrees.erase(vIter); - } - } else { - // Remove only v if it reaches zero - uIter->first--; - vIter->first--; - if (vIter->first == 0) - degrees.erase(vIter); - } - //degrees.erase(std::remove_if(degrees.begin(), degrees.end(), - // [](auto x) { return x.first == 0; })); - } - } - return true; -} - int main(int argc, char* argv[]) { // Generate a random degree sequence std::mt19937 rng(std::random_device{}()); @@ -208,8 +23,6 @@ int main(int argc, char* argv[]) { 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; std::ofstream outfile;