clustered_graph_builder.h

Go to the documentation of this file.

#ifndef FPMAS_CLUSTERED_GRAPH_BUILDER_H
#define FPMAS_CLUSTERED_GRAPH_BUILDER_H
 
#include "fpmas/api/graph/graph_builder.h"
#include "fpmas/graph/static_load_balancing.h"
#include "fpmas/model/spatial/grid_load_balancing.h"
#include "random_graph_builder.h"
#include "fpmas/utils/functional.h"
 
#include <list>
 
namespace fpmas { namespace graph {
    namespace detail {
        struct Point {
            double x;
            double y;
 
            Point(double x, double y) : x(x), y(y) {}
 
            static double distance(const Point& p1, const Point& p2) {
                return std::pow(p2.y - p1.y, 2) + std::pow(p2.x - p1.x, 2);
            }
        };
 
        template<typename T>
            struct LocalizedNode {
                Point p;
                api::graph::DistributedNode<T>* node;
 
                LocalizedNode(Point p, api::graph::DistributedNode<T>* node)
                    : p(p), node(node) {}
            };
 
        template<typename T>
            struct LocalizedNodeView {
                Point p;
                fpmas::api::graph::DistributedId node_id;
                int location;
 
                LocalizedNodeView(
                        Point p, 
                        fpmas::api::graph::DistributedId node_id,
                        int location)
                    : p(p), node_id(node_id), location(location) {
                    }
            };
 
 
        class DistanceComparator {
            private:
                Point& p;
            public:
                DistanceComparator(Point& p)
                    : p(p) {}
 
                bool operator()(const Point& p1, const Point& p2) {
                    return Point::distance(p1, p) < Point::distance(p2, p);
                }
        };
    }
 
    template<typename T>
        class ClusteredGraphBuilder :
            public api::graph::GraphBuilder<T>,
            private RandomGraphBuilder {
                private:
                    /*
                     * Function object that returns a random x coordinate.
                     */
                    std::function<double()> x;
                    /*
                     * Function object that returns a random y coordinate.
                     */
                    std::function<double()> y;
 
                    static random::UniformRealDistribution<double> default_xy_dist;
 
                public:
                    template<typename Generator_t, typename EdgeDist, typename X_Dist, typename Y_Dist>
                        ClusteredGraphBuilder(
                                Generator_t& generator,
                                EdgeDist& edge_distribution,
                                X_Dist& x_distribution,
                                Y_Dist& y_distribution
                                ) :
                            RandomGraphBuilder(generator, edge_distribution),
                            // Generator, x_distribution and y_distribution are
                            // catched in a lambda to avoid class template
                            // parameters usage
                            x([&generator, &x_distribution] () {
                                    return x_distribution(generator);
                                    }),
                            y([&generator, &y_distribution] () {
                                    return y_distribution(generator);
                                    }) {
                            }
 
                    template<typename EdgeDist, typename X_Dist, typename Y_Dist>
                        ClusteredGraphBuilder(
                                EdgeDist& edge_distribution,
                                X_Dist& x_distribution,
                                Y_Dist& y_distribution
                                ) : ClusteredGraphBuilder(
                                    RandomGraphBuilder::rd, edge_distribution,
                                    x_distribution, y_distribution) {
                                }
 
                    template<typename Generator_t, typename Distribution_t>
                        ClusteredGraphBuilder(
                                Generator_t& generator,
                                Distribution_t& edge_distribution
                                ) :
                            ClusteredGraphBuilder(
                                    generator, edge_distribution,
                                    default_xy_dist, default_xy_dist) {
                            }
 
                    std::vector<api::graph::DistributedNode<T>*> build(
                            api::graph::NodeBuilder<T>& node_builder,
                            api::graph::LayerId layer,
                            api::graph::DistributedGraph<T>& graph) override;
            };
 
    template<typename T>
        random::UniformRealDistribution<double>
        ClusteredGraphBuilder<T>::default_xy_dist {0, 1000};
 
