binary_tree.hpp

// Copyright 2021 Arnaud Becheler    <abechele@umich.edu>
 
 
#pragma once
 
#include <type_traits>
 
#include <boost/range/iterator_range.hpp>
#include <range/v3/all.hpp>
#include <ranges>
 
#include <boost/graph/graphviz.hpp>
 
#include "detail/adl_resolution.hpp"
#include "detail/cardinal_k_ary_tree.hpp"
#include "detail/tree_traits.hpp"
#include "detail/utils.hpp"
 
#include <algorithm>
#include <iterator>
#include <tuple>
#include <utility>
 
namespace quetzal::coalescence
{
 
using no_property = boost::no_property;
 
namespace detail
{
 
// Getting std::map::emplace to work with aggregate initialization for POD EdgeProperties
template <typename T> struct tag
{
    using type = T;
};
 
template <typename F> struct initializer
{
    F f;
    template <typename T> operator T() &&
    {
        return std::forward<F>(f)(tag<T>{});
    }
};
 
template <typename F> initializer(F &&) -> initializer<F>;
 
template <typename... Args> auto initpack(Args &&...args)
{
    return initializer{[&](auto t) {
        using Ret = typename decltype(t)::type;
        return Ret{std::forward<Args>(args)...};
    }};
}
 
template <typename VertexDescriptor, typename VertexProperty> struct VertexManager
{
    using vertex_descriptor = VertexDescriptor;
    using vertex_hashmap_type = std::map<vertex_descriptor, VertexProperty>;
 
    vertex_hashmap_type _property_map;
 
    template <typename... Args> void add_vertex_to_manager(vertex_descriptor v, Args &&...args)
    {
        _property_map[v] = {std::forward<Args>(args)...};
    }
 
    const VertexProperty &operator[](vertex_descriptor v) const
    {
        return _property_map.at(v);
    }
 
    VertexProperty &operator[](vertex_descriptor v)
    {
        return _property_map[v];
    }
};
 
template <typename EdgeDescriptor, typename EdgeProperty> struct EdgeManager
{
    using edge_descriptor = EdgeDescriptor;
    using vertex_descriptor = typename EdgeDescriptor::first_type;
    using edge_hashmap_type = std::map<edge_descriptor, EdgeProperty>;
 
    edge_hashmap_type _property_map;
 
    void add_edges(EdgeDescriptor u, const EdgeProperty &left, EdgeDescriptor v, const EdgeProperty &right)
    {
        _property_map.insert({u, left});
        _property_map.insert({v, right});
    }
 
    template <typename... Args>
    void add_edges(EdgeDescriptor u, std::tuple<Args...> left, EdgeDescriptor v, std::tuple<Args...> right)
    {
        _property_map.emplace(
            std::piecewise_construct, std::forward_as_tuple(u),
            std::forward_as_tuple(std::apply([](auto &&...args) { return initpack(args...); }, left)));
        _property_map.emplace(
            std::piecewise_construct, std::forward_as_tuple(v),
            std::forward_as_tuple(std::apply([](auto &&...args) { return initpack(args...); }, right)));
    }
 
    template <typename VertexDescriptor>
    const EdgeProperty &operator[](const std::pair<VertexDescriptor, VertexDescriptor> &edge) const
    {
        return _property_map.at(edge);
    }
 
    template <typename VertexDescriptor>
    EdgeProperty &operator[](const std::pair<VertexDescriptor, VertexDescriptor> &edge)
    {
        return _property_map.at(edge);
    }
};
 
template <class VertexProperty, class EdgeProperty> class binary_tree_common
{
  protected:
    using base = boost::binary_tree<true, std::size_t>;
    base _graph;
 
  public:
    binary_tree_common() : _graph()
    {
    }
 
    binary_tree_common(size_t n) : _graph(n)
    {
    }
 
    using vertex_descriptor = typename base::vertex_descriptor;
 
    using edge_descriptor = typename base::edge_descriptor;
 
    using degree_size_type = typename base::degree_size_type;
 
    using traversal_category = typename base::traversal_category;
 
    using directed_category = typename base::directed_category;
 
    using in_edge_iterator = typename base::in_edge_iterator;
 
    using edge_parallel_category = typename base::edge_parallel_category;
 
 
    bool is_isomorphic(binary_tree_common const &other) const
    {
        using detail::adl_resolution::isomorphism;
        return isomorphism(_graph, other._graph);
    }
 
    vertex_descriptor find_root_from(vertex_descriptor u) const
    {
        using detail::adl_resolution::root;
        return root(u, _graph);
    }
 
    degree_size_type degree(vertex_descriptor u) const
    {
        using detail::adl_resolution::degree;
        return degree(u, _graph);
    }
 
    degree_size_type in_degree(vertex_descriptor u) const
    {
        return has_predecessor(u);
    }
 
    degree_size_type out_degree(vertex_descriptor v) const
    {
        using detail::adl_resolution::out_degree;
        return out_degree(v, _graph);
    }
 
    bool has_predecessor(vertex_descriptor u) const
    {
        using detail::adl_resolution::has_predecessor;
        return has_predecessor(u, _graph);
    }
 
    vertex_descriptor predecessor(vertex_descriptor u) const
    {
        using detail::adl_resolution::predecessor;
        return predecessor(u, _graph);
    }
 
    bool has_successors(vertex_descriptor u) const
    {
        return out_degree(u) == 2;
    }
 
    auto successors(vertex_descriptor u) const
    {
        return boost::make_iterator_range(out_edges(u, _graph)) |
               boost::adaptors::transformed([this](auto it) { return target(it, _graph); });
    }
    
    bool is_left_successor(vertex_descriptor u) const
    {
        using detail::adl_resolution::is_left_successor;
        return is_left_successor(u, _graph);
    }
 
    bool is_right_successor(vertex_descriptor u) const
    {
        using detail::adl_resolution::is_right_successor;
        return is_right_successor(u, _graph);
    }
 
 
 
    std::pair<in_edge_iterator, in_edge_iterator> in_edges(vertex_descriptor u) const
    {
        using detail::adl_resolution::in_edges;
        return in_edges(u, _graph);
    }
 
 
 
    template <typename DFSTreeVisitor> void depth_first_search(vertex_descriptor s, DFSTreeVisitor &vis)
    {
        // delete the member function void depth_first_search(vertex_descriptor s, DFSTreeVisitor &vis) const
        // using detail::adl_resolution::depth_first_search;
        // ADL is now enabled
        return boost::depth_first_search(_graph, s, vis);
    }
 
    template <typename DFSTreeVisitor> void depth_first_search(vertex_descriptor s, DFSTreeVisitor &vis) const
    {
        // delete the member function void depth_first_search(vertex_descriptor s, DFSTreeVisitor &vis)
        // using detail::adl_resolution::depth_first_search;
        // ADL is now enabled
        return boost::depth_first_search(_graph, s, vis);
    }
 
 
 
    void to_graphviz(std::ostream &out) const
    {
        using namespace boost;
        return boost::write_graphviz(out, *this, boost::make_label_writer(boost::get(vertex_bundle, *this)),
                                     boost::make_label_writer(boost::get(edge_bundle, *this)));
    }
 
 
    static constexpr inline vertex_descriptor null_vertex()
    {
        return base::null_vertex();
    }
};
 
} // end namespace detail
 
template <class VertexProperty, class EdgeProperty> class binary_tree
{
};
 
template <> class binary_tree<no_property, no_property> : public detail::binary_tree_common<no_property, no_property>
{
    using base = detail::binary_tree_common<no_property, no_property>;
 
  public:
 
    explicit binary_tree() : base()
    {
    }
 
    explicit binary_tree(size_t n) : base(n)
    {
    }
 
 
    vertex_descriptor add_vertex()
    {
        // ADL intended to happen on that name, somewhere in that scope.
        using boost::add_vertex;
        return add_vertex(_graph);
    }
 
    std::pair<edge_descriptor, edge_descriptor> add_edges(vertex_descriptor parent, vertex_descriptor left,
                                                          vertex_descriptor right)
    {
        assert(parent != left);
        assert(parent != right);
        assert(left != right);
        return std::make_pair(add_left_edge(parent, left, _graph), add_right_edge(parent, right, _graph));
    }
 
 
}; // end specialization binary_tree<boost::no::property, boost::no_property>
 
template <class VertexProperty>
    requires(!std::is_same_v<VertexProperty, no_property>)
class binary_tree<VertexProperty, no_property> : public detail::binary_tree_common<VertexProperty, no_property>
{
  private:
    using base = detail::binary_tree_common<VertexProperty, no_property>;
    detail::VertexManager<typename base::vertex_descriptor, VertexProperty> _vertex_manager;
 
