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:

cpp/graph.hpp

➞

Show inline comments

@@ @@ -49,24 +49,26 @@ class Graph { @@
         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];

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

0 comments (0 inline, 0 general)