diff --git a/cpp/switchchain.cpp b/cpp/switchchain.cpp index 188620c860f59c1cbc8690d1eed0e77dd8bf3262..46c0ec8fee28118b9e38a9a7f3e5bba08d96ba1b 100644 --- a/cpp/switchchain.cpp +++ b/cpp/switchchain.cpp @@ -73,8 +73,8 @@ void getTriangleDegrees(const Graph& g) { 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::array ds = {{v.size(), adj[v[i]].size(), + adj[v[j]].size()}}; std::sort(ds.begin(), ds.end()); trids.push_back(ds); } @@ -90,7 +90,8 @@ void getTriangleDegrees(const Graph& g) { // // method2 = true -> take highest degree and finish its pairing completely // method2 = false -> take new highest degree after every pairing -bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, auto& rng, bool method2) { +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(); @@ -194,7 +195,7 @@ bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, auto& rng, bool meth return true; } -int main() { +int main(int argc, char* argv[]) { // Generate a random degree sequence std::mt19937 rng(std::random_device{}()); @@ -209,11 +210,22 @@ int main() { Graph g1; Graph g2; - std::ofstream outfile("graphdata.m"); + std::ofstream outfile; + + if (argc >= 2) + outfile.open(argv[1]); + else + outfile.open("graphdata.m"); + + if (!outfile.is_open()) { + std::cout << "ERROR: Could not open output file.\n"; + return 1; + } + outfile << '{'; bool outputComma = false; - for (int numVertices = 200; numVertices <= 2000; numVertices += 400) { + for (int numVertices = 500; numVertices <= 500; numVertices += 1000) { for (float tau : tauValues) { DegreeSequence ds(numVertices); @@ -223,7 +235,7 @@ int main() { // For a single n,tau take samples over several instances of // the degree distribution. // 500 samples seems to give reasonable results - for (int degreeSample = 0; degreeSample < 1; ++degreeSample) { + for (int degreeSample = 0; degreeSample < 5; ++degreeSample) { // Generate a graph // might require multiple tries for (int i = 1; ; ++i) { @@ -247,6 +259,7 @@ int main() { } } +#if 0 // // Test the GCM1 and GCM2 success rate // @@ -269,6 +282,9 @@ int main() { g2 = gtemp; } } +#endif + + for (int i = 1; i < 5; ++i) { SwitchChain chain; if (!chain.initialize(g)) { @@ -276,17 +292,6 @@ int main() { return 1; } - SwitchChain chain1, chain2; - bool do1 = true, do2 = true; - if (!chain1.initialize(g1)) { - std::cerr << "Could not initialize Markov chain.\n"; - do1 = false; - } - if (!chain2.initialize(g2)) { - std::cerr << "Could not initialize Markov chain.\n"; - do2 = false; - } - std::cout << "Running n = " << numVertices << ", tau = " << tau << ". \t" << std::flush; @@ -299,28 +304,41 @@ int main() { constexpr int measureSkip = 1; - - int movesDone = 0; + int movesTotal = 0; + int movesSuccess = 0; int triangles[measurements]; for (int i = 0; i < mixingTime; ++i) { - if (chain.doMove()) - ++movesDone; + ++movesTotal; + if (chain.doMove()) { + ++movesSuccess; + } } + + std::vector successRates; + successRates.reserve(measurements * measureSkip); + int successrate = 0; for (int i = 0; i < measurements; ++i) { - for (int j = 0; j < measureSkip; ++j) - if (chain.doMove()) - ++movesDone; + for (int j = 0; j < measureSkip; ++j) { + ++movesTotal; + if (chain.doMove()) { + ++movesSuccess; + ++successrate; + } + } triangles[i] = chain.g.countTriangles(); + + if ((i+1) % 100 == 0) { + successRates.push_back(successrate); + successrate = 0; + } } - std::cout << movesDone << '/' << mixingTime + measurements * measureSkip - << " moves succeeded (" - << 100.0f * float(movesDone) / - float(mixingTime + measurements * measureSkip) - << "%)."; - //std::cout << std::endl; + std::cout << '(' + << 100.0f * float(movesSuccess) / float(movesTotal) + << "% successrate). " << std::flush; + // std::cout << std::endl; if (outputComma) outfile << ',' << '\n'; @@ -330,10 +348,12 @@ int main() { outfile << '{' << '{' << numVertices << ',' << tau << '}'; outfile << ',' << triangles; outfile << ',' << ds; +#if 0 outfile << ',' << greedyTriangles1; outfile << ',' << greedyTriangles2; - if (do1) { + SwitchChain chain1, chain2; + if (chain1.initialize(g1)) { movesDone = 0; SwitchChain& c = chain1; for (int i = 0; i < mixingTime; ++i) { @@ -355,7 +375,7 @@ int main() { outfile << ',' << triangles; } - if (do2) { + if (chain2.initialize(g2)) { movesDone = 0; SwitchChain& c = chain2; for (int i = 0; i < mixingTime; ++i) { @@ -377,10 +397,14 @@ int main() { outfile << ',' << triangles; } +#endif + + outfile << ',' << successRates; outfile << '}' << std::flush; std::cout << std::endl; + } } } }