Explore network growing in a synchronous setting

network-exploration.cpp

#include <vector>
#include <iostream>
#include <map>
#include <random>
#include <numeric>

using namespace std;

mt19937 rng(0);

int MAXIMUM_CONNECTIONS_ALLOWED = 40;
int MINIMUM_OUTBOUND_CONNECTIONS = 5;
int IDEAL_CONNECTIONS_LO = 30;
int IDEAL_CONNECTIONS_HI = 35;

// random number between [0, n)
int my_rand(int n)
{
    std::uniform_int_distribution<int> dist(0, n - 1);
    return dist(rng);
}

struct Stats
{
    bool started;
    int val_min, val_max, val_sum, total;

    Stats()
    {
        started = false;
    }

    void push(int val)
    {
        if (!started)
        {
            started = true;
            val_min = val_max = val_sum = val;
            total = 1;
        }
        else
        {
            val_sum += val;
            val_min = min(val_min, val);
            val_max = max(val_max, val);
            total++;
        }
    }

    double mean()
    {
        return 1. * val_sum / total;
    }

    void print()
    {
        cout.precision(2);
        cout << "Min: " << val_min << endl;
        cout << "Mean: " << fixed << mean() << endl;
        cout << "Max: " << val_max << endl;
    }
};

struct Network
{
    int try_created_edge;
    int removed_edge;
    int created_edge;
    int steps;

    vector<map<int, bool>> adj;
    vector<int> outbound;
    vector<bool> active;

    Network()
    {
        reset_stats();
    }

    void reset_stats()
    {
        try_created_edge = removed_edge = created_edge = steps = 0;
    }

    void add_node()
    {
        adj.push_back({});
        active.push_back(true);
        outbound.push_back(0);
    }

    void kill(int s)
    {
        if (!active[s])
            return;

        active[s] = false;
        for (auto e : adj[s])
        {
            adj[e.first].erase(s);
        }
        adj[s].clear();
    }

    void drop_connection(int u)
    {
        removed_edge++;

        int index = my_rand(adj[u].size());
        int v = -1;
        bool out;

        for (auto it : adj[u])
        {
            if (--index < 0)
            {
                v = it.first;
                out = it.second;
                break;
            }
        }

        assert(index == -1);

        if (out)
            outbound[u]--;
        else
            outbound[v]--;

        adj[u].erase(v);
        adj[v].erase(u);
    }

    void run_establish_connection(int u, int v)
    {
        if (adj[v].size() == MAXIMUM_CONNECTIONS_ALLOWED)
            return;

        created_edge++;
        adj[u][v] = true;
        adj[v][u] = false;
        outbound[u]++;
    }

    // Return false if there is no available peer to establish a connection with
    bool try_to_establish_connection(int u)
    {
        try_created_edge++;
        int v = -1, t = 1;

        for (int i = 0; i < active.size(); ++i)
        {
            if (i == u || !active[i] || adj[u].count(i))
                continue;

            if (my_rand(t++) == 0)
                v = i;
        }

        if (v == -1)
            return false;

        run_establish_connection(u, v);
        return true;
    }

    bool step(int u)
    {
        bool did_something = false;
        int connections = adj[u].size();

        if (connections > IDEAL_CONNECTIONS_HI)
        {
            drop_connection(u);
            return true;
        }

        if (connections < IDEAL_CONNECTIONS_LO || (outbound[u] < MINIMUM_OUTBOUND_CONNECTIONS && connections < MAXIMUM_CONNECTIONS_ALLOWED))
        {
            return try_to_establish_connection(u);
        }

        return false;
    }

    bool step()
    {
        vector<int> order(active.size());
        iota(order.begin(), order.end(), 0);
        shuffle(order.begin(), order.end(), rng);

        for (auto u : order)
            if (active[u] && step(u))
                return true;
        return false;
    }

    int run(int max_steps = -1)
    {
        int cur_steps = 0;
        while (cur_steps != max_steps)
        {
            if (step())
            {
                cur_steps++;
                steps++;
            }
            else
            {
                break;
            }
        }

        return cur_steps;
    }

    // If return -1, the graph is disconnected.
    int diameter()
    {
        vector<int> id(active.size());
        int n = 0;

        for (int i = 0; i < active.size(); ++i)
            if (active[i])
                id[i] = n++;

        vector<vector<int>> mat(n, vector<int>(n, n));
        for (int i = 0; i < n; ++i)
            mat[i][i] = 0;

        for (int i = 0; i < active.size(); ++i)
            if (active[i])
                for (auto e : adj[i])
                    mat[id[i]][id[e.first]] = 1;

        for (int k = 0; k < n; ++k)
        {
            int t = 2;
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                {
                    mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
                    t = max(t, mat[i][j]);
                }
            if (t == 2)
                break;
        }

        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                ans = max(ans, mat[i][j]);

        if (ans == n)
            ans = -1;

        return ans;
    }

