#CXX=clang++

all: switchchain switchchain_exponent switchchain_initialtris switchchain_dsp

switchchain:

switchchain_exponent:

switchchain_initialtris:

switchchain_dsp:

# 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; }

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

    }

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

        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)

#include "exports.hpp"

#include "graph.hpp"

#include "powerlaw.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)));

        // Consider one of the three possible permutations

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

        bool switchType = permutationDistribution(mt);

        return g.exchangeEdges(e1index, e2index, switchType);

    }

    Graph g;

    std::mt19937 mt;

    std::uniform_int_distribution<> edgeDistribution;

    //std::uniform_int_distribution<> permutationDistribution;

    std::bernoulli_distribution permutationDistribution;

};

void getTriangleDegrees(const Graph& g) {

    std::vector<std::array<std::size_t,3>> trids;

    const auto& adj = g.getAdj();

    int triangles = 0;

    for (auto& v : adj) {

        for (unsigned int i = 0; i < v.size(); ++i) {

            for (unsigned int j = i + 1; j < v.size(); ++j) {

                if (g.hasEdge({v[i], v[j]})) {

                    ++triangles;

                    std::array<std::size_t, 3> ds = {{v.size(), adj[v[i]].size(),

                                                     adj[v[j]].size()}};

                    std::sort(ds.begin(), ds.end());

                    trids.push_back(ds);

                }

            }

        }

    }

    assert(triangles % 3 == 0);

    return;

}

//

// Assumes degree sequence does NOT contain any zeroes!

//

// method2 = true  -> take highest degree and finish its pairing completely

// method2 = false -> take new highest degree after every pairing

template <typename RNG>

bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, RNG& rng, bool method2) {

    // Similar to Havel-Hakimi but instead of pairing up with the highest ones

    // that remain, simply pair up with random ones

    unsigned int n = ds.size();

    // degree, vertex index