main.h 2.01 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
template<class T>
struct nullable
12
{
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
    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
    ~Graph() { delete[] adjacency; delete[] generated; };
39 40

    void GetDistancesFrom(int node, int* distance);
41 42
    int AddEdge(int from, unordered_set<int>& alreadyConnected);
    int RemoveEdge(int from, int to);
43
    int GetMinCut();
44
    int CountUnreachableFrom(int node);
45
    void GetRoutesFrom(int node, int* distance, float* routesCount);
46 47

    void KillMachines(float proportion);
48 49
    //void SplitAS(float proportionAS1, float proportionAS2);

50
    vector<int>* adjacency;
51
    vector<int>* generated;
52 53
    int size;
private:
54 55
    int GetMinCut(MinCutGraph& graph);

56
    uniform_int_distribution<int> distrib;
57
    mt19937& generator;
58 59
    int maxPeers;
    int k;
60 61
};

62 63 64 65 66 67 68
class Results
{
public:
    Results(int maxArity, int maxDistance);
    ~Results();

    void UpdateArity(const Graph& graph);
69
    void AddAccessibilitySample(double accessibility);
70 71 72 73 74
    void UpdateDistance(int* distance, int nSamples);
    void Finalise();

    double* arityDistrib;
    double* distanceDistrib;
75
    double avgDistance;
76
    double avgAccessibility;
77
    int maxDistanceReached;
78
    int minKConnexity;
79

80 81 82 83
    double disconnectionProba;
    double arityTooBig;
    double distanceTooBig;
    int64_t disconnected;
84

85 86 87 88 89 90
    int maxArity;
    int maxDistance;

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

92 93
    int64_t nAritySample;
    int64_t nDistanceSample;
94
    int64_t nAccessibilitySample;
95
};