diff --git a/cpp/graph.hpp b/cpp/graph.hpp index feac06b5febbcda3f9b3e78018181e7022f55e9a..b060f19362e37e55d009fc1f64820d77bc77c868 100644 --- a/cpp/graph.hpp +++ b/cpp/graph.hpp @@ -88,7 +88,14 @@ class Graph { } // Assumes valid vertex indices - bool hasEdge(const Edge &e) const { + bool hasEdge(const Edge& e_) const { + Edge e; + if (adj[e_.u].size() <= adj[e_.v].size()) { + e = e_; + } else { + e.u = e_.v; + e.v = e_.u; + } for (unsigned int v : adj[e.u]) { if (v == e.v) return true; 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 diff --git a/showgraphs.m b/showgraphs.m index 48127315c852e3851039ad2d997733725205fc14..f4e1275e013b13cfb135af99cdaf0bfa59a9e57f 100644 --- a/showgraphs.m +++ b/showgraphs.m @@ -17,7 +17,7 @@ Needs["ErrorBarPlots`"] (* (a) Don't remove/add edges from the std::vector. Simply replace them*) (* (b) Better direct triangle counting? (I doubt it)*) (* (b') Better triangle counting by only keeping track of CHANGES in #triangles*) -(* (c) Do not choose the three permutations with 1/3 probability: choose the "staying" one with a very low probability. Should still be a valid switch chain?*) +(* (c) Do not choose the three permutations with 1/3 probability: choose the "staying" one with zero probability. Should still be a valid switch chain?*) (**) (*- Experimental mixing time as function of n. At (n,tau)=(1000,2.5) it seems to be between 10.000 and 20.000 steps.*) (**) @@ -62,7 +62,7 @@ Grid[Partition[gs,10],Frame->All] (*Data import and data merge*) -gsraw=Import[NotebookDirectory[]<>"data/min_deg_two/graphdata_merged.m"]; +gsraw=Import[NotebookDirectory[]<>"data/graphdata_merged.m"]; gsraw=SortBy[gsraw,#[[1,1]]&]; (* Sort by n *) @@ -70,9 +70,9 @@ gdata=GatherBy[gsraw,{#[[1,2]]&,#[[1,1]]&}]; (* gdata[[ tau index, n index, run index , {ntau, #tris, ds} ]] *) -newData=Import[NotebookDirectory[]<>"graphdata_tau_multi4.m"]; -mergedData=Import[NotebookDirectory[]<>"graphdata_merged.m"]; -Export[NotebookDirectory[]<>"graphdata_merged_new.m",Join[mergedData,newData]] +newData=Import[NotebookDirectory[]<>"data/graphdata_3.m"]; +mergedData=Import[NotebookDirectory[]<>"data/graphdata_merged.m"]; +Export[NotebookDirectory[]<>"data/graphdata_merged_new.m",Join[mergedData,newData]] (* ::Subsection:: *) @@ -151,12 +151,6 @@ ErrorListPlot[averagesErrorBars,Joined->True,PlotMarkers->Automatic,AxesLabel->{ ListLogLogPlot[averagesErrorBars[[All,All,1]],Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels] -averagesErrorBars=Map[ -{{Log[#[[1,1,1]]],Log[Mean[#[[All,2]]]]}, -ErrorBar[ (StandardDeviation[#[[All,2]]] )] -}&,averagesGrouped,{2}]; - - (* ::Subsection:: *) (*Fitting the log-log-plot*)