network.hpp

// Copyright 2021 Arnaud Becheler    <abechele@umich.edu>
 
 
#pragma once
 
#include "detail/tree_traits.hpp"
#include "detail/visit.hpp"
 
#include <boost/range/adaptor/transformed.hpp>
#include <boost/range/iterator_range.hpp>
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/topological_sort.hpp>
 
#include <boost/graph/connected_components.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/random_spanning_tree.hpp>
 
#include "detail/adl_resolution.hpp"
#include "detail/utils.hpp"
 
#include <algorithm>
#include <iostream>
 
#include <range/v3/all.hpp>
 
namespace quetzal::coalescence
{
using no_property = boost::no_property;
 
namespace detail
{
 
// Base class and common implementation
template <class VertexProperty, class EdgeProperty, class CRTP> class network_common
{
  protected:
    using base = tree_traits::model<tree_traits::out_edge_list_type, tree_traits::vertex_list_type,
                                    tree_traits::directed_type, VertexProperty, EdgeProperty>;
 
    base _graph;
 
  public:
    explicit network_common() : _graph()
    {
    }
 
    explicit network_common(size_t n) : _graph(n)
    {
    }
 
    using vertex_descriptor = typename base::vertex_descriptor;
 
    using edge_descriptor = typename base::edge_descriptor;
 
    using vertex_property = VertexProperty;
 
    using edge_property = EdgeProperty;
 
    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 out_edge_iterator = typename base::out_edge_iterator;
 
    using edge_parallel_category = typename base::edge_parallel_category;
 
 
    bool is_isomorphic(network_common const &other) const
    {
        return boost::isomorphism(_graph, other._graph);
    }
 
    vertex_descriptor find_root_from(vertex_descriptor u) const
    {
        std::vector<vertex_descriptor> order;
        topological_sort(this->_graph, back_inserter(order));
        return order.back();
    }
 
    degree_size_type degree(vertex_descriptor u) const
    {
        return boost::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
    {
        return boost::out_degree(v, _graph);
    }
 
    bool has_predecessor(vertex_descriptor u) const
    {
        auto range = boost::in_edges(u, _graph);
        return std::distance(range.first, range.second) > 0;
    }
 
    vertex_descriptor predecessor(vertex_descriptor u) const
    {
        auto range = boost::in_edges(u, _graph);
        assert(std::distance(range.first, range.second) == 1);
        return source(*range.first);
    }
 
    bool has_successors(vertex_descriptor u) const
    {
        auto range = boost::out_edges(u, _graph);
        assert(std::distance(range.first, range.second) != 1);
        return std::distance(range.first, range.second) >= 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); });
    }
 
    std::optional<edge_descriptor> edge(vertex_descriptor u, vertex_descriptor v) const
    {
        auto p = boost::edge(u, v, _graph);
        return p.second ? std::make_optional(p.first) : std::nullopt;
    }
 
    vertex_descriptor source(edge_descriptor e) const
    {
        return boost::source(e, _graph);
    }
 
    vertex_descriptor target(edge_descriptor e) const
    {
        return boost::target(e, _graph);
    }
 
 
 
    vertex_descriptor add_vertex()
    {
        return boost::add_vertex(_graph);
    }
 
    void clear_vertex(vertex_descriptor u)
    {
        return boost::clear_vertex(u, _graph);
    }
 
    void remove_vertex(vertex_descriptor u)
    {
        clear_vertex(u);
        return boost::remove_vertex(u, _graph);
    }
 
    edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v)
    {
        return boost::add_edge(u, v, _graph).first;
    }
 
    void remove_edge(vertex_descriptor u, vertex_descriptor v)
    {
        return boost::remove_edge(u, v, _graph);
    }
 
    void remove_edge(edge_descriptor e)
    {
        return boost::remove_edge(e, _graph);
    }
 
 
 
    auto in_edges(vertex_descriptor u) const
    {
        return boost::make_iterator_range(boost::in_edges(u, _graph));
    }
 
    auto out_edges(vertex_descriptor u) const
    {
        return boost::make_iterator_range(boost::out_edges(u, _graph));
    }
 
    auto vertices() const
    {
        return boost::make_iterator_range(boost::vertices(_graph));
    }
 
 
 
    template <typename DFSVisitor> void depth_first_search(vertex_descriptor start, DFSVisitor &vis)
    {
        // Give a BGL interface to a Quetzal visitor
        struct wrapper : boost::default_dfs_visitor
        {
            network_common &_graph;
            DFSVisitor &_visitor;
 
            wrapper(network_common &graph, DFSVisitor &v) : _graph(graph), _visitor(v)
            {
            }
            void discover_vertex(vertex_descriptor v, const base &g)
            {
                _visitor(boost::visit::pre, v);
            }
            void tree_edge(const edge_descriptor &e, const base &g)
            {
                _visitor(boost::visit::in, _graph.target(e));
            }
            void finish_vertex(vertex_descriptor v, const base &g)
            {
                _visitor(boost::visit::post, v);
            }
        } bgl_visitor(*this, vis);
 
        std::vector<boost::default_color_type> colors(boost::num_vertices(_graph));
        boost::iterator_property_map color_map(colors.begin(), boost::get(boost::vertex_index, _graph));
        return boost::depth_first_search(_graph, boost::visitor(bgl_visitor).color_map(color_map).root_vertex(start));
    }
 
    template <typename DFSVisitor> void depth_first_search(vertex_descriptor start, DFSVisitor &vis) const
    {
        // Give a BGL interface to a Quetzal visitor
        struct wrapper : boost::default_dfs_visitor
        {
            const network_common &_graph;
            DFSVisitor &_visitor;
 
            wrapper(const network_common &graph, DFSVisitor &v) : _graph(graph), _visitor(v)
            {
            }
            void discover_vertex(vertex_descriptor v, const base &g)
            {
                _visitor(boost::visit::pre, v);
            }
            void tree_edge(const edge_descriptor &e, const base &g)
            {
                _visitor(boost::visit::in, _graph.target(e));
            }
            void finish_vertex(vertex_descriptor v, const base &g)
            {
                _visitor(boost::visit::post, v);
            }
        } bgl_visitor(*this, vis);
 
        std::vector<boost::default_color_type> colors(boost::num_vertices(_graph));
        boost::iterator_property_map color_map(colors.begin(), boost::get(boost::vertex_index, _graph));
        return boost::depth_first_search(_graph, boost::visitor(bgl_visitor).color_map(color_map).root_vertex(start));
    }
 
 
 
    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 class network_common
 
} // end namespace detail
 
template <class VertexProperty, class EdgeProperty> class network
{
};
 
template <>
class network<no_property, no_property>
    : public detail::network_common<no_property, no_property, network<no_property, no_property>>
{
    using base = detail::network_common<no_property, no_property, network<no_property, no_property>>;
 
  public:
 
    explicit network() : base()
    {
    }
 
    explicit network(size_t n) : base(n)
    {
    }
 
 
    vertex_descriptor add_vertex()
    {
        return boost::add_vertex(_graph);
    }
 
    std::vector<edge_descriptor> add_edges(vertex_descriptor parent, std::vector<vertex_descriptor> children)
    {
        assert(children.size() > 1);
        for (auto const &c : children)
        {
            assert(parent != c);
        }
 
        std::vector<edge_descriptor> edges(children.size());
        std::transform(children.cbegin(), children.cend(), edges.begin(),
                       [parent, this](auto c) { return boost::add_edge(parent, c, this->_graph).first; });
        return edges;
    }
 
 
}; // end specialization network<boost::no::property, boost::no_property>
 
template <class VertexProperty>
    requires(!std::is_same_v<VertexProperty, no_property>)
