uniform_graph_builder.h

Go to the documentation of this file.

#ifndef FPMAS_UNIFORM_GRAPH_BUILDER_H
#define FPMAS_UNIFORM_GRAPH_BUILDER_H
 
#include "fpmas/api/graph/graph_builder.h"
#include "random_graph_builder.h"
#include "fpmas/utils/functional.h"
 
namespace fpmas { namespace graph {
    // TODO 2.0: remove or rename this, use Distributed instead
    template<typename T>
        class UniformGraphBuilder :
            public api::graph::GraphBuilder<T>,
            private RandomGraphBuilder {
                private:
                    /*
                     * Function object that return a random integer between 0 and
                     * the specified argument (included).
                     */
                    std::function<std::size_t(std::size_t)> index;
 
                public:
                    // TODO 2.0: Remove this constructor
                    template<typename Generator_t, typename EdgeDist>
                        UniformGraphBuilder(
                                Generator_t& generator,
                                EdgeDist& distribution) :
                            RandomGraphBuilder(generator, distribution),
                            // A lambda function is used to "catch" generator, without
                            // requiring class level template parameters.
                            index([&generator] (std::size_t max) {
                                    random::UniformIntDistribution<std::size_t> index(
                                            0, max
                                            );
                                    return index(generator);
                                    }) {
                            }
 
                    template<typename EdgeDist>
                        UniformGraphBuilder(EdgeDist& distribution)
                        : UniformGraphBuilder(RandomGraphBuilder::rd, distribution) {
                        }
 
                    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>
        std::vector<api::graph::DistributedNode<T>*> UniformGraphBuilder<T>
			::build(
                    api::graph::NodeBuilder<T>& node_builder,
                    api::graph::LayerId layer,
                    api::graph::DistributedGraph<T>& graph) {
                std::vector<api::graph::DistributedNode<T>*> built_nodes;
                while(node_builder.nodeCount() != 0)
                    built_nodes.push_back(node_builder.buildNode(graph));
 
                std::vector<api::graph::DistributedNode<T>*> node_buffer = built_nodes;
                for(auto node : built_nodes) {
                    std::size_t edge_count = std::min(
                            // Random edge count
                            this->num_edge(), built_nodes.size()-1
                            );
 
                    auto position = std::find(
                                node_buffer.begin(), node_buffer.end(),
                                node
                            );
                    std::swap(*position, node_buffer.back());
 
                    for(std::size_t i = 0; i < edge_count; i++) {
                        auto& target_node = node_buffer[
                            this->index(node_buffer.size()-2-i) // random index
                        ];
                        graph.link(node, target_node, layer);
 
                        std::swap(target_node, node_buffer[node_buffer.size()-2-i]);
                    }
                }
                return built_nodes;
        }
 
    template<typename T>
        class DistributedUniformGraphBuilder :
            public api::graph::DistributedGraphBuilder<T>,
            private RandomGraphBuilder {
                private:
                    /*
                     * Function object that return a random integer between 0 and
                     * the specified argument (included).
                     */
                    std::function<std::size_t(std::size_t)> index;
                public:
                    
                    template<typename EdgeDist>
                        DistributedUniformGraphBuilder(
                                random::DistributedGenerator<>& generator,
                                EdgeDist& distribution) :
                            RandomGraphBuilder(generator, distribution),
                            // A lambda function is used to "catch" generator, without
                            // requiring class level template parameters.
                            index([&generator] (std::size_t max) {
                                    random::UniformIntDistribution<std::size_t> index(
                                            0, max
                                            );
                                    return index(generator);
                                    }) {
                        }
 
                    template<typename EdgeDist>
                        DistributedUniformGraphBuilder(
                                EdgeDist& distribution) :
                            DistributedUniformGraphBuilder(RandomGraphBuilder::distributed_rd, distribution) {
                            }
 
                    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>
        std::vector<api::graph::DistributedNode<T>*> DistributedUniformGraphBuilder<T>
			::build(
                    api::graph::DistributedNodeBuilder<T>& node_builder,
                    api::graph::LayerId layer,
                    api::graph::DistributedGraph<T>& graph) {
                std::vector<api::graph::DistributedNode<T>*> built_nodes;
                while(node_builder.localNodeCount() != 0)
                    built_nodes.push_back(node_builder.buildNode(graph));
 
                typedef std::pair<api::graph::DistributedId, int> LocId;
                communication::TypedMpi<std::vector<LocId>>
                    id_mpi(graph.getMpiCommunicator());
                std::vector<LocId> node_ids;
                for(auto node : built_nodes)
                    node_ids.push_back({node->getId(), node->location()});
 
                node_ids = fpmas::communication::all_reduce(
                        id_mpi, node_ids, fpmas::utils::Concat()
                        );
 
 
                const auto& graph_nodes = graph.getNodes();
                for(auto node : built_nodes) {
                    std::size_t edge_count = std::min(
                            this->num_edge(), node_ids.size()-1
                            );
 
                    auto position = std::find_if(
                                node_ids.begin(), node_ids.end(),
                                [node] (const LocId& id) {return id.first == node->getId();}
                            );
                    std::swap(*position, node_ids.back());
 
                    for(std::size_t i = 0; i < edge_count; i++) {
                        auto& id = node_ids[this->index(node_ids.size()-2-i)];
 
                        fpmas::api::graph::DistributedNode<T>* target_node;
                        auto it = graph_nodes.find(id.first); 
                        if(it != graph_nodes.end()) {
                            target_node = it->second;
                        } else {
                            target_node = node_builder.buildDistantNode(id.first, id.second, graph);
                        }
                        graph.link(node, target_node, layer);
 
                        std::swap(id, node_ids[node_ids.size()-2-i]);
                    }
                }
 
                // Commits new links
                graph.synchronizationMode().getSyncLinker().synchronize();
 
                return built_nodes;
        }
}}
#endif