    template<typename T>
        std::vector<api::graph::DistributedNode<T>*> ClusteredGraphBuilder<T>
		::build(api::graph::NodeBuilder<T>& node_builder, api::graph::LayerId layer, api::graph::DistributedGraph<T>& graph) {
            std::vector<api::graph::DistributedNode<T>*> raw_built_nodes;
            std::vector<detail::LocalizedNode<T>> built_nodes;
            while(node_builder.nodeCount() != 0) {
                auto* node = node_builder.buildNode(graph);
                built_nodes.push_back({
                        {this->x(), this->y()},
                        node
                        });
                raw_built_nodes.push_back(node);
            }
 
            for(auto& node : built_nodes) {
                std::size_t edge_count = std::min(
                        this->num_edge(), built_nodes.size()-1
                        );
 
                detail::DistanceComparator comp(node.p);
                std::list<detail::LocalizedNode<T>> nearest_nodes;
                std::size_t i = 0;
                while(nearest_nodes.size() < edge_count) {
                    auto local_node = built_nodes[i];
                    if(local_node.node != node.node) {
                        auto it = nearest_nodes.begin();
                        while(it != nearest_nodes.end() && comp((*it).p, local_node.p))
                            it++;
                        nearest_nodes.insert(it, local_node);
                    }
                    i++;
                }
 
                for(std::size_t j = i; j < built_nodes.size(); j++) {
                    auto local_node = built_nodes[j];
                    if(local_node.node != node.node) {
                        auto it = nearest_nodes.begin();
                        while(it != nearest_nodes.end() && comp((*it).p, local_node.p))
                            it++;
                        if(it != nearest_nodes.end()) {
                            nearest_nodes.insert(it, local_node);
                            nearest_nodes.pop_back();
                        }
                    }
                }
 
                for(auto nearest_node : nearest_nodes)
                    graph.link(node.node, nearest_node.node, layer);
            }
            return raw_built_nodes;
        }
 
    template<typename T>
        class DistributedClusteredGraphBuilder :
            public api::graph::DistributedGraphBuilder<T>,
            private RandomGraphBuilder {
                private:
                    /*
                     * Function object that returns a random x coordinate.
                     */
                    std::function<double()> x;
                    /*
                     * Function object that returns a random y coordinate.
                     */
                    std::function<double()> y;
 
                    double x0;
                    double y0;
                    double X;
                    double Y;
 
                    static random::UniformRealDistribution<double> default_xy_dist;
 
                public:
                    template<typename EdgeDist, typename X_Dist, typename Y_Dist>
                        DistributedClusteredGraphBuilder(
                                random::DistributedGenerator<>& generator,
                                EdgeDist& edge_distribution,
                                X_Dist& x_distribution,
                                Y_Dist& y_distribution
                                ) :
                            RandomGraphBuilder(generator, edge_distribution),
                            x([&generator, &x_distribution] () {return x_distribution(generator);}),
                            y([&generator, &y_distribution] () {return y_distribution(generator);}),
                            x0(x_distribution.min()), y0(y_distribution.min()),
                            X(x_distribution.max()-x0), Y(y_distribution.max()-y0) {
                            }
 
                    template<typename EdgeDist, typename X_Dist, typename Y_Dist>
                        DistributedClusteredGraphBuilder(
                                EdgeDist& edge_distribution,
                                X_Dist& x_distribution,
                                Y_Dist& y_distribution
                                ) :
                            DistributedClusteredGraphBuilder(
                                    RandomGraphBuilder::distributed_rd, edge_distribution,
                                    x_distribution, y_distribution) {
                            }
 
 
                    template<typename EdgeDist>
                        DistributedClusteredGraphBuilder(
                                random::DistributedGenerator<>& generator,
                                EdgeDist& edge_distribution
                                ) :
                            DistributedClusteredGraphBuilder(
                                    generator, edge_distribution,
                                    default_xy_dist, default_xy_dist){
                            }
 
                    template<typename EdgeDist>
                        DistributedClusteredGraphBuilder(
                                EdgeDist& edge_distribution
                                ) :
                            DistributedClusteredGraphBuilder(
                                    RandomGraphBuilder::distributed_rd, edge_distribution,
                                    default_xy_dist, default_xy_dist){
                            }
 
                    std::vector<api::graph::DistributedNode<T>*> build(
                            api::graph::DistributedNodeBuilder<T>& node_builder,
                            api::graph::LayerId layer,
                            api::graph::DistributedGraph<T>& graph) override;
            };
 
    template<typename T>
        random::UniformRealDistribution<double>
        DistributedClusteredGraphBuilder<T>::default_xy_dist {0, 1000};
 
