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;
24 using value_type = std::pair<size_type, size_type>;
25 using pointer = input_iterator_pointer<value_type>;
26 using reference = value_type;
27 using difference_type = std::ptrdiff_t;
28 using iterator_category = std::input_iterator_tag;
29 using iterator_concept = std::forward_iterator_tag;
31 constexpr edge_iterator() noexcept
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)},
44 for(; pos != last && !it[pos]; pos += offset) {}
47 constexpr edge_iterator &operator++() noexcept {
48 for(pos += offset; pos != last && !it[pos]; pos += offset) {}
52 constexpr edge_iterator operator++(
int)
noexcept {
53 edge_iterator orig = *
this;
54 return ++(*this), orig;
57 [[nodiscard]]
constexpr reference operator*() const noexcept {
61 [[nodiscard]]
constexpr pointer operator->() const noexcept {
62 return std::make_pair<size_type>(pos / vert, pos % vert);
65 template<
typename Type>
66 friend constexpr bool operator==(
const edge_iterator<Type> &,
const edge_iterator<Type> &)
noexcept;
76template<
typename Container>
77[[nodiscard]]
inline constexpr bool operator==(
const edge_iterator<Container> &lhs,
const edge_iterator<Container> &rhs)
noexcept {
78 return lhs.pos == rhs.pos;
81template<
typename Container>
82[[nodiscard]]
inline constexpr bool operator!=(
const edge_iterator<Container> &lhs,
const edge_iterator<Container> &rhs)
noexcept {
94template<
typename Category,
typename Allocator>
96 using alloc_traits = std::allocator_traits<Allocator>;
97 static_assert(std::is_base_of_v<directed_tag, Category>,
"Invalid graph category");
98 static_assert(std::is_same_v<typename alloc_traits::value_type, std::size_t>,
"Invalid value type");
99 using container_type = std::vector<std::size_t, typename alloc_traits::template rebind_alloc<std::size_t>>;
113 using edge_iterator = internal::edge_iterator<typename container_type::const_iterator>;
155 : matrix{other.matrix, allocator},
171 : matrix{std::move(other.matrix), allocator},
172 vert{std::exchange(other.vert, 0u)} {}
180 matrix = other.matrix;
191 matrix = std::move(other.matrix);
192 vert = std::exchange(other.vert, 0u);
201 return matrix.get_allocator();
216 swap(matrix, other.matrix);
217 swap(vert, other.vert);
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 & operator=(const adjacency_matrix &other)
Default copy assignment operator.
adjacency_matrix() noexcept(noexcept(allocator_type{}))
Default constructor.
Category graph_category
Graph category tag.
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.
size_type size() const noexcept
Returns the number of vertices.
void swap(adjacency_matrix &other)
Exchanges the contents with those of a given adjacency matrix.
adjacency_matrix(adjacency_matrix &&other, const allocator_type &allocator)
Allocator-extended move constructor.
std::size_t size_type
Unsigned integer type.
Allocator allocator_type
Allocator type.
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.
iterable_adaptor< vertex_iterator > vertices() const noexcept
Returns an iterable object to visit all vertices of a matrix.
iterable_adaptor< edge_iterator > edges() const noexcept
Returns an iterable object to visit all edges of a matrix.
adjacency_matrix(const adjacency_matrix &other)
Copy constructor.
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 & operator=(adjacency_matrix &&other) noexcept
Default move assignment operator.
adjacency_matrix(const adjacency_matrix &other, const allocator_type &allocator)
Allocator-extended copy constructor.
adjacency_matrix(adjacency_matrix &&other) noexcept
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.