  public:
    using edge_descriptor = typename base::edge_descriptor;
 
    using vertex_descriptor = typename base::vertex_descriptor;
 
 
    explicit binary_tree() : base()
    {
    }
 
    explicit binary_tree(size_t n) : base(n)
    {
    }
 
 
 
    vertex_descriptor add_vertex(const VertexProperty &p)
    {
        // ADL intended to happen on that name, somewhere in that scope.
        using boost::add_vertex;
        vertex_descriptor v = add_vertex(this->_graph);
        _vertex_manager.add_vertex_to_manager(v, p);
        return v;
    }
 
    std::pair<edge_descriptor, edge_descriptor> add_edges(vertex_descriptor parent, vertex_descriptor left,
                                                          vertex_descriptor right)
    {
        assert(parent != left);
        assert(parent != right);
        assert(left != right);
        return {add_left_edge(parent, left, this->_graph), add_right_edge(parent, right, this->_graph)};
    }
 
 
 
    const VertexProperty &operator[](vertex_descriptor v) const
    {
        return _vertex_manager[v];
    }
 
    VertexProperty &operator[](vertex_descriptor v)
    {
        return _vertex_manager[v];
    }
 
 
}; // end specialization binary_tree<Vertex, boost::no_property>
 
template <class EdgeProperty>
    requires(!std::is_same_v<EdgeProperty, no_property>)
class binary_tree<no_property, EdgeProperty> : public detail::binary_tree_common<no_property, EdgeProperty>
{
  private:
    using base = detail::binary_tree_common<no_property, EdgeProperty>;
    detail::EdgeManager<typename base::edge_descriptor, EdgeProperty> _edge_manager;
 
