From 0c08dc6184912b4360c611464a05db1c392f7afc 2017-03-13 12:31:42
From: Tom Bannink <tom.bannink@cwi.nl>
Date: 2017-03-13 12:31:42
Subject: [PATCH] Add triple degenerate graph representation

---

diff --git a/cpp/graph.hpp b/cpp/graph.hpp
index b060f19362e37e55d009fc1f64820d77bc77c868..43376b42fe91d6530be954d9d53d9b491801ca6b 100644
--- a/cpp/graph.hpp
+++ b/cpp/graph.hpp
@@ -3,6 +3,7 @@
 #include <cassert>
 #include <numeric>
 #include <vector>
+#include <iostream>
 
 class Edge {
   public:
@@ -11,6 +12,15 @@ class Edge {
     bool operator==(const Edge &e) const { return u == e.u && v == e.v; }
 };
 
+class StoredEdge {
+  public:
+    Edge e;
+    // indices into adjacency lists
+    // adj[u][u2vindex] = v;
+    // adj[v][v2uindex] = u;
+    unsigned int u2vindex, v2uindex;
+};
+
 class DiDegree {
   public:
     unsigned int in;
@@ -24,21 +34,30 @@ class Graph {
   public:
     Graph() {}
 
-    Graph(unsigned int n) { adj.resize(n); }
+    Graph(unsigned int n) { reset(n); }
 
     ~Graph() {}
 
-    void resize(unsigned int n) {
-        if (n < adj.size()) {
-            edges.clear();
-        }
+    // Clears any previous edges and create
+    // an empty graph on n vertices
+    void reset(unsigned int n) {
+        edges.clear();
         adj.resize(n);
+        for (auto &v : adj)
+            v.clear();
+        badj.resize(n);
+        for (auto &v : badj) {
+            v.resize(n);
+            v.assign(n, false);
+        }
     }
 
     unsigned int edgeCount() const { return edges.size(); }
 
-    const Edge &getEdge(unsigned int i) const { return edges[i]; }
+    const Edge &getEdge(unsigned int i) const { return edges[i].e; }
 
+    // When the degree sequence is not graphics, the Graph can be
+    // in any state, it is not neccesarily empty
     bool createFromDegreeSequence(const DegreeSequence &d) {
         // Havel-Hakimi algorithm
 
@@ -51,8 +70,9 @@ class Graph {
             degrees[i].second = i;
         }
 
-        edges.clear();
-        adj.resize(n);
+        // Clear the graph
+        reset(n);
+
         while (!degrees.empty()) {
             std::sort(degrees.begin(), degrees.end());
             // Highest degree is at back of the vector
@@ -61,16 +81,12 @@ class Graph {
             unsigned int u = degrees.back().second;
             degrees.pop_back();
             if (degree > degrees.size()) {
-                edges.clear();
-                adj.clear();
                 return false;
             }
             // Now loop over the last 'degree' entries of degrees
             auto rit = degrees.rbegin();
             for (unsigned int i = 0; i < degree; ++i) {
                 if (rit->first == 0 || !addEdge({u, rit->second})) {
-                    edges.clear();
-                    adj.clear();
                     return false;
                 }
                 rit->first--;
@@ -89,18 +105,19 @@ class Graph {
 
     // Assumes valid vertex indices
     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;
-        }
-        return false;
+        return badj[e_.u][e_.v];
+        //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;
+        //}
+        //return false;
     }
 
     bool addEdge(const Edge &e) {
@@ -108,81 +125,60 @@ class Graph {
             return false;
         if (hasEdge(e))
             return false;
-        edges.push_back(e);
+        StoredEdge se;
+        se.e = e;
+        se.u2vindex = adj[e.u].size();
+        se.v2uindex = adj[e.v].size();
         adj[e.u].push_back(e.v);
         adj[e.v].push_back(e.u);
+        edges.push_back(se);
+        badj[e.u][e.v] = 1;
+        badj[e.v][e.u] = 1;
         return true;
     }
 
     // There are two possible edge exchanges
     // switchType indicates which one is desired
     // Returns false if the switch is not possible
-    bool exchangeEdges(const Edge &e1, const Edge &e2, bool switchType) {
+    bool exchangeEdges(unsigned int e1index, unsigned int e2index, bool switchType) {
+        StoredEdge &se1 = edges[e1index];
+        StoredEdge &se2 = edges[e2index];
+        const Edge &e1 = se1.e;
+        const Edge &e2 = se2.e;
+
         // The new edges configuration is one of these two
         // A) e1.u - e2.u and e1.v - e2.v
-        // B) e1.u - e2.v and e1.v - e2.u
-        // First check if the move is possible
+        // B) e1.u - e2.v and e2.u - e1.v
+        // Note that to do (B) instead of (A), simply swap e2.u <-> e2.v
+        // Now we can just consider switch type (A)
+        switchType = false;
         if (switchType) {
-            if (hasEdge({e1.u, e2.u}) || hasEdge({e1.v, e2.v}))
-                return false; // conflicting edges
-        } else {
-            if (hasEdge({e1.u, e2.v}) || hasEdge({e1.v, e2.u}))
-                return false; // conflicting edges
+            std::swap(se2.e.u, se2.e.v);
+            std::swap(se2.u2vindex, se2.v2uindex);
         }
 
-        // Find the edges in the adjacency lists
-        unsigned int i1, j1, i2, j2;
-        for (i1 = 0; i1 < adj[e1.u].size(); ++i1) {
-            if (adj[e1.u][i1] == e1.v)
-                break;
-        }
-        for (j1 = 0; j1 < adj[e1.v].size(); ++j1) {
-            if (adj[e1.v][j1] == e1.u)
-                break;
-        }
-        for (i2 = 0; i2 < adj[e2.u].size(); ++i2) {
-            if (adj[e2.u][i2] == e2.v)
-                break;
-        }
-        for (j2 = 0; j2 < adj[e2.v].size(); ++j2) {
-            if (adj[e2.v][j2] == e2.u)
-                break;
-        }
-
-        // Remove the old edges
-        bool removedOne = false;
-        for (auto iter = edges.begin(); iter != edges.end();) {
-            if (*iter == e1) {
-                iter = edges.erase(iter);
-                if (removedOne)
-                    break;
-                removedOne = true;
-            } else if (*iter == e2) {
-                iter = edges.erase(iter);
-                if (removedOne)
-                    break;
-                removedOne = true;
-            } else {
-                ++iter;
-            }
-        }
-
-        // Add the new edges
-        if (switchType) {
-            adj[e1.u][i1] = e2.u;
-            adj[e1.v][j1] = e2.v;
-            adj[e2.u][i2] = e1.u;
-            adj[e2.v][j2] = e1.v;
-            edges.push_back({e1.u, e2.u});
-            edges.push_back({e1.v, e2.v});
-        } else {
-            adj[e1.u][i1] = e2.v;
-            adj[e1.v][j1] = e2.u;
-            adj[e2.u][i2] = e1.v;
-            adj[e2.v][j2] = e1.u;
-            edges.push_back({e1.u, e2.v});
-            edges.push_back({e1.v, e2.u});
-        }
+        // First check if the move is possible
+        if (hasEdge({e1.u, e2.u}) || hasEdge({e1.v, e2.v}))
+            return false; // conflicting edges
+
+        // Clear old edges
+        badj[e1.u][e1.v] = false;
+        badj[e1.v][e1.u] = false;
+        badj[e2.u][e2.v] = false;
+        badj[e2.v][e2.u] = false;
+
+        adj[e1.u][se1.u2vindex] = e2.u;
+        adj[e1.v][se1.v2uindex] = e2.v;
+        adj[e2.u][se2.u2vindex] = e1.u;
+        adj[e2.v][se2.v2uindex] = e1.v;
+        // Carefull: when updating se1,se2 also e1 and 2e change
+        std::swap(se1.e.v, se2.e.u);
+        std::swap(se1.v2uindex, se2.u2vindex);
+        // e1 and e2 now contain the NEW edges!!
+        badj[e1.u][e1.v] = true;
+        badj[e1.v][e1.u] = true;
+        badj[e2.u][e2.v] = true;
+        badj[e2.v][e2.u] = true;
         return true;
     }
 
@@ -201,10 +197,58 @@ class Graph {
         return triangles / 3;
     }
 
+    // Should return zero
+    int consistencyCheck() const {
+        // Check if info in 'edges' is present
+        // in adj and badj
+        for (auto &se : edges) {
+            if (se.e.u >= adj.size() || se.e.v >= adj.size())
+                return 1;
+            if (!badj[se.e.u][se.e.v])
+                return 2;
+            if (!badj[se.e.v][se.e.u])
+                return 3;
+            if (se.u2vindex >= adj[se.e.u].size())
+                return 4;
+            if (se.v2uindex >= adj[se.e.v].size())
+                return 5;
+            if (adj[se.e.u][se.u2vindex] != se.e.v)
+                return 6;
+            if (adj[se.e.v][se.v2uindex] != se.e.u)
+                return 7;
+        }
+        // Check if info in 'adj' is present
+        // in badj and edges
+        for (unsigned int u = 0; u < adj.size(); ++u) {
+            for (unsigned int v : adj[u]) {
+                if (!badj[u][v])
+                    return 8;
+                if (!badj[v][u])
+                    return 9;
+                // Check if it appears in edges
+                bool found = false;
+                for (auto &se : edges) {
+                    if ((se.e.u == u && se.e.v == v) ||
+                        (se.e.u == v && se.e.v == u)) {
+                        found = true;
+                        break;
+                    }
+                }
+                if (!found)
+                    return 10;
+            }
+        }
+        // Check if info in 'badj' is present
+        // in adj and edges
+        // TODO
+        return 0;
+    }
+
   private:
-    // Graph is saved in two formats for speed
-    // The two should be kept consistent at all times
+    // Graph is saved in three formats for speed
+    // They should be kept consistent at all times
     std::vector<std::vector<unsigned int>> adj;
-    std::vector<Edge> edges;
+    std::vector<std::vector<bool>> badj; // symmetric binary matrix
+    std::vector<StoredEdge> edges;
 };
 
diff --git a/cpp/switchchain.cpp b/cpp/switchchain.cpp
index 8636b77157077b6bc1007496077d998cd1e1ab31..559d9fa4814dbd2f820d3479cb823654384822fc 100644
--- a/cpp/switchchain.cpp
+++ b/cpp/switchchain.cpp
@@ -56,26 +56,8 @@ class SwitchChain {
         // 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 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
-        }
-
-        // 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);
+        return g.exchangeEdges(e1index, e2index, switchType);
     }
 
     Graph g;