class network<VertexProperty, no_property>
    : public detail::network_common<VertexProperty, no_property, network<VertexProperty, no_property>>
{
  private:
    using base = detail::network_common<VertexProperty, no_property, network<VertexProperty, no_property>>;
 
  public:
    using edge_descriptor = typename base::edge_descriptor;
 
    using vertex_descriptor = typename base::vertex_descriptor;
 
 
    explicit network() : base()
    {
    }
 
    explicit network(size_t n) : base(n)
    {
    }
 
 
 
    auto add_vertex(const VertexProperty &p)
    {
        return boost::add_vertex(p, this->_graph);
    }
 
    std::vector<edge_descriptor> add_edges(vertex_descriptor parent, std::vector<vertex_descriptor> children)
    {
        assert(children.size() > 1);
        for (auto const &c : children)
        {
            assert(parent != c);
        }
 
        std::vector<edge_descriptor> edges(children.size());
        std::transform(children.cbegin(), children.cend(), edges.begin(),
                       [parent, this](auto c) { return boost::add_edge(parent, c, this->_graph).first; });
        return edges;
    }
 
 
 
    const VertexProperty &operator[](vertex_descriptor v) const
    {
        return this->_graph[v];
    }
 
    VertexProperty &operator[](vertex_descriptor v)
    {
        return this->_graph[v];
    }
 
 
}; // end specialization network<Vertex, boost::no_property>
 
template <class EdgeProperty>
    requires(!std::is_same_v<EdgeProperty, no_property>)
class network<no_property, EdgeProperty>
    : public detail::network_common<no_property, EdgeProperty, network<no_property, EdgeProperty>>
{
  private:
    using base = detail::network_common<no_property, EdgeProperty, network<no_property, EdgeProperty>>;
 
  public:
    using edge_descriptor = typename base::edge_descriptor;
 
    using vertex_descriptor = typename base::vertex_descriptor;
 
 
    explicit network() : base()
    {
    }
 
    explicit network(size_t n) : base(n)
    {
    }
 
 
 
    vertex_descriptor add_vertex()
    {
        return boost::add_vertex(this->_graph);
    }
 
    std::vector<edge_descriptor> add_edges(vertex_descriptor parent,
                                           const std::vector<std::pair<vertex_descriptor, EdgeProperty>> &children)
    {
        assert(children.size() > 1);
        for (auto const &c : children)
        {
            assert(parent != c);
        }
 
        std::vector<edge_descriptor> edges(children.size());
        std::transform(children.cbegin(), children.cend(), edges.begin(), [parent, this](const auto &c) {
            return boost::add_edge(parent, c.first, c.second, this->_graph).first;
        });
        return edges;
    }
 
 
 
    const EdgeProperty &operator[](const edge_descriptor &edge) const
    {
        return this->_graph[edge];
    }
 
    EdgeProperty &operator[](const edge_descriptor &edge)
    {
        return this->_graph[edge];
    }
 
 
}; // end specialization network<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 network<VertexProperty, EdgeProperty>
    : public detail::network_common<VertexProperty, EdgeProperty, network<no_property, EdgeProperty>>
{
  private:
    using base = detail::network_common<VertexProperty, EdgeProperty, network<no_property, EdgeProperty>>;
 
  public:
    using edge_descriptor = typename base::edge_descriptor;
 
    using vertex_descriptor = typename base::vertex_descriptor;
 
 
 
    explicit network() : base()
    {
    }
 
    explicit network(size_t n) : base(n)
    {
    }
 
 
 
    vertex_descriptor add_vertex(const VertexProperty &p)
    {
        return boost::add_vertex(p, this->_graph);
    }
 
    std::vector<edge_descriptor> add_edges(vertex_descriptor parent,
                                           std::vector<std::tuple<vertex_descriptor, EdgeProperty>> children)
    {
        assert(children.size() > 1);
        for (auto const &[c, p] : children)
        {
            assert(parent != c);
        }
 
        std::vector<edge_descriptor> edges(children.size());
        std::transform(children.cbegin(), children.cend(), edges.begin(), [parent, this](const auto &c) {
            return boost::add_edge(parent, std::get<0>(c), std::get<1>(c), this->_graph).first;
        });
        return edges;
    }
 
 
 
    const VertexProperty &operator[](vertex_descriptor v) const
    {
        return this->_graph[v];
    }
 
    VertexProperty &operator[](vertex_descriptor v)
    {
        return this->_graph[v];
    }
 
    const EdgeProperty &operator[](const edge_descriptor &edge) const
    {
        return this->_graph[edge];
    }
 
    EdgeProperty &operator[](const edge_descriptor &edge)
    {
        return this->_graph[edge];
    }
 
};
 
} // end namespace quetzal::coalescence