models/cpm_sgv_ucs_tree_builder.hpp

#ifndef CPM_SGV_UCS_TREE_BULDER_HPP_
#define CPM_SGV_UCS_TREE_BULDER_HPP_

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

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

class UCS_binomial_builder {
private:
    CPM_predictor* predictor;
    CPM_next_node_strategy next_node;

public:
    UCS_binomial_builder(CPM_predictor* _predictor, CPM_next_node_strategy _next_node): predictor(_predictor), next_node(_next_node) {}

    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(free rank, source->rank prediction) for searching min/max prediction
        deque<pair<int, double> > ranks;
        for (int i = 0; i < size; i++)
            if (i != root)
                ranks.push_back(make_pair(i, 0));
        // blocks(binomial size, parent vertices)
        multimap<int, Vertex> blocks;
        // size - 1 = sum of powers of 2
        int tmp, bin;
        for (tmp = size - 1, bin = 1; tmp > 0; tmp /= 2, bin *= 2)
            if (tmp % 2)
                blocks.insert(map<int, Vertex>::value_type(bin, r));
        bin /= 2;
        // construction, starting with the highest order
        while (!blocks.empty()) {
            //  subtrees of the same order
            pair<map<int, Vertex>::iterator, map<int, Vertex>::iterator> range =
                blocks.equal_range(bin);
            for (map<int, Vertex>::iterator b = range.first; b != range.second; b++) {
                // add source->target
                Vertex s = b->second;
                int source = get(vertex_index, g, s);
                for (deque<pair<int, double> >::iterator i = ranks.begin(); i != ranks.end(); i++){
                    int target = i->first;
                    i->second = predictor->predict_p2p(predictor, source, target, counts[target]);
                }
                deque<pair<int, double> >::iterator i = (next_node == MAX) ?
                        max_element(ranks.begin(), ranks.end(), second_less()):
                        min_element(ranks.begin(), ranks.end(), second_less());
                int target = i->first;

                if ( (rank == root) && (mpib_coll_verbose ==1) ){
                    printf("DEBUG: source(fixed)= %d, target(selected)=%d, prediction=%lf\n", source, target, i->second);
                    for (deque<pair<int, double> >::iterator i = ranks.begin(); i != ranks.end(); i++) {
                        printf("DEBUG: alternative link prediction: (%d-%d) = %lf\n", source, i->first, i->second);
                    }
                    printf("DEBUG: ===\n");
                }

                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;
                }
                // add lesser blocks
                for (int bin = b->first / 2; bin > 0; bin /= 2)
                    blocks.insert(map<int, Vertex>::value_type(bin, t));
            }
            blocks.erase(range.first, range.second);
            bin /= 2;
        }
    }
};
}
}
#endif //CPM_SGV_UCS_TREE_BULDER_HPP_