1#ifndef ENTT_GRAPH_ADJACENCY_MATRIX_HPP
2#define ENTT_GRAPH_ADJACENCY_MATRIX_HPP
10#include "../config/config.h"
11#include "../core/iterator.hpp"
21 using size_type = std::size_t;
23 void find_next() noexcept {
24 for(; pos != last && !it[
static_cast<typename It::difference_type
>(pos)]; pos += offset) {}
28 using value_type = std::pair<size_type, size_type>;
29 using pointer = input_iterator_pointer<value_type>;
30 using reference = value_type;
31 using difference_type = std::ptrdiff_t;
32 using iterator_category = std::input_iterator_tag;
33 using iterator_concept = std::forward_iterator_tag;
35 constexpr edge_iterator() noexcept = default;
38 constexpr edge_iterator(It base, const size_type vertices, const size_type from, const size_type to, const size_type step) noexcept
39 : it{std::move(base)},
47 constexpr edge_iterator &operator++() noexcept {
53 constexpr edge_iterator operator++(
int)
noexcept {
54 const edge_iterator orig = *
this;
55 return ++(*this), orig;
58 [[nodiscard]]
constexpr reference operator*() const noexcept {
62 [[nodiscard]]
constexpr pointer operator->() const noexcept {
63 return std::make_pair<size_type>(pos / vert, pos % vert);
66 template<
typename Type>
67 friend constexpr bool operator==(
const edge_iterator<Type> &,
const edge_iterator<Type> &)
noexcept;
77template<
typename Container>
78[[nodiscard]]
constexpr bool operator==(
const edge_iterator<Container> &lhs,
const edge_iterator<Container> &rhs)
noexcept {
79 return lhs.pos == rhs.pos;
82template<
typename Container>
83[[nodiscard]]
constexpr bool operator!=(
const edge_iterator<Container> &lhs,
const edge_iterator<Container> &rhs)
noexcept {
95template<
typename Category,
typename Allocator>
97 using alloc_traits = std::allocator_traits<Allocator>;
98 static_assert(std::is_base_of_v<directed_tag, Category>,
"Invalid graph category");
99 static_assert(std::is_same_v<typename alloc_traits::value_type, std::size_t>,
"Invalid value type");
100 using container_type = std::vector<std::size_t, typename alloc_traits::template rebind_alloc<std::size_t>>;
114 using edge_iterator = internal::edge_iterator<typename container_type::const_iterator>;
153 : matrix{other.matrix, allocator},
165 : matrix{std::move(other.matrix), allocator},
189 swap(matrix, other.matrix);
190 swap(vert, other.vert);
198 return matrix.get_allocator();
215 [[nodiscard]]
bool empty() const noexcept {
216 const auto iterable =
edges();
217 return (iterable.begin() == iterable.end());
241 const auto it = matrix.cbegin();
242 const auto sz = matrix.size();
243 return {{it, vert, 0u, sz, 1u}, {it, vert, sz, sz, 1u}};
252 const auto it = matrix.cbegin();
253 const auto from = vertex * vert;
254 const auto to = from + vert;
255 return {{it, vert, from, to, 1u}, {it, vert, to, to, 1u}};
264 const auto it = matrix.cbegin();
265 const auto from = vertex;
266 const auto to = vert * vert + from;
267 return {{it, vert, from, to, vert}, {it, vert, to, to, vert}};
277 for(
auto [lhs, rhs]:
edges()) {
278 other.insert(lhs, rhs);
293 const auto pos = lhs * vert + rhs;
295 if constexpr(std::is_same_v<graph_category, undirected_tag>) {
296 const auto rev = rhs * vert + lhs;
297 ENTT_ASSERT(matrix[pos] == matrix[rev],
"Something went really wrong");
301 const auto inserted = !std::exchange(matrix[pos], 1u);
302 return {
edge_iterator{matrix.cbegin(), vert, pos, matrix.size(), 1u}, inserted};
312 const auto pos = lhs * vert + rhs;
314 if constexpr(std::is_same_v<graph_category, undirected_tag>) {
315 const auto rev = rhs * vert + lhs;
316 ENTT_ASSERT(matrix[pos] == matrix[rev],
"Something went really wrong");
320 return std::exchange(matrix[pos], 0u);
330 const auto pos = lhs * vert + rhs;
331 return pos < matrix.size() && matrix[pos];
335 container_type matrix;
Basic implementation of a directed adjacency matrix.
std::pair< edge_iterator, bool > insert(const vertex_type lhs, const vertex_type rhs)
Inserts an edge into the adjacency matrix, if it does not exist.
adjacency_matrix(const adjacency_matrix &)=default
Default copy constructor.
iota_iterator< vertex_type > vertex_iterator
Vertex iterator type.
adjacency_matrix() noexcept(noexcept(allocator_type{}))
Default constructor.
Category graph_category
Graph category tag.
bool empty() const noexcept
Returns true if an adjacency matrix is empty, false otherwise.
iterable_adaptor< out_edge_iterator > out_edges(const vertex_type vertex) const noexcept
Returns an iterable object to visit all out-edges of a vertex.
internal::edge_iterator< typename container_type::const_iterator > edge_iterator
Edge iterator type.
void swap(adjacency_matrix &other) noexcept
size_type size() const noexcept
Returns the number of vertices.
std::size_t size_type
Unsigned integer type.
Allocator allocator_type
Allocator type.
adjacency_matrix & operator=(adjacency_matrix &&) noexcept=default
Default move assignment operator.
bool contains(const vertex_type lhs, const vertex_type rhs) const
Checks if an adjacency matrix contains a given edge.
void clear() noexcept
Clears the adjacency matrix.
adjacency_matrix(const size_type vertices, const allocator_type &allocator=allocator_type{})
Constructs an empty container with a given allocator and user supplied number of vertices.
edge_iterator out_edge_iterator
Out-edge iterator type.
iterable_adaptor< in_edge_iterator > in_edges(const vertex_type vertex) const noexcept
Returns an iterable object to visit all in-edges of a vertex.
std::pair< vertex_type, vertex_type > edge_type
Edge type.
~adjacency_matrix()=default
Default destructor.
iterable_adaptor< vertex_iterator > vertices() const noexcept
adjacency_matrix & operator=(const adjacency_matrix &)=default
Default copy assignment operator.
iterable_adaptor< edge_iterator > edges() const noexcept
Returns an iterable object to visit all edges of a matrix.
edge_iterator in_edge_iterator
In-edge iterator type.
void resize(const size_type vertices)
Resizes an adjacency matrix.
size_type vertex_type
Vertex type.
adjacency_matrix(const adjacency_matrix &other, const allocator_type &allocator)
Allocator-extended copy constructor.
adjacency_matrix(adjacency_matrix &&) noexcept=default
Default move constructor.
size_type erase(const vertex_type lhs, const vertex_type rhs)
Removes the edge associated with a pair of given vertices.
adjacency_matrix(const allocator_type &allocator) noexcept
Constructs an empty container with a given allocator.
constexpr allocator_type get_allocator() const noexcept
Returns the associated allocator.
Plain iota iterator (waiting for C++20).
constexpr bool operator!=(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
constexpr bool operator==(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
Utility class to create an iterable object from a pair of iterators.