AENC/switchchain Changeset - b8a998539881 · Centrum Wiskunde & Informatica (CWI)

Changeset - b8a998539881

Parent rev.

Child rev.

[Not reviewed]

0 3 1

Tom Bannink - 8 years ago 2017-06-10 18:23:10
tombannink@gmail.com

Add class to compute graph spectrum

4 files changed with 77 insertions and 4 deletions:

cpp/Makefile

cpp/graph.hpp

cpp/graph_spectrum.hpp

cpp/switchchain.cpp

0 comments (0 inline, 0 general)

cpp/Makefile

➞

Show inline comments

 #CXX=clang++
 INCLUDES += -I.
 CXXFLAGS += -std=c++14 -O3 -Wall -Wextra -Wfatal-errors -Werror -pedantic -Wno-deprecated-declarations $(INCLUDES)
 INCLUDES += -I. \
 			-I/usr/include/eigen3
 CXXFLAGS += -std=c++14 -O3
 CXXFLAGS += -Wall -Wextra -Wfatal-errors -Werror -pedantic -Wno-deprecated-declarations
 CXXFLAGS += $(INCLUDES)
 # Disable Eigen's debug info and disable a warning generated by Eigen
 CXXFLAGS += -DNDEBUG
 CXXFLAGS += -Wno-int-in-bool-context
 all: switchchain switchchain_exponent switchchain_initialtris switchchain_dsp
 switchchain:
 switchchain_exponent:
 switchchain_initialtris:
 switchchain_dsp:
 # target : dep1 dep2 dep3
 # 	$@ = target
 # 	$< = dep1
 # 	$^ = dep1 dep2 dep3

cpp/graph.hpp

➞

Show inline comments

@@ @@ -13,96 +13,98 @@ class Edge { @@
 };
 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;
     unsigned int out;
 };
 typedef std::vector<unsigned int> DegreeSequence;
 typedef std::vector<DiDegree> DiDegreeSequence;
 class Graph {
   public:
     Graph() {}
     Graph(unsigned int n) { reset(n); }
     ~Graph() {}
     // 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].e; }
     const auto& getAdj() const { return adj; }
     const auto& getBooleanAdj() const { return badj; }
     // 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
         // Based on Erdos-Gallai theorem
         unsigned int n = d.size();
         // degree, vertex index
         std::vector<std::pair<unsigned int, unsigned int>> degrees(n);
         for (unsigned int i = 0; i < n; ++i) {
             degrees[i].first = d[i];
             degrees[i].second = i;
+        }
         // Clear the graph
         reset(n);
         while (!degrees.empty()) {
             std::sort(degrees.begin(), degrees.end());
             // Highest degree is at back of the vector
             // Take it out
             unsigned int degree = degrees.back().first;
             unsigned int u = degrees.back().second;
             degrees.pop_back();
             if (degree > degrees.size()) {
                 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})) {
                     return false;
+                }
                 rit->first--;
                 ++rit;
+            }
+        }
         return true;
+    }
     DegreeSequence getDegreeSequence() const {
         DegreeSequence d(adj.size());
         std::transform(adj.begin(), adj.end(), d.begin(),
                        [](const auto &u) { return u.size(); });
         return d;
+    }

cpp/graph_spectrum.hpp

➞

Show inline comments

@@ new file 100644 @@
 #include "graph.hpp"
 #include <Eigen/Dense>
 #include <Eigen/Eigenvalues>
 using MatrixType =
     Eigen::Matrix<float, Eigen::Dynamic, Eigen::Dynamic, Eigen::RowMajor>;
 // A: Adjacency matrix
 //    lambda_max <= d_max
 //
 // L: Laplacian
 //    L = D - A
 ///
 // P: Random walk matrix
 //    lambda_max = 1
 class GraphSpectrum {
   public:
     GraphSpectrum(const Graph& g) : graph(g) {}
     ~GraphSpectrum() {}
     std::vector<float> computeAdjacencySpectrum() const {
         // matrix stored as std::vector<std::vector<bool>>
         auto& badj = graph.getBooleanAdj();
         // Convert it to MatrixType
         auto n = badj.size();
         MatrixType m(n, n);
         for (auto i = 0u; i < n; ++i)
             for (auto j = 0u; j < n; ++j)
                 m(i, j) = badj[i][j] ? 1.0f : 0.0f;
         return getEigenvalues_(m);
+    }
     std::vector<float> computeLaplacianSpectrum() const {
         // matrix stored as std::vector<std::vector<bool>>
         auto& badj = graph.getBooleanAdj();
         auto& adj = graph.getAdj();
         // - A
         auto n = badj.size();
         MatrixType m(n, n);
         for (auto i = 0u; i < n; ++i)
             for (auto j = 0u; j < n; ++j)
                 m(i, j) = badj[i][j] ? -1.0f : 0.0f;
         // + D
         for (auto i = 0u; i < n; ++i)
             m(i, i) = float(adj[i].size());
         return getEigenvalues_(m);
+    }
   private:
     const Graph& graph;
     std::vector<float> getEigenvalues_(const MatrixType& m) const {
         Eigen::SelfAdjointEigenSolver<MatrixType> es(
             m, Eigen::DecompositionOptions::EigenvaluesOnly);
         auto ev = es.eigenvalues();
         return std::vector<float>(ev.data(), ev.data() + ev.rows() * ev.cols());
+    }
 };

cpp/switchchain.cpp

➞

Show inline comments

 #include "exports.hpp"
 #include "graph.hpp"
 #include "powerlaw.hpp"
 #include "graph_spectrum.hpp"
 #include <algorithm>
 #include <array>
 #include <fstream>
 #include <iostream>
 #include <numeric>
 #include <random>
 #include <vector>
 // Its assumed that u,v are distinct.
 // Check if all four vertices are distinct
 bool edgeConflicts(const Edge& e1, const Edge& e2) {
     return (e1.u == e2.u || e1.u == e2.v || e1.v == e2.u || e1.v == e2.v);
+}
 class SwitchChain {
   public:
     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());
+    }
     ~SwitchChain() {}
     bool initialize(const Graph& gstart) {
         if (gstart.edgeCount() == 0)
             return false;
         g = gstart;
         edgeDistribution.param(
             std::uniform_int_distribution<>::param_type(0, g.edgeCount() - 1));
         return true;
+    }
     bool doMove() {
         int e1index, e2index;
         int timeout = 0;
         // Keep regenerating while conflicting edges
         do {
             e1index = edgeDistribution(mt);
             e2index = edgeDistribution(mt);
             if (++timeout % 100 == 0) {
                 std::cerr << "Warning: sampled " << timeout
                           << " random edges but they keep conflicting.\n";
+            }
         } while (edgeConflicts(g.getEdge(e1index), g.getEdge(e2index)));

0 comments (0 inline, 0 general)