SocialNetworkGraph.h

Go to the documentation of this file.

//
// Class SocialNetworkGraph
//   Modeling social graph (Cartesian neighbors plus additional random
//   link) as underlaying master network.
//
//   @see MasterNode
//
//   Due to its nice rumor spreading properties this master network is mimicking
//   a social network graph (augmented grid) and solution states are distributed
//   in a rumor fashion.
//
//   Here, we use a simple mapping from processor ID's to 2D grid
//   (determining neigborhood) assuming the total number of masters:
//
//      n_m = n_g * n_g
//
//   This is fine, because if we have topology info the masters are numbered
//   in ascending order (done in comm splitter) and we can map them from 1D to
//   2D by index calculations.
//
// Copyright (c) 2010 - 2013, Yves Ineichen, ETH Zürich
// All rights reserved
//
// Implemented as part of the PhD thesis
// "Toward massively parallel multi-objective optimization with application to
// particle accelerators" (https://doi.org/10.3929/ethz-a-009792359)
//
// This file is part of OPAL.
//
// OPAL is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// You should have received a copy of the GNU General Public License
// along with OPAL. If not, see <https://www.gnu.org/licenses/>.
//
#ifndef __SOCIAL_NETWORK_GRAPH__
#define __SOCIAL_NETWORK_GRAPH__
 
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <random>
#include <set>
#include <vector>
 
template < class TopoDiscoveryStrategy_t >
class SocialNetworkGraph : public TopoDiscoveryStrategy_t {
 
public:
    std::set<size_t> execute(size_t numMasters, size_t dimensions,
                             size_t id, int /*island_id*/) {
 
        numMasters_ = numMasters;
        dim_        = dimensions;
        myID_       = id;
 
        chooseRandomNeighbor();
        setNetworkNeighbors();
        return realNetworkNeighborPIDs_;
    }
 
 
private:
    std::mt19937 gen_{5489u}; // default seed for reproducibility
    double alpha_;
 
    size_t numMasters_;
    size_t dim_;
    size_t myID_;
 
    size_t randomNeighbor_;
    std::set<size_t> realNetworkNeighborPIDs_;
 
    void setNetworkNeighbors() {
        size_t m = static_cast<size_t>(std::sqrt(numMasters_));
        size_t north = myID_ + m % numMasters_;
        int64_t south = myID_ - m;
        if (south < 0) {
            south += numMasters_;
        }
        size_t east = myID_ + 1;
        if ((myID_ + 1) % m == 0) {
            east = myID_ - m + 1;
        }
        size_t west = myID_ - 1;
        if (myID_ % m == 0) {
            west = myID_ + m - 1;
        }
 
        realNetworkNeighborPIDs_.insert(north);
        realNetworkNeighborPIDs_.insert(south);
        realNetworkNeighborPIDs_.insert(east);
        realNetworkNeighborPIDs_.insert(west);
    }
 
    //XXX: at the moment assumes square number of masters
    //void setNetworkNeighbors() {
        //size_t m = static_cast<size_t>(std::sqrt(numMasters_));
        //size_t north = myID_ + m;
        //if(north < numMasters_)
            //realNetworkNeighborPIDs_.insert(north);
        //size_t south = myID_ - m;
        //if(south >= 0)
            //realNetworkNeighborPIDs_.insert(south);
        //size_t east = myID_ + 1;
        //if((myID_ + 1) % m != 0)
            //realNetworkNeighborPIDs_.insert(east);
        //size_t west = myID_ - 1;
        //if(myID_ % m == 0)
            //realNetworkNeighborPIDs_.insert(west);
    //}
 
    double manhattenDistance(size_t from, size_t to) {
 
        size_t m = static_cast<size_t>(std::sqrt(numMasters_));
        int x_from = from / m;
        int y_from = from % m;
        int x_to = to / m;
        int y_to = to % m;
 
        return std::abs(x_from - x_to) + std::abs(y_from - y_to);
    }
 
    void chooseRandomNeighbor() {
 
        std::vector<double> probabilities(numMasters_, 0.0);
 
        double sum = 0.0;
        for (size_t i = 0; i < numMasters_; i++) {
            if (i == myID_) continue;
            sum += std::pow(manhattenDistance(myID_, i), -alpha_);
        }
 
        for (size_t i = 0; i < numMasters_; i++) {
            if (i == myID_) continue;
            probabilities[i] =
                std::pow(manhattenDistance(myID_, i), -alpha_) / sum;
        }
 
        std::discrete_distribution<size_t>
            dist(probabilities.begin(), probabilities.end());
 
        randomNeighbor_ = dist(gen_);
    }
 
};
 
#endif