diff --git a/cpp/exports.hpp b/cpp/exports.hpp index 8be142765b6e1d9e4d7aafa700f6d8b67d67655a..c6128061badfc045b382378814af6b0c2921cf88 100644 --- a/cpp/exports.hpp +++ b/cpp/exports.hpp @@ -1,4 +1,5 @@ #pragma once +#include #include "graph.hpp" std::ostream &operator<<(std::ostream &s, const Edge &e) { diff --git a/cpp/graph.hpp b/cpp/graph.hpp index a6c5ea22dffe491607b800b87a7d540be013d5ea..f17e7a43d51d97356827405ba26fbfd48d1ebf2b 100644 --- a/cpp/graph.hpp +++ b/cpp/graph.hpp @@ -1,4 +1,5 @@ #pragma once +#include #include #include @@ -35,7 +36,6 @@ class Graph { unsigned int edgeCount() const { return edges.size(); } - Edge &getEdge(unsigned int i) { return edges[i]; } const Edge &getEdge(unsigned int i) const { return edges[i]; } bool createFromDegreeSequence(const DegreeSequence &d) { @@ -178,6 +178,21 @@ class Graph { return true; } + int countTriangles() const { + 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 (hasEdge({v[i], v[j]})) { + ++triangles; + } + } + } + } + assert(triangles % 3 == 0); + return triangles / 3; + } + private: // Graph is saved in two formats for speed // The two should be kept consistent at all times diff --git a/cpp/showgraphs.m b/cpp/showgraphs.m index 8d0daf467e86d15e6db6885e3359cf74adceffe5..0bfb52839469439e7be1f2dd7ce663204fc5513e 100644 --- a/cpp/showgraphs.m +++ b/cpp/showgraphs.m @@ -3,8 +3,11 @@ gsraw=Import[NotebookDirectory[]<>"graphdata.m"]; -gs=Map[Graph[#,GraphLayout->"CircularEmbedding"]&,gsraw]; -gs2=Map[Graph[#,GraphLayout->Automatic]&,gsraw]; +ListPlot[gsraw[[2]],Joined->True,PlotRange->All,AxesLabel->{"Step","Triangles"}] + + +gs=Map[Graph[#,GraphLayout->"CircularEmbedding"]&,gsraw[[1]]]; +gs2=Map[Graph[#,GraphLayout->Automatic]&,gsraw[[1]]]; Grid[Partition[gs,10],Frame->All] diff --git a/cpp/switchchain.cpp b/cpp/switchchain.cpp index 436dc7a20821815e95ec973e42b11561b121fa49..f04edcc8adb2969cddb286f0b1183810f3345c5f 100644 --- a/cpp/switchchain.cpp +++ b/cpp/switchchain.cpp @@ -104,18 +104,24 @@ int main() { } std::ofstream outfile("graphdata.m"); + outfile << '{'; outfile << '{' << g; std::cout << "Starting switch Markov chain" << std::endl; int movesDone = 0; - int movesTotal = 100000; + constexpr int movesTotal = 10000; + int triangles[movesTotal]; for (int i = 0; i < movesTotal; ++i) { if (chain.doMove()) ++movesDone; + triangles[i] = chain.g.countTriangles(); if (i % (movesTotal / 50) == (movesTotal / 50 - 1)) outfile << ',' << chain.g; } - outfile << '}'; + outfile << '}' << ',' << '{' << triangles[0]; + for (int i = 1; i < movesTotal; ++i) + outfile << ',' << triangles[i]; + outfile << '}' << '}'; std::cout << movesDone << '/' << movesTotal << " moves succeeded." << std::endl;