graph.hpp

// Copyright 2021 Arnaud Becheler    <abechele@umich.edu>
 
 
#pragma once
 
#include <boost/range/adaptor/transformed.hpp>
#include <boost/range/iterator_range.hpp>
 
#include <boost/graph/connected_components.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/topological_sort.hpp>
 
#include "detail/adl_resolution.hpp"
#include "detail/concepts.hpp"
 
#include <algorithm>
#include <iostream>
#include <optional>
#include <type_traits>
#include <ranges>
 
namespace quetzal::geography
{
 
namespace detail
{
 
// Base class and common implementation
template <class CRTP, class VertexProperty, class EdgeProperty, connectedness Representation, directional Directed>
class graph_common
{
 
  protected:
    using base_type = typename Representation::rebind<Directed, VertexProperty, EdgeProperty>;
    base_type _graph;
 
  public:
    explicit graph_common() : _graph()
    {
    }
 
    explicit graph_common(size_t n) : _graph(n)
    {
    }
 
    using vertex_property = VertexProperty;
 
    using edge_property = EdgeProperty;
 
    using directed_category = Directed;
 
    using vertex_descriptor = typename base_type::vertex_descriptor;
 
    using edge_descriptor = typename base_type::edge_descriptor;
 
    using degree_size_type = typename base_type::degree_size_type;
 
    using traversal_category = typename base_type::traversal_category;
 
    using in_edge_iterator = typename base_type::in_edge_iterator;
 
    using out_edge_iterator = typename base_type::out_edge_iterator;
 
    using edge_parallel_category = typename base_type::edge_parallel_category;
 
 
    int num_vertices() const
    {
        return boost::num_vertices(_graph);
    }
 
    int num_edges() const
    {
        return boost::num_edges(_graph);
    }
 
    bool is_isomorphic(graph_common const &other) const
    {
        return boost::isomorphism(_graph, other._graph);
    }
 
    degree_size_type degree(vertex_descriptor u) const
    {
        return boost::degree(u, _graph);
    }
 
    degree_size_type in_degree(vertex_descriptor u) const
    {
        return boost::in_degree(u, _graph);
    }
 
    degree_size_type out_degree(vertex_descriptor v) const
    {
        return boost::out_degree(v, _graph);
    }
 
    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));
    }
 
    auto edges() const
    {
        auto [first, last] = boost::edges(_graph);
        return std::ranges::subrange(first, last);
    }
 
 
    static constexpr inline vertex_descriptor null_vertex()
    {
        return base_type::null_vertex();
    }
 
}; // end class graph_common
 
} // end namespace detail
 
// Base for template partial specialization
template <class VertexProperty, class EdgeProperty, connectedness Representation, directional Directed>
class graph
{
};
 
template < connectedness Representation, directional Directed>
class graph<no_property, no_property, Representation, Directed> : 
public detail::graph_common<graph<no_property, no_property, Representation, Directed>, no_property, no_property, Representation, Directed>
{
  private:
    using self_type = graph<no_property, no_property, Representation, Directed>;
    using base_type = detail::graph_common<self_type, no_property, no_property, Representation, Directed>;
 
  public:
 
    explicit graph() : base_type()
    {
    }
 
    explicit graph(size_t n) : base_type(n)
    {
    }
 
}; // end specialization graph<boost::no::property, boost::no_property>
 
template <class VertexProperty, connectedness Representation, directional Directed>
    requires(!std::is_same_v<VertexProperty, no_property>)
class graph<VertexProperty, no_property, Representation, Directed>
    : public detail::graph_common<graph<VertexProperty, no_property, Representation, Directed>, VertexProperty,
                                  no_property, Representation, Directed>
{
  private:
    using self_type = graph<VertexProperty, no_property, Representation, Directed>;
    using base_type = detail::graph_common<self_type, VertexProperty, no_property, Representation, Directed>;
 
  public:
    using edge_descriptor = typename base_type::edge_descriptor;
 
    using vertex_descriptor = typename base_type::vertex_descriptor;
 
 
    explicit graph() : base_type()
    {
    }
 
    explicit graph(size_t n) : base_type(n)
    {
    }
 
 
 
    auto add_vertex(const VertexProperty &p)
    {
        return boost::add_vertex(p, this->_graph);
    }
 
 
 
    const VertexProperty &operator[](vertex_descriptor v) const
    {
        return this->_graph[v];
    }
 
    VertexProperty &operator[](vertex_descriptor v)
    {
        return this->_graph[v];
    }
 
 
}; // end specialization graph<Vertex, no_property>
 
template <class EdgeProperty, connectedness Representation, directional Directed>
    requires(!std::is_same_v<EdgeProperty, no_property>)
class graph<no_property, EdgeProperty, Representation, Directed>
    : public detail::graph_common<graph<no_property, EdgeProperty, Representation, Directed>, no_property, EdgeProperty,
                                  Representation, Directed>
{
  private:
    using self_type = graph<no_property, EdgeProperty, Representation, Directed>;
    using base_type = detail::graph_common<self_type, no_property, EdgeProperty, Representation, Directed>;
 
  public:
    using edge_descriptor = typename base_type::edge_descriptor;
 
    using vertex_descriptor = typename base_type::vertex_descriptor;
 
 
    explicit graph() : base_type()
    {
    }
 
    explicit graph(size_t n) : base_type(n)
    {
    }
 
 
 
    edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v, const EdgeProperty &p)
    {
        return boost::add_edge(u, v, p, this->_graph).first;
    }
 
 
 
    const EdgeProperty &operator[](const edge_descriptor &edge) const
    {
        return this->_graph[edge];
    }
 
    EdgeProperty &operator[](const edge_descriptor &edge)
    {
        return this->_graph[edge];
    }
 
 
}; // end specialization graph<boost::no_property, Edge>
 
template <class VertexProperty, class EdgeProperty, connectedness Representation, directional Directed>
    requires(!std::is_same_v<VertexProperty, no_property> and !std::is_same_v<EdgeProperty, no_property>)
class graph<VertexProperty, EdgeProperty, Representation, Directed>
    : public detail::graph_common<graph<VertexProperty, EdgeProperty, Representation, Directed>, VertexProperty,
                                  EdgeProperty, Representation, Directed>
{
  private:
    using self_type = graph<VertexProperty, EdgeProperty, Representation, Directed>;
    using base_type = detail::graph_common<self_type, VertexProperty, EdgeProperty, Representation, Directed>;
 
  public:
    using edge_descriptor = typename base_type::edge_descriptor;
 
    using vertex_descriptor = typename base_type::vertex_descriptor;
 
 
 
    explicit graph() : base_type()
    {
    }
 
    explicit graph(size_t n) : base_type(n)
    {
    }
 
 
 
    auto add_vertex(const VertexProperty &p)
    {
        return boost::add_vertex(p, this->_graph);
    }
 
    edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v, const EdgeProperty &p)
    {
        return boost::add_edge(u, v, p, this->_graph).first;
    }
 
 
 
    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::geography