  public:
    using edge_descriptor = typename base::edge_descriptor;
 
    using vertex_descriptor = typename base::vertex_descriptor;
 
 
    explicit binary_tree() : base()
    {
    }
 
    explicit binary_tree(size_t n) : base(n)
    {
    }
 
 
 
    vertex_descriptor add_vertex()
    {
        // ADL intended to happen on that name, somewhere in that scope.
        using boost::add_vertex;
        return add_vertex(this->_graph);
    }
 
    std::pair<edge_descriptor, edge_descriptor> add_edges(vertex_descriptor parent,
                                                          const std::pair<vertex_descriptor, EdgeProperty> &left,
                                                          const std::pair<vertex_descriptor, EdgeProperty> &right)
    {
        assert(parent != left.first);
        assert(parent != right.first);
        assert(left.first != right.first);
 
        auto left_edge = add_left_edge(parent, left.first, this->_graph);
        auto right_edge = add_right_edge(parent, right.first, this->_graph);
 
        _edge_manager.add_edges(left_edge, left.second, right_edge, right.second);
        return {left_edge, right_edge};
    }
 
 
 
    const EdgeProperty &operator[](const edge_descriptor &edge) const
    {
        return _edge_manager[edge];
    }
 
    EdgeProperty &operator[](const edge_descriptor &edge)
    {
        return _edge_manager[edge];
    }
 
 
}; // end specialization binary_tree<boost::no_property, Edge>
 
template <class VertexProperty, class EdgeProperty>
    requires(!std::is_same_v<VertexProperty, no_property> && !std::is_same_v<EdgeProperty, no_property>)
class binary_tree<VertexProperty, EdgeProperty> : public detail::binary_tree_common<VertexProperty, EdgeProperty>
{
  private:
    using base = detail::binary_tree_common<VertexProperty, EdgeProperty>;
    detail::EdgeManager<typename base::edge_descriptor, EdgeProperty> _edge_manager;
    detail::VertexManager<typename base::vertex_descriptor, VertexProperty> _vertex_manager;
 