    void print()
    {
        cout << endl;
        cout << "Try created edge: " << try_created_edge << endl;
        cout << "Removed edge: " << removed_edge << endl;
        cout << "Created edge: " << created_edge << endl;
        cout << "Steps: " << steps << endl;
        cout << "Diameter: " << diameter() << endl;

        Stats connections, outb;

        for (int i = 0; i < active.size(); ++i)
        {
            if (!active[i])
                continue;

            connections.push(adj[i].size());
            outb.push(outbound[i]);
        }

        cout << "Connections:" << endl;
        connections.print();
        cout << "Outbound:" << endl;
        outb.print();
    }
};

void small_experiment()
{
    MAXIMUM_CONNECTIONS_ALLOWED = 4;
    MINIMUM_OUTBOUND_CONNECTIONS = 1;
    IDEAL_CONNECTIONS_LO = 1;
    IDEAL_CONNECTIONS_HI = 3;

    int INITIAL_NODES = 5;
    int THEN_NODES = 4;

    Network net;
    for (int i = 0; i < INITIAL_NODES; ++i)
    {
        net.add_node();
    }
    net.run();
    net.print();
    net.reset_stats();

    for (int i = 0; i < THEN_NODES; ++i)
    {
        net.add_node();
    }
    net.run();
    net.print();
}

void big_experiment(int initial, int then)
{
    MAXIMUM_CONNECTIONS_ALLOWED = 40;
    MINIMUM_OUTBOUND_CONNECTIONS = 8;
    IDEAL_CONNECTIONS_LO = 30;
    IDEAL_CONNECTIONS_HI = 35;

    int INITIAL_NODES = initial;
    int THEN_NODES = then;

    cout << endl;
    cout << "Big experiment" << endl;
    cout << "Initial nodes: " << INITIAL_NODES << endl;
    cout << "Updating nodes: " << THEN_NODES << endl;

    Network net;
    for (int i = 0; i < INITIAL_NODES; ++i)
    {
        net.add_node();
    }
    net.run();
    net.print();
    net.reset_stats();

    for (int i = 0; i < THEN_NODES; ++i)
    {
        // First is always create
        if (my_rand(2) == 0 && i > 0)
        { // Delete node
            int u = my_rand(net.active.size());
            net.kill(u);
        }
        else
        {
            net.add_node();
        }

        // start organizing while nodes are going in and out.
        net.run(10);
    }
    net.run();
    net.print();
}

int main()
{
    small_experiment();
    big_experiment(100, 50);
    big_experiment(100, 200);
    big_experiment(1000, 1);
}

output.txt

Try created edge: 5
Removed edge: 0
Created edge: 5
Steps: 5
Diameter: 3
Connections:
Min: 1
Mean: 2.00
Max: 3
Outbound:
Min: 1
Mean: 1.00
Max: 1

Try created edge: 5
Removed edge: 1
Created edge: 5
Steps: 6
Diameter: 6
Connections:
Min: 1
Mean: 2.00
Max: 3
Outbound:
Min: 1
Mean: 1.00
Max: 1

Big experiment
Initial nodes: 100
Updating nodes: 50

Try created edge: 1597
Removed edge: 9
Created edge: 1597
Steps: 1606
Diameter: 2
Connections:
Min: 30
Mean: 31.76
Max: 35
Outbound:
Min: 9
Mean: 15.88
Max: 23

Try created edge: 727
Removed edge: 44
Created edge: 727
Steps: 771
Diameter: 2
Connections:
Min: 30
Mean: 32.80
Max: 35
Outbound:
Min: 10
Mean: 19.20
Max: 32

Big experiment
Initial nodes: 100
Updating nodes: 200

Try created edge: 1610
Removed edge: 18
Created edge: 1610
Steps: 1628
Diameter: 2
Connections:
Min: 30
Mean: 31.84
Max: 35
Outbound:
Min: 9
Mean: 15.92
Max: 24

Try created edge: 2648
Removed edge: 130
Created edge: 2648
Steps: 2778
Diameter: 2
Connections:
Min: 30
Mean: 32.77
Max: 35
Outbound:
Min: 16
Mean: 23.48
Max: 36

Big experiment
Initial nodes: 1000
Updating nodes: 1

Try created edge: 16099
Removed edge: 177
Created edge: 16099
Steps: 16276
Diameter: 3
Connections:
Min: 30
Mean: 31.84
Max: 35
Outbound:
Min: 8
Mean: 15.92
Max: 24

Try created edge: 32
Removed edge: 4
Created edge: 32
Steps: 36
Diameter: 3
Connections:
Min: 30
Mean: 31.87
Max: 35
Outbound:
Min: 8
Mean: 15.93
Max: 30