#CXX=clang++

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

TARGETS += switchchain

TARGETS += switchchain_canonical_properties

TARGETS += switchchain_ccm_initialtris

TARGETS += switchchain_ccm_timeevol

TARGETS += switchchain_properties

TARGETS += switchchain_exponent

TARGETS += switchchain_mixingtime

TARGETS += switchchain_spectrum

TARGETS += switchchain_successrates

TARGETS += switchchain_timeevol

all: $(TARGETS)

clean:

	rm -f $(TARGETS)

# target : dep1 dep2 dep3

# 	$@ = target

# 	$< = dep1

# 	$^ = dep1 dep2 dep3

#pragma once

#include <algorithm>

#include <cassert>

#include <numeric>

#include <vector>

#include <iostream>

class Edge {

  public:

    unsigned int u, v;

    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;

    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()) {

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

    }

    // Assumes valid vertex indices

    bool hasEdge(const Edge& e_) const {

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

        if (e.u >= adj.size() || e.v >= adj.size())

            return false;

        if (hasEdge(e))

            return false;

        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(unsigned int e1index, unsigned int e2index,

                       bool switchType, bool trackTriangles = false) {

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

        if (switchType) {

            std::swap(se2.e.u, se2.e.v);

            std::swap(se2.u2vindex, se2.v2uindex);

        }

        // First check if the move is possible

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

            return false; // conflicting edges

        if (trackTriangles) {

            trackedTriangles -= countTriangles(e1);

            trackedTriangles -= countTriangles(e2);

        }

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