  public:
    using edge_descriptor = typename base::edge_descriptor;
 
    using vertex_descriptor = typename base::vertex_descriptor;
 
 
    explicit binary_tree() : base()
    {
    }
 
    explicit binary_tree(size_t n) : base(n)
    {
    }
 
 
 
    vertex_descriptor add_vertex(const VertexProperty &p)
    {
        // ADL intended to happen on that name, somewhere in that scope.
        using boost::add_vertex;
        vertex_descriptor v = add_vertex(this->_graph);
        _vertex_manager.add_vertex_to_manager(v, p);
        return v;
    }
 
    std::pair<edge_descriptor, edge_descriptor> add_edges(vertex_descriptor parent,
                                                          const std::pair<vertex_descriptor, EdgeProperty> &left,
                                                          const std::pair<vertex_descriptor, EdgeProperty> &right)
    {
        assert(parent != left.first);
        assert(parent != right.first);
        assert(left.first != right.first);
 
        auto left_edge = add_left_edge(parent, left.first, this->_graph);
        auto right_edge = add_right_edge(parent, right.first, this->_graph);
 
        _edge_manager.add_edges(left_edge, left.second, right_edge, right.second);
        return {left_edge, right_edge};
    }
 
 
 
    const VertexProperty &operator[](vertex_descriptor v) const
    {
        return _vertex_manager[v];
    }
 
    VertexProperty &operator[](vertex_descriptor v)
    {
        return _vertex_manager[v];
    }
 
    const EdgeProperty &operator[](const edge_descriptor &edge) const
    {
        return _edge_manager[edge];
    }
 
    EdgeProperty &operator[](const edge_descriptor &edge)
    {
        return _edge_manager[edge];
    }
 
};
 
namespace detail
{
template <typename Vertex, typename Edge, typename Generator>
auto update_tree(binary_tree<Vertex, Edge> &tree,
                 std::vector<typename binary_tree<Vertex, Edge>::vertex_descriptor> leaves, Generator &rng)
{
    using tree_type = binary_tree<Vertex, Edge>;
    using vertex_descriptor = typename tree_type::vertex_descriptor;
 
    if (leaves.size() == 1)
    {
        return leaves.front();
    }
    else
    {
        std::uniform_int_distribution<> distrib(1, leaves.size() - 1);
        int split = distrib(rng);
 
        std::vector<vertex_descriptor> left(leaves.begin(), leaves.begin() + split);
        std::vector<vertex_descriptor> right(leaves.begin() + split, leaves.end());
 
        vertex_descriptor parent;
 
        if constexpr (std::is_same_v<Vertex, boost::no_property>)
            parent = tree.add_vertex();
        else
            parent = tree.add_vertex(Vertex());
 
        if constexpr (std::is_same_v<Edge, boost::no_property>)
            tree.add_edges(parent, update_tree(tree, left, rng), update_tree(tree, right, rng));
        else
            tree.add_edges(parent, {update_tree(tree, left, rng), Edge()}, {update_tree(tree, right, rng), Edge()});
        return parent;
    }
}
} // namespace detail
 
template <typename Vertex = boost::no_property, typename Edge = boost::no_property, typename Generator>
std::pair<quetzal::coalescence::binary_tree<Vertex, Edge>,
          typename quetzal::coalescence::binary_tree<Vertex, Edge>::vertex_descriptor>
get_random_binary_tree(int n_leaves, Generator &rng)
{
    using tree_type = quetzal::coalescence::binary_tree<Vertex, Edge>;
    using vertex_descriptor = typename tree_type::vertex_descriptor;
 
    tree_type tree;
 
    std::vector<vertex_descriptor> leaves(n_leaves);
 
    std::transform(leaves.cbegin(), leaves.cend(), leaves.begin(), [&tree](auto) {
        if constexpr (std::is_same_v<Vertex, boost::no_property>)
            return tree.add_vertex();
        else
            return tree.add_vertex(Vertex());
    });
 
    vertex_descriptor root = detail::update_tree(tree, leaves, rng);
    return std::make_pair(std::move(tree), root);
}
} // namespace quetzal::coalescence