models/cpm_sgv_dfs_tree_builder.hpp

#ifndef CPM_SGV_DFS_TREE_BUILDER_HPP_
#define CPM_SGV_DFS_TREE_BUILDER_HPP_

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

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

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

public:
    DFS_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(parent vertex, binomial size) in ascending order
        deque<pair<Vertex, int> > blocks;
        // size - 1 = sum of powers of 2
        for (int tmp = size - 1, bin = 1; tmp > 0; tmp /= 2, bin *= 2)
            if (tmp % 2)
                blocks.push_back(make_pair(r, bin));
        // powers of 2
        while (!blocks.empty()) {
            Vertex s = blocks.front().first;
            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);
            if (rank == target) {
                u = s;
                v = t;
            }
            add_edge(s, t, g);
            int bin = blocks.front().second;
            blocks.pop_front();
            for (bin /= 2; bin > 0; bin /= 2)
                blocks.push_front(make_pair(t, bin));
        }
    }
};
}
}
#endif //CPM_SGV_DFS_TREE_BUILDER_HPP_