Changeset - 0c08dc618491
Parent rev.
Child rev.
[Not reviewed]
0 2 0
Tom Bannink - 8 years ago 2017-03-13 12:31:42
tom.bannink@cwi.nl
Add triple degenerate graph representation
2 files changed with 132 insertions and 106 deletions:
cpp/graph.hpp
131
87
cpp/switchchain.cpp
1
19
0 comments (0 inline, 0 general)
cpp/graph.hpp
➞
Show inline comments
 
@@ -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()) {

			




	
	
	
		
 
    // 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;

			




	
	
	
		
 
            }

			




	
	
	
		
 
        }

			




	
	
	
		
 
        // First check if the move is possible

			




	
	
	
		
 
        if (hasEdge({e1.u, e2.u}) || hasEdge({e1.v, e2.v}))

			




	
	
	
		
 
            return false; // conflicting edges

			




	
	
	
		
 

			




	
	
	
		
 
        // 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});

			




	
	
	
		
 
        }

			




	
	
	
		
 
        // 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;

			




	
	
	
		
 
};

			




	
	
	
		
 

			




        

    


    
    

    

        

                

                    cpp/switchchain.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -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;

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: kalli-3806679
    
    
        This site is powered by
            Kallithea,
        which is
        © 2010–2022 by various authors & licensed under GPLv3.
            – Support