diff --git a/cpp/switchchain.cpp b/cpp/switchchain.cpp index 25b3fe70a86d760de72c089966eb1d7c90724457..2b2a5efafb28ed999295cd523ccbd8ab3b981c0e 100644 --- a/cpp/switchchain.cpp +++ b/cpp/switchchain.cpp @@ -1,3 +1,4 @@ +#include #include #include #include @@ -32,22 +33,30 @@ typedef std::vector DiDegreeSequence; class Graph { public: - Graph() : edgeCount(0) {} + Graph() {} - Graph(int n) : edgeCount(0) { adj.resize(n); } + Graph(int n) { adj.resize(n); } ~Graph() {} - bool createFromSequence(const DegreeSequence &d) { - edgeCount = std::accumulate(d.begin(), d.end(), 0); - + bool createFromDegreeSequence(const DegreeSequence &d) { // // TODO // - + // See + // http://stackoverflow.com/questions/13102738/creating-graphs-using-a-degree-sequence + // See https://en.wikipedia.org/wiki/Havel%E2%80%93Hakimi_algorithm + (void)d; return false; } + DegreeSequence getDegreeSequence() const { + DegreeSequence d(adj.size()); + std::transform(adj.begin(), adj.end(), d.begin(), + [](const auto &u) { return u.size(); }); + return d; + } + bool hasEdge(const Edge &e) const { for (int v : adj[e.u]) { if (v == e.v) @@ -56,6 +65,15 @@ class Graph { return false; } + bool addEdge(const Edge &e) { + if (hasEdge(e)) + return false; + edges.push_back(e); + adj[e.u].push_back(e.v); + adj[e.v].push_back(e.u); + return true; + } + // There are two possible edge exchanges // switchType indicates which one is desired // Returns false if the switch is not possible @@ -132,23 +150,31 @@ class Graph { // The two should be kept consistent at all times std::vector> adj; std::vector edges; - int edgeCount; }; class SwitchChain { public: - SwitchChain() : permutationDistribution(0, 2) { + SwitchChain() : mt(std::random_device{}()), permutationDistribution(0, 2) { // random_device uses hardware entropy if available - std::random_device rd; - mt.seed(rd()); + // std::random_device rd; + // mt.seed(rd()); } ~SwitchChain() {} bool initialize(const DegreeSequence &d) { - if (!g.createFromSequence(d)) + if (!g.createFromDegreeSequence(d)) return false; edgeDistribution.param( - std::uniform_int_distribution<>::param_type(0, g.edgeCount - 1)); + std::uniform_int_distribution<>::param_type(0, g.edges.size() - 1)); + return true; + } + + bool initialize(const Graph &gstart) { + if (gstart.edges.size() == 0) + return false; + g = gstart; + edgeDistribution.param( + std::uniform_int_distribution<>::param_type(0, g.edges.size() - 1)); return true; } @@ -188,19 +214,28 @@ class SwitchChain { }; int main() { + Graph g(6); + g.addEdge({0, 1}); + g.addEdge({0, 2}); + g.addEdge({0, 3}); + g.addEdge({2, 3}); + g.addEdge({3, 4}); + g.addEdge({3, 5}); + SwitchChain chain; - if (!chain.initialize({3, 2, 4, 2, 2, 1})) { + if (!chain.initialize(g)) { std::cerr << "Could not initialize Markov chain.\n"; return 1; } std::cout << "Starting switch Markov chain" << std::endl; int movesDone = 0; - for (int i = 0; i < 100; ++i) + int movesTotal = 10000; + for (int i = 0; i < movesTotal; ++i) if (chain.doMove()) ++movesDone; - std::cout << movesDone << "/100 moves succeeded." << std::endl; + std::cout << movesDone << '/' << movesTotal << " moves succeeded." << std::endl; return 0; }