You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
648 lines
25 KiB
648 lines
25 KiB
#pragma once
|
|
|
|
#include <utility>
|
|
#include "compressed_vector_tuple.hpp"
|
|
#include "../../utils/pointer_wrapper.hpp"
|
|
#include "../../utils/type_list.hpp"
|
|
|
|
// a specialization of n-partite graph
|
|
// the graph consists of nodes of N types, each node can only be connected with previous type or next type to its type
|
|
// and the edges of the graph should not have any property (like weight or what else)
|
|
namespace detail::relation_graph
|
|
{
|
|
enum class edge_bidirection { to_prev, to_next };
|
|
|
|
template <typename Graph, size_t TypeIndex, edge_bidirection direction>
|
|
struct edge_iterator;
|
|
|
|
template <typename Graph, size_t TypeIndex>
|
|
struct node_proxy;
|
|
|
|
template <typename Graph, size_t TypeIndex>
|
|
struct node_container_proxy;
|
|
|
|
template <typename Graph, size_t TypeIndex, edge_bidirection direction>
|
|
struct edge_proxy {
|
|
private:
|
|
friend struct edge_iterator<Graph, TypeIndex, direction>;
|
|
using index_type = typename Graph::index_type;
|
|
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
index_type m_edge_index{};
|
|
|
|
static constexpr auto to_node_layer =
|
|
direction == edge_bidirection::to_prev ? (TypeIndex) : ((TypeIndex + 1) % Graph::layer_count);
|
|
|
|
public:
|
|
edge_proxy(pointer_wrapper<Graph> graph_ptr, index_type edge_index) : m_graph_ptr(graph_ptr), m_edge_index(edge_index) {}
|
|
|
|
edge_proxy(Graph* graph_ptr, index_type edge_index) : m_graph_ptr(graph_ptr), m_edge_index(edge_index) {}
|
|
|
|
auto to()
|
|
{
|
|
const auto to = std::get<TypeIndex>(m_graph_ptr->m_edges).template fetch<0>(m_edge_index).to;
|
|
assert(to != Graph::invalid_index);
|
|
return node_proxy<Graph, to_node_layer>(m_graph_ptr, static_cast<index_type>(to));
|
|
}
|
|
|
|
auto to() const
|
|
{
|
|
const auto to = std::get<TypeIndex>(m_graph_ptr->m_edges).template fetch<0>(m_edge_index).to;
|
|
assert(to != Graph::invalid_index);
|
|
return node_proxy<Graph, to_node_layer>(m_graph_ptr, static_cast<index_type>(to));
|
|
}
|
|
|
|
auto& property()
|
|
{
|
|
static_assert(Graph::template has_edge_property<TypeIndex>,
|
|
"called layer of relation graph does not have edge property.");
|
|
auto& edges = std::get<TypeIndex>(m_graph_ptr->m_edges);
|
|
return edges.template fetch<1>(m_edge_index >> 1);
|
|
}
|
|
|
|
auto& property() const
|
|
{
|
|
static_assert(Graph::template has_edge_property<TypeIndex>,
|
|
"called layer of relation graph does not have edge property.");
|
|
auto& edges = std::get<TypeIndex>(m_graph_ptr->m_edges);
|
|
return edges.template fetch<1>(m_edge_index >> 1);
|
|
}
|
|
};
|
|
|
|
template <typename Graph, size_t TypeIndex, edge_bidirection direction>
|
|
struct edge_iterator {
|
|
private:
|
|
using index_type = typename Graph::index_type;
|
|
static constexpr auto invalid_index = Graph::invalid_index;
|
|
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
index_type m_edge_index{};
|
|
|
|
public:
|
|
using iterator_category = std::forward_iterator_tag;
|
|
using value_type = edge_proxy<Graph, TypeIndex, direction>;
|
|
using difference_type = std::ptrdiff_t;
|
|
using pointer = value_type*;
|
|
using reference = value_type;
|
|
|
|
edge_iterator(pointer_wrapper<Graph> graph_ptr, index_type edge_index) : m_graph_ptr(graph_ptr), m_edge_index(edge_index) {}
|
|
|
|
bool operator==(const edge_iterator& other) const
|
|
{
|
|
return m_graph_ptr == other.m_graph_ptr && m_edge_index == other.m_edge_index;
|
|
}
|
|
|
|
bool operator!=(const edge_iterator& other) const { return !(*this == other); }
|
|
|
|
value_type operator*() const { return value_type(m_graph_ptr, m_edge_index); }
|
|
|
|
value_type operator->() const { return value_type(m_graph_ptr, m_edge_index); }
|
|
|
|
edge_iterator& operator++()
|
|
{
|
|
if (m_edge_index != invalid_index) {
|
|
m_edge_index = std::get<TypeIndex>(m_graph_ptr->m_edges).template fetch<0>(m_edge_index).next;
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
edge_iterator operator++(int)
|
|
{
|
|
edge_iterator tmp = *this;
|
|
++(*this);
|
|
return tmp;
|
|
}
|
|
};
|
|
|
|
template <typename Graph, size_t TypeIndex, edge_bidirection direction>
|
|
struct edge_range {
|
|
private:
|
|
using index_type = typename Graph::index_type;
|
|
static constexpr auto invalid_index = Graph::invalid_index;
|
|
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
index_type m_edge_index{};
|
|
|
|
public:
|
|
using iterator = edge_iterator<Graph, TypeIndex, direction>;
|
|
|
|
edge_range(pointer_wrapper<Graph> graph_ptr, index_type edge_index) : m_graph_ptr(graph_ptr), m_edge_index(edge_index) {}
|
|
|
|
bool empty() const { return begin() == end(); }
|
|
|
|
iterator begin() { return iterator(m_graph_ptr, m_edge_index); }
|
|
|
|
iterator end() { return iterator(m_graph_ptr, invalid_index); }
|
|
|
|
iterator begin() const { return iterator(m_graph_ptr, m_edge_index); }
|
|
|
|
iterator end() const { return iterator(m_graph_ptr, invalid_index); }
|
|
};
|
|
|
|
template <typename Graph, size_t TypeIndex>
|
|
struct node_proxy {
|
|
private:
|
|
friend struct node_container_proxy<Graph, TypeIndex>;
|
|
using index_type = typename Graph::index_type;
|
|
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
index_type m_node_index{};
|
|
|
|
public:
|
|
node_proxy(pointer_wrapper<Graph> graph_ptr, index_type node_index) : m_graph_ptr(graph_ptr), m_node_index(node_index) {}
|
|
|
|
auto index() const { return m_node_index; }
|
|
|
|
auto& property()
|
|
{
|
|
static_assert(Graph::template has_node_property<TypeIndex>,
|
|
"called layer of relation graph does not have node property.");
|
|
return std::get<TypeIndex>(m_graph_ptr->m_nodes).template fetch<1>(m_node_index);
|
|
}
|
|
|
|
auto& property() const
|
|
{
|
|
static_assert(Graph::template has_node_property<TypeIndex>,
|
|
"called layer of relation graph does not have node property.");
|
|
return std::get<TypeIndex>(m_graph_ptr->m_nodes).template fetch<1>(m_node_index);
|
|
}
|
|
|
|
template <edge_bidirection direction>
|
|
auto edges()
|
|
{
|
|
constexpr auto edge_tuple_index = Graph::template edge_tuple_index_v<TypeIndex, direction>;
|
|
const auto& node = std::get<TypeIndex>(m_graph_ptr->m_nodes).template fetch<0>(m_node_index);
|
|
if constexpr (direction == edge_bidirection::to_prev)
|
|
return edge_range<Graph, edge_tuple_index, direction>(m_graph_ptr, node.first_edge_to_prev);
|
|
else if constexpr (direction == edge_bidirection::to_next)
|
|
return edge_range<Graph, edge_tuple_index, direction>(m_graph_ptr, node.first_edge_to_next);
|
|
else
|
|
static_assert(false, "illegal edge direction.");
|
|
}
|
|
|
|
template <edge_bidirection direction>
|
|
auto edges() const
|
|
{
|
|
constexpr auto edge_tuple_index = Graph::template edge_tuple_index_v<TypeIndex, direction>;
|
|
const auto& node = std::get<TypeIndex>(m_graph_ptr->m_nodes).template fetch<0>(m_node_index);
|
|
if constexpr (direction == edge_bidirection::to_prev)
|
|
return edge_range<Graph, edge_tuple_index, direction>(m_graph_ptr, node.first_edge_to_prev);
|
|
else if constexpr (direction == edge_bidirection::to_next)
|
|
return edge_range<Graph, edge_tuple_index, direction>(m_graph_ptr, node.first_edge_to_next);
|
|
else
|
|
static_assert(false, "illegal edge direction.");
|
|
}
|
|
};
|
|
|
|
template <typename Graph, size_t TypeIndex>
|
|
bool operator==(const node_proxy<Graph, TypeIndex>& lhs, const node_proxy<Graph, TypeIndex>& rhs)
|
|
{
|
|
return lhs.m_graph_ptr == rhs.m_graph_ptr && lhs.m_node_index == rhs.m_node_index;
|
|
}
|
|
|
|
template <typename Graph, size_t TypeIndex>
|
|
struct node_iterator {
|
|
private:
|
|
using index_type = typename Graph::index_type;
|
|
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
index_type m_node_index{};
|
|
|
|
public:
|
|
using iterator_category = std::random_access_iterator_tag;
|
|
using value_type = node_proxy<Graph, TypeIndex>;
|
|
using difference_type = std::ptrdiff_t;
|
|
using pointer = value_type*;
|
|
using reference = value_type;
|
|
|
|
node_iterator(pointer_wrapper<Graph> graph_ptr, index_type node_index) : m_graph_ptr(graph_ptr), m_node_index(node_index) {}
|
|
|
|
bool operator==(const node_iterator& other) const
|
|
{
|
|
return m_graph_ptr == other.m_graph_ptr && m_node_index == other.m_node_index;
|
|
}
|
|
|
|
bool operator!=(const node_iterator& other) const { return !(*this == other); }
|
|
|
|
bool operator<(const node_iterator& other) const { return m_node_index < other.m_node_index; }
|
|
|
|
bool operator<=(const node_iterator& other) const { return m_node_index <= other.m_node_index; }
|
|
|
|
bool operator>(const node_iterator& other) const { return m_node_index > other.m_node_index; }
|
|
|
|
bool operator>=(const node_iterator& other) const { return m_node_index >= other.m_node_index; }
|
|
|
|
value_type operator*() { return value_type(m_graph_ptr, m_node_index); }
|
|
|
|
value_type operator*() const { return value_type(m_graph_ptr, m_node_index); }
|
|
|
|
// value_type operator->() { return value_type(m_graph_ptr, m_node_index); }
|
|
|
|
// value_type operator->() const { return value_type(m_graph_ptr, m_node_index); }
|
|
|
|
node_iterator& operator++()
|
|
{
|
|
++m_node_index;
|
|
return *this;
|
|
}
|
|
|
|
node_iterator operator++(int)
|
|
{
|
|
node_iterator tmp = *this;
|
|
++m_node_index;
|
|
return tmp;
|
|
}
|
|
|
|
node_iterator& operator--()
|
|
{
|
|
--m_node_index;
|
|
return *this;
|
|
}
|
|
|
|
node_iterator operator--(int)
|
|
{
|
|
node_iterator tmp = *this;
|
|
--m_node_index;
|
|
return tmp;
|
|
}
|
|
|
|
node_iterator& operator+=(difference_type n)
|
|
{
|
|
m_node_index += static_cast<index_type>(n);
|
|
return *this;
|
|
}
|
|
|
|
node_iterator& operator-=(difference_type n)
|
|
{
|
|
m_node_index -= static_cast<index_type>(n);
|
|
return *this;
|
|
}
|
|
|
|
node_iterator operator+(difference_type n) const
|
|
{
|
|
return node_iterator(m_graph_ptr, static_cast<index_type>(m_node_index + n));
|
|
}
|
|
|
|
node_iterator operator-(difference_type n) const
|
|
{
|
|
return node_iterator(m_graph_ptr, static_cast<index_type>(m_node_index - n));
|
|
}
|
|
|
|
difference_type operator-(const node_iterator& other) const
|
|
{
|
|
return static_cast<difference_type>(m_node_index) - static_cast<difference_type>(other.m_node_index);
|
|
}
|
|
|
|
value_type operator[](difference_type n) const
|
|
{
|
|
return value_type(m_graph_ptr, static_cast<index_type>(m_node_index + n));
|
|
}
|
|
};
|
|
|
|
template <typename Graph, size_t TypeIndex>
|
|
struct node_container_proxy {
|
|
private:
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
|
|
public:
|
|
using iterator = node_iterator<Graph, TypeIndex>;
|
|
using const_iterator = node_iterator<Graph, TypeIndex>;
|
|
using index_type = typename Graph::index_type;
|
|
|
|
node_container_proxy() = default;
|
|
~node_container_proxy() = default;
|
|
node_container_proxy(const node_container_proxy&) = default;
|
|
node_container_proxy(node_container_proxy&&) = default;
|
|
node_container_proxy& operator=(const node_container_proxy&) = default;
|
|
node_container_proxy& operator=(node_container_proxy&&) = default;
|
|
|
|
node_container_proxy(const Graph* ptr) : m_graph_ptr(const_cast<Graph*>(ptr)) {}
|
|
|
|
template <typename size_type>
|
|
void reserve(size_type size)
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
std::get<TypeIndex>(m_graph_ptr->m_nodes).reserve_all(static_cast<size_t>(size));
|
|
}
|
|
|
|
template <typename size_type>
|
|
void resize(size_type size)
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
std::get<TypeIndex>(m_graph_ptr->m_nodes).resize_all(static_cast<size_t>(size));
|
|
}
|
|
|
|
bool empty() const { return std::get<TypeIndex>(m_graph_ptr->m_nodes).empty(); }
|
|
|
|
auto size() const { return std::get<TypeIndex>(m_graph_ptr->m_nodes).size(); }
|
|
|
|
void clear() { return std::get<TypeIndex>(m_graph_ptr->m_nodes).clear_all(); }
|
|
|
|
void shrink_to_fit() { return std::get<TypeIndex>(m_graph_ptr->m_nodes).shrink_to_fit_all(); }
|
|
|
|
template <typename size_type>
|
|
node_proxy<Graph, TypeIndex> operator[](size_type index)
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
return node_proxy<Graph, TypeIndex>(m_graph_ptr, static_cast<index_type>(index));
|
|
}
|
|
|
|
template <typename size_type>
|
|
node_proxy<Graph, TypeIndex> operator[](size_type index) const
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
return node_proxy<Graph, TypeIndex>(m_graph_ptr, static_cast<index_type>(index));
|
|
}
|
|
|
|
iterator begin() { return iterator(m_graph_ptr, 0); }
|
|
|
|
iterator end() { return iterator(m_graph_ptr, static_cast<index_type>(size())); }
|
|
|
|
const_iterator begin() const { return const_iterator(m_graph_ptr, 0); }
|
|
|
|
const_iterator end() const { return const_iterator(m_graph_ptr, static_cast<index_type>(size())); }
|
|
|
|
template <typename container>
|
|
void set_properties(container&& cont)
|
|
{
|
|
static_assert(Graph::template has_node_property<TypeIndex>,
|
|
"called layer of relation graph does not have node property.");
|
|
resize(cont.size());
|
|
std::get<TypeIndex>(m_graph_ptr->m_nodes).template raw<1>() = cont;
|
|
}
|
|
};
|
|
|
|
template <typename Graph, size_t TypeIndex>
|
|
struct edge_container_proxy {
|
|
private:
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
|
|
public:
|
|
edge_container_proxy() = default;
|
|
~edge_container_proxy() = default;
|
|
edge_container_proxy(const edge_container_proxy&) = default;
|
|
edge_container_proxy(edge_container_proxy&&) = default;
|
|
edge_container_proxy& operator=(const edge_container_proxy&) = default;
|
|
edge_container_proxy& operator=(edge_container_proxy&&) = default;
|
|
|
|
edge_container_proxy(const Graph* ptr) : m_graph_ptr(const_cast<Graph*>(ptr)) {}
|
|
|
|
template <typename size_type>
|
|
void reserve(size_type size)
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
std::get<TypeIndex>(m_graph_ptr->m_edges).reserve_all(static_cast<size_t>(size));
|
|
}
|
|
|
|
template <typename size_type>
|
|
void resize(size_type size)
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
std::get<TypeIndex>(m_graph_ptr->m_edges).resize_all(static_cast<size_t>(size));
|
|
}
|
|
|
|
bool empty() const { return std::get<TypeIndex>(m_graph_ptr->m_edges).empty(); }
|
|
|
|
auto size() const { return static_cast<typename Graph::size_type>(std::get<TypeIndex>(m_graph_ptr->m_edges).size()); }
|
|
|
|
void clear() { std::get<TypeIndex>(m_graph_ptr->m_edges).clear_all(); }
|
|
|
|
void shrink_to_fit() { std::get<TypeIndex>(m_graph_ptr->m_edges).shrink_to_fit_all(); }
|
|
};
|
|
|
|
template <typename IndexType>
|
|
struct node {
|
|
static_assert(std::is_integral_v<IndexType>);
|
|
|
|
node() = default;
|
|
~node() = default;
|
|
node(const node&) = default;
|
|
node(node&&) = default;
|
|
node& operator=(const node&) = default;
|
|
node& operator=(node&&) = default;
|
|
|
|
node(IndexType first_edge_to_prev, IndexType first_edge_to_next)
|
|
: first_edge_to_prev(first_edge_to_prev), first_edge_to_next(first_edge_to_next)
|
|
{
|
|
}
|
|
|
|
IndexType first_edge_to_prev{std::numeric_limits<IndexType>::max()};
|
|
IndexType first_edge_to_next{std::numeric_limits<IndexType>::max()};
|
|
};
|
|
|
|
template <typename IndexType>
|
|
struct edge {
|
|
static_assert(std::is_integral_v<IndexType>);
|
|
|
|
edge() = default;
|
|
~edge() = default;
|
|
edge(const edge&) = default;
|
|
edge(edge&&) = default;
|
|
edge& operator=(const edge&) = default;
|
|
edge& operator=(edge&&) = default;
|
|
|
|
edge(IndexType to, IndexType next) : to(to), next(next) {}
|
|
|
|
IndexType to{};
|
|
IndexType next{std::numeric_limits<IndexType>::max()};
|
|
};
|
|
|
|
template <typename IndexType, typename NodePropertyTuple, typename EdgePropertyTuple>
|
|
class graph;
|
|
|
|
template <typename IndexType, typename... NodeProperties, typename... EdgeProperties>
|
|
class graph<IndexType, type_list<NodeProperties...>, type_list<EdgeProperties...>>
|
|
{
|
|
protected:
|
|
static_assert(std::is_integral_v<IndexType>);
|
|
static_assert(sizeof...(NodeProperties) == sizeof...(EdgeProperties));
|
|
static constexpr auto invalid_index = std::numeric_limits<IndexType>::max();
|
|
|
|
std::tuple<compressed_vector_tuple<node<IndexType>, NodeProperties>...> m_nodes{};
|
|
// for i-th tuple: the edge of layer i+1 to layer i and layer i to layer i+1, with the property to the edges
|
|
// here the i+1 is modeled by layer count n
|
|
std::tuple<compressed_vector_tuple<edge<IndexType>, EdgeProperties>...> m_edges{};
|
|
|
|
template <size_t from_type_index, edge_bidirection direction>
|
|
static constexpr auto edge_tuple_index_v =
|
|
(direction == edge_bidirection::to_prev)
|
|
? ((from_type_index - 1 + sizeof...(NodeProperties)) % (sizeof...(NodeProperties)))
|
|
: from_type_index;
|
|
|
|
public:
|
|
using index_type = IndexType;
|
|
static constexpr size_t layer_count = sizeof...(NodeProperties);
|
|
template <size_t TypeIndex>
|
|
using node_property_type = element_type_t<TypeIndex, type_list<NodeProperties...>>;
|
|
template <size_t TypeIndex>
|
|
static constexpr auto has_node_property = !std::is_void_v<node_property_type<TypeIndex>>;
|
|
template <size_t TypeIndex>
|
|
using edge_property_type = element_type_t<TypeIndex, type_list<EdgeProperties...>>;
|
|
template <size_t TypeIndex>
|
|
static constexpr auto has_edge_property = !std::is_void_v<edge_property_type<TypeIndex>>;
|
|
|
|
template <size_t TypeIndex>
|
|
node_container_proxy<graph, TypeIndex> nodes()
|
|
{
|
|
static_assert(TypeIndex < sizeof...(NodeProperties));
|
|
return node_container_proxy<graph, TypeIndex>{this};
|
|
}
|
|
|
|
template <size_t TypeIndex>
|
|
node_container_proxy<graph, TypeIndex> nodes() const
|
|
{
|
|
static_assert(TypeIndex < sizeof...(NodeProperties));
|
|
return node_container_proxy<graph, TypeIndex>{this};
|
|
}
|
|
|
|
template <size_t TypeIndex>
|
|
edge_container_proxy<graph, TypeIndex> edges()
|
|
{
|
|
static_assert(TypeIndex < sizeof...(EdgeProperties));
|
|
return edge_container_proxy<graph, TypeIndex>{this};
|
|
}
|
|
|
|
template <size_t TypeIndex>
|
|
edge_container_proxy<graph, TypeIndex> edges() const
|
|
{
|
|
static_assert(TypeIndex < sizeof...(EdgeProperties));
|
|
return edge_container_proxy<graph, TypeIndex>{this};
|
|
}
|
|
|
|
// add edge between node 'from' of layer 'type_index' to node 'to' of layer 'type_index + 1'
|
|
template <size_t type_index, typename size_type>
|
|
void add_edge_pair(size_type from, size_type to)
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
static_assert(type_index < sizeof...(NodeProperties));
|
|
|
|
add_edge<type_index, edge_bidirection::to_next>(from, to);
|
|
add_edge<(type_index + 1) % layer_count, edge_bidirection::to_prev>(to, from);
|
|
}
|
|
|
|
// add edge between node 'from' of layer 'type_index' to node 'to' of layer 'type_index + 1'
|
|
template <size_t type_index, typename size_type, typename... Args>
|
|
auto add_edge_pair(size_type from, size_type to, Args&&... args) -> std::enable_if_t<(sizeof...(Args) > 0)>
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
static_assert(type_index < sizeof...(NodeProperties));
|
|
|
|
add_edge_pair<type_index, edge_bidirection::to_next>(from, to, std::forward<Args>(args)...);
|
|
add_edge_pair<(type_index + 1) % layer_count, edge_bidirection::to_prev>(to, from, std::forward<Args>(args)...);
|
|
}
|
|
|
|
// resize nodes/edges by given graph, and copy the connection between nodes from given graph
|
|
// CAUTION: the size of properties of edges are not set
|
|
template <typename IndexType_, typename... NodeProperties_, typename... EdgeProperties_>
|
|
void copy_structure(const graph<IndexType_, type_list<NodeProperties_...>, type_list<EdgeProperties_...>>& graph)
|
|
{
|
|
static_assert(sizeof...(NodeProperties) == sizeof...(NodeProperties_));
|
|
copy_structure_impl(graph, std::index_sequence_for<NodeProperties...>{});
|
|
}
|
|
|
|
private:
|
|
template <size_t type_index, edge_bidirection direction, typename size_type>
|
|
void add_edge(size_type from, size_type to)
|
|
{
|
|
constexpr auto edge_tuple_index = edge_tuple_index_v<type_index, direction>;
|
|
auto& nodes = std::get<type_index>(m_nodes);
|
|
auto& edges = std::get<edge_tuple_index>(m_edges);
|
|
if constexpr (direction == edge_bidirection::to_prev) {
|
|
auto& next = nodes.template fetch<0>(from).first_edge_to_prev;
|
|
auto cur_edge_index = static_cast<index_type>(edges.size());
|
|
edges.template emplace_back<0>(static_cast<index_type>(to), next);
|
|
next = cur_edge_index;
|
|
} else if constexpr (direction == edge_bidirection::to_next) {
|
|
auto& next = nodes.template fetch<0>(from).first_edge_to_next;
|
|
auto cur_edge_index = static_cast<index_type>(edges.size());
|
|
edges.template emplace_back<0>(static_cast<index_type>(to), next);
|
|
next = cur_edge_index;
|
|
} else
|
|
static_assert(false, "illegal edge direction.");
|
|
}
|
|
|
|
template <size_t type_index, edge_bidirection direction, typename size_type, typename... Args>
|
|
auto add_edge(size_type from, size_type to, Args&&... args)
|
|
-> std::enable_if_t<has_edge_property<edge_tuple_index_v<type_index, direction>> && (sizeof...(Args) > 0)>
|
|
{
|
|
constexpr auto edge_tuple_index = edge_tuple_index_v<type_index, direction>;
|
|
auto& nodes = std::get<type_index>(m_nodes);
|
|
auto& edges = std::get<edge_tuple_index>(m_edges);
|
|
if constexpr (direction == edge_bidirection::to_prev) {
|
|
auto& next = nodes.template fetch<0>(from).first_edge_to_prev;
|
|
auto cur_edge_index = static_cast<index_type>(edges.size());
|
|
edges.template emplace_back<0>(static_cast<index_type>(to), next);
|
|
edges.template emplace_back<2>(std::forward<Args>(args)...);
|
|
next = cur_edge_index;
|
|
} else if constexpr (direction == edge_bidirection::to_next) {
|
|
auto& next = &nodes.template fetch<0>(from).first_edge_to_next;
|
|
auto cur_edge_index = static_cast<index_type>(edges.size());
|
|
edges.template emplace_back<0>(static_cast<index_type>(to), next);
|
|
edges.template emplace_back<2>(std::forward<Args>(args)...);
|
|
next = cur_edge_index;
|
|
} else
|
|
static_assert(false, "illegal edge direction.");
|
|
}
|
|
|
|
template <typename IndexType_, typename... NodeProperties_, typename... EdgeProperties_, size_t... indices>
|
|
void copy_structure_impl(const graph<IndexType_, type_list<NodeProperties_...>, type_list<EdgeProperties_...>>& graph,
|
|
std::index_sequence<indices...>)
|
|
{
|
|
(std::get<indices>(this->m_nodes).resize_all(std::get<indices>(graph.m_nodes).size()), ...);
|
|
((std::get<indices>(this->m_nodes).template raw<0>() = std::get<indices>(graph.m_nodes).template raw<0>()), ...);
|
|
|
|
(std::get<indices>(this->m_edges).template resize<0>(std::get<indices>(graph.m_edges).size()), ...);
|
|
((std::get<indices>(this->m_edges).template raw<0>() = std::get<indices>(graph.m_edges).template raw<0>()), ...);
|
|
((resize_edge_property<indices>(std::get<indices>(graph.m_edges).size())), ...);
|
|
}
|
|
|
|
template <size_t TypeIndex>
|
|
void resize_edge_property(size_t edge_size)
|
|
{
|
|
if constexpr (has_edge_property<TypeIndex>) {
|
|
assert(edge_size % 2 == 0);
|
|
std::get<TypeIndex>(this->m_edges).template resize<1>(edge_size >> 1);
|
|
}
|
|
}
|
|
|
|
template <typename IndexType_, typename NodePropertyTuple_, typename EdgePropertyTuple_>
|
|
friend class graph;
|
|
|
|
template <typename Graph, size_t TypeIndex>
|
|
friend struct node_proxy;
|
|
template <typename Graph, size_t TypeIndex, edge_bidirection direction>
|
|
friend struct edge_proxy;
|
|
template <typename Graph, size_t TypeIndex, edge_bidirection direction>
|
|
friend struct edge_iterator;
|
|
template <typename Graph, size_t TypeIndex, edge_bidirection direction>
|
|
friend struct edge_range;
|
|
template <typename Graph, size_t TypeIndex>
|
|
friend struct node_container_proxy;
|
|
template <typename Graph, size_t TypeIndex>
|
|
friend struct edge_container_proxy;
|
|
};
|
|
|
|
template <size_t rest_count, typename... voids>
|
|
struct empty_properties {
|
|
using type = typename empty_properties<rest_count - 1, void, voids...>::type;
|
|
};
|
|
|
|
template <typename... voids>
|
|
struct empty_properties<0, voids...> {
|
|
using type = type_list<voids...>;
|
|
};
|
|
} // namespace detail::relation_graph
|
|
|
|
using edge_bidirection = detail::relation_graph::edge_bidirection;
|
|
|
|
template <typename... node_properties>
|
|
using node_properties_t = type_list<node_properties...>;
|
|
|
|
template <typename... edge_properties>
|
|
using edge_properties_t = type_list<edge_properties...>;
|
|
|
|
template <size_t count>
|
|
using empty_properties_t = typename detail::relation_graph::empty_properties<count>::type;
|
|
|
|
template <typename index_type, typename node_properties_t, typename edge_properties_t>
|
|
using relation_graph = detail::relation_graph::graph<index_type, node_properties_t, edge_properties_t>;
|