models/cpm_sgv_traff_tree_builder.hpp

#ifndef CPM_SGV_TRAFF_TREE_BUILDER_HPP_
#define CPM_SGV_TRAFF_TREE_BUILDER_HPP_

#include "MPIBlib/collectives/comm_tree.hpp"
#include "cpm_model.h"

namespace CPM {
namespace SGv {
using namespace MPIB::comm_tree;

class Traff_builder {
private:
    CPM_predictor* predictor;

public:
    Traff_builder(CPM_predictor* _predictor): predictor(_predictor) {}

    void build(int size, int root, int rank, int* counts,
        Graph& g, Vertex& r, Vertex& u, Vertex& v)
    {
        // root
        r = add_vertex(g);
        put(vertex_index, g, r, root);
        if (rank == root)
            v = r;
        // ranks(rank, root->rank prediction)
        deque<pair<int, double> > ranks;
        for (int i = 0; i < size; i++)
            if (i != root)
                ranks.push_back(make_pair(i, predictor->predict_p2p(predictor, root, i, counts[i])));
        sort(ranks.begin(), ranks.end(), second_greater());
        // sets(source vertex, ranks)
        deque<pair<Vertex, deque<int> > > sets;
        double sum = 0;
        double weight = 0;
        for (deque<pair<int, double> >::iterator i = ranks.begin(); i != ranks.end(); i++) {
            if (weight == 0) {
                sets.push_back(make_pair(r, deque<int>()));

                if ((mpib_coll_verbose == 1) && (rank == root)) {
                    printf("DEBUG: ===\n");
                }

            }
            sets.back().second.push_back(i->first);

            if ((mpib_coll_verbose == 1) && (rank == root)) {
                printf("DEBUG: add element %d , potential link (%d-%d), prediction: %lf\n", i->first, root, i->first, i->second);
            }

            weight += i->second;
            if (weight >= sum) {
                sum += weight;
                weight = 0;
            }
        }
        if ((mpib_coll_verbose == 1) && (rank == root)) {
            printf("DEBUG: ===\n");
        }
        // subtrees
        while (!sets.empty()) {
            // parent is the fastest
            Vertex s = sets.front().first;
            int source = get(vertex_index, g, s);
            deque<int>& targets = sets.front().second;
            int count = 0;
            for (deque<int>::iterator i = targets.begin(); i != targets.end(); i++)
                count += counts[*i];
            // ranks(rank, source->rank prediction)
            deque<pair<int, double> > ranks;
            for (deque<int>::iterator i = targets.begin(); i != targets.end(); i++) {
                int target = *i;
                ranks.push_back(make_pair(target, predictor->predict_p2p(predictor, source, target, count)));

                if ((mpib_coll_verbose == 1) && (rank == root)) {
                    printf("DEBUG: add element %d , potential link (%d-%d), prediction: %lf\n", target, source, target, ranks.back().second);
                }

            }
            deque<pair<int, double> >::iterator i = min_element(ranks.begin(), ranks.end(), second_less());
            int target = i->first;
            if ((mpib_coll_verbose == 1) && (rank == root)) {
                printf("DEBUG: create link (%d-%d) with prediction %lf\n", source, target, i->second);
            }
            ranks.erase(i);
            Vertex t = add_vertex(g);
            put(vertex_index, g, t, target);
            add_edge(s, t, g);
            if (rank == target) {
                u = s;
                v = t;
            }
            // children
            for (deque<pair<int, double> >::iterator i = ranks.begin(); i != ranks.end(); i++) {
                int child = i->first;
                i->second = predictor->predict_p2p(predictor, target, child, counts[child]);
            }
            sort(ranks.begin(), ranks.end(), second_greater());
            double sum = 0;
            double weight = 0;
            for (deque<pair<int, double> >::iterator i = ranks.begin(); i != ranks.end(); i++) {
                if (weight == 0) {
                    if ((mpib_coll_verbose == 1) && (rank == root)) {
                        printf("DEBUG: ===\n");
                    }
                    sets.push_back(make_pair(t, deque<int>()));
                }
                sets.back().second.push_back(i->first);
                if ((mpib_coll_verbose == 1) && (rank == root)) {
                    printf("DEBUG: add element %d , potential link (%d-%d), prediction: %lf\n", i->first, target, i->first, i->second);
                }
                weight += i->second;
                if (weight >= sum) {
                    sum += weight;
                    weight = 0;
                }
            }
            sets.pop_front();

            if ((mpib_coll_verbose == 1) && (rank == root)) {
                printf("DEBUG: ===\n");
            }
        }
    }
};
}
}
#endif //CPM_SGV_TRAFF_TREE_BUILDER_HPP_