    template<typename T>
        std::vector<api::graph::DistributedNode<T>*> DistributedClusteredGraphBuilder<T>
		::build(
                api::graph::DistributedNodeBuilder<T>& node_builder,
                api::graph::LayerId layer,
                api::graph::DistributedGraph<T>& graph) {
            fpmas::model::FastProcessMapping process_mapping(X, Y, graph.getMpiCommunicator());
 
            fpmas::graph::PartitionMap partition;
            std::vector<detail::LocalizedNode<T>> local_built_nodes;
            while(node_builder.localNodeCount() != 0) {
                auto* node = node_builder.buildNode(graph);
                double x = this->x();
                double y = this->y();
                local_built_nodes.push_back({
                        {x, y},
                        node
                        });
                // Builds and gathers coordinates on each process according to the
                // FastProcessMapping to reduce the count of DISTANT nodes
                partition[node->getId()] = process_mapping.process({
                        (int) x - (int) x0, (int) y - (int) y0
                        });
            }
 
            std::vector<detail::LocalizedNodeView<T>> all_built_nodes;
            for(auto node : local_built_nodes)
                all_built_nodes.push_back({
                        node.p, node.node->getId(), partition[node.node->getId()]
                        });
 
            fpmas::communication::TypedMpi<std::vector<detail::LocalizedNodeView<T>>> mpi(
                    graph.getMpiCommunicator()
                    );
 
            all_built_nodes = fpmas::communication::all_reduce(
                    mpi, all_built_nodes, fpmas::utils::Concat()
                    );
 
            graph.distribute(partition);
            local_built_nodes.clear();
            std::vector<api::graph::DistributedNode<T>*> raw_built_nodes;
            {
                const auto& local_nodes = graph.getLocationManager().getLocalNodes();
                for(auto& item : all_built_nodes) {
                    auto it = local_nodes.find(item.node_id);
                    if(it != local_nodes.end()) {
                        local_built_nodes.push_back({item.p, it->second});
                        raw_built_nodes.push_back(it->second);
                    }
                }
            }
 
            const auto& graph_nodes = graph.getNodes();
            for(auto& node : local_built_nodes) {
                std::size_t edge_count = std::min(
                        this->num_edge(), all_built_nodes.size()-1
                        );
                detail::DistanceComparator comp(node.p);
                std::list<detail::LocalizedNodeView<T>> nearest_nodes;
                std::size_t i = 0;
                while(nearest_nodes.size() < edge_count) {
                    auto local_node = all_built_nodes[i];
                    if(local_node.node_id != node.node->getId()) {
                        auto it = nearest_nodes.begin();
                        while(it != nearest_nodes.end() && comp((*it).p, local_node.p))
                            it++;
                        nearest_nodes.insert(it, local_node);
                    }
                    i++;
                }
 
                for(std::size_t j = i; j < all_built_nodes.size(); j++) {
                    auto local_node = all_built_nodes[j];
                    if(local_node.node_id != node.node->getId()) {
                        auto it = nearest_nodes.begin();
                        while(it != nearest_nodes.end() && comp((*it).p, local_node.p))
                            it++;
                        if(it != nearest_nodes.end()) {
                            nearest_nodes.insert(it, local_node);
                            nearest_nodes.pop_back();
                        }
                    }
                }
 
                for(auto nearest_node : nearest_nodes) {
                    api::graph::DistributedNode<T>* target_node;
                    auto it = graph_nodes.find(nearest_node.node_id);
                    if(it != graph_nodes.end()) {
                        target_node = it->second;
                    } else {
                        target_node = node_builder.buildDistantNode(
                                nearest_node.node_id, nearest_node.location, graph
                                );
                    }
                    graph.link(node.node, target_node, layer);
                }
            }
 
            // Commits new links
            graph.synchronizationMode().getSyncLinker().synchronize();
 
            return raw_built_nodes;
        }
}}
 
namespace nlohmann {
    template<typename T>
        struct adl_serializer<fpmas::graph::detail::LocalizedNodeView<T>> {
 
            template<typename JsonType>
                static void to_json(
                        JsonType& j,
                        const fpmas::graph::detail::LocalizedNodeView<T>& node
                        ) {
                    j = {{node.p.x, node.p.y}, node.node_id, node.location};
                }
 
            template<typename JsonType>
                static fpmas::graph::detail::LocalizedNodeView<T> from_json(const JsonType& j) {
                    return {
                        {
                            j.at(0).at(0).template get<double>(),
                            j.at(0).at(1).template get<double>()
                        },
                        j[1].template get<fpmas::api::graph::DistributedId>(),
                        j.at(2).template get<int>()
                    };
                }
        };
}
 
namespace fpmas { namespace io { namespace datapack {
    template<typename T>
        struct Serializer<graph::detail::LocalizedNodeView<T>> {
 
            static std::size_t size(
                    const ObjectPack& p, const graph::detail::LocalizedNodeView<T>&) {
                return 2*p.size<double>() + p.size<DistributedId>() + p.size<int>();
            }
 
            static void to_datapack(
                    ObjectPack& pack,
                    const graph::detail::LocalizedNodeView<T>& node) {
                pack.put(node.p.x);
                pack.put(node.p.y);
                pack.put(node.node_id);
                pack.put(node.location);
            }
 
            static graph::detail::LocalizedNodeView<T> from_datapack(const ObjectPack& pack) {
                // Call order guaranteed, DO NOT CALL gets FROM THE CONSTRUCTOR
                double x = pack.get<double>();
                double y = pack.get<double>();
                DistributedId id = pack.get<DistributedId>();
                int location = pack.get<int>();
                return {{x, y}, id, location};
            }
 
        };
}}}
#endif