main.h 1.77 KB
Newer Older
1 2 3 4 5
#include <iostream>
#include <vector>
#include <random>
#include <queue>
#include <set>
6
#include <unordered_set>
7 8 9

using namespace std;

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
template<class T>
struct nullable
{ 
    T v;
    bool null;

    nullable() : null(false) { };
    nullable(T t) : v(t), null(false) { };
};

class MinCutGraph
{
public:
    vector<nullable<pair<int, int>>> edges;
    vector<nullable<unordered_set<int>>> nodes;
    MinCutGraph(vector<int>* adjacency, int n);
    void Merge(int nMerge, mt19937& rng);
private:
    void Check();
    void RenumEdges();
    void RenumNodes();
};


34 35 36
class Graph
{
public:
37
    Graph(int size, int k, int maxPeers, mt19937& rng);
38 39 40
    ~Graph() { delete[] adjacency; };

    void GetDistancesFrom(int node, int* distance);
41
    int GetMinCut();
42 43 44
    int CountUnreachableFrom(int node);

    void KillMachines(float proportion);
45 46
    //void SplitAS(float proportionAS1, float proportionAS2);

47 48 49
    vector<int>* adjacency;
    int size;
private:
50 51
    int GetMinCut(MinCutGraph& graph);

52
    uniform_int_distribution<int> distrib;
53
    mt19937& generator;
54 55
};

56 57 58 59 60 61 62
class Results
{
public:
    Results(int maxArity, int maxDistance);
    ~Results();

    void UpdateArity(const Graph& graph);
63
    void AddAccessibilitySample(double accessibility);
64 65 66 67 68
    void UpdateDistance(int* distance, int nSamples);
    void Finalise();

    double* arityDistrib;
    double* distanceDistrib;
69
    double avgDistance;
70
    double avgAccessibility;
71
    int maxDistanceReached;
72
    int minKConnexity;
73

74 75 76 77
    double disconnectionProba;
    double arityTooBig;
    double distanceTooBig;
    int64_t disconnected;
78
    
79 80 81 82 83 84
    int maxArity;
    int maxDistance;

private:
    void AddAritySample(int arity);
    void AddDistanceSample(int distance);
85

86 87
    int64_t nAritySample;
    int64_t nDistanceSample;
88
    int64_t nAccessibilitySample;
89
};