1#ifndef ENTT_GRAPH_FLOW_HPP
2#define ENTT_GRAPH_FLOW_HPP
12#include "../config/config.h"
13#include "../container/dense_map.hpp"
14#include "../container/dense_set.hpp"
15#include "../core/compressed_pair.hpp"
16#include "../core/fwd.hpp"
17#include "../core/iterator.hpp"
18#include "../core/utility.hpp"
19#include "adjacency_matrix.hpp"
28template<
typename Allocator>
30 using alloc_traits = std::allocator_traits<Allocator>;
31 static_assert(std::is_same_v<typename alloc_traits::value_type, id_type>,
"Invalid value type");
33 using ro_rw_container_type = std::vector<std::pair<std::size_t, bool>,
typename alloc_traits::template rebind_alloc<std::pair<std::size_t, bool>>>;
37 void emplace(
const id_type res,
const bool is_rw) {
38 ENTT_ASSERT(index.first() < vertices.size(),
"Invalid node");
40 if(!deps.contains(res) && sync_on != vertices.size()) {
41 deps[res].emplace_back(sync_on,
true);
44 deps[res].emplace_back(index.first(), is_rw);
47 void setup_graph(adjacency_matrix_type &matrix)
const {
48 for(
const auto &elem: deps) {
49 const auto last = elem.second.cend();
50 auto it = elem.second.cbegin();
55 if(
auto curr = it++; it != last) {
57 matrix.
insert(curr->first, it->first);
58 }
else if(
const auto next = std::find_if(it, last, [](
const auto &value) {
return value.second; }); next != last) {
59 for(; it != next; ++it) {
60 matrix.
insert(curr->first, it->first);
61 matrix.
insert(it->first, next->first);
64 for(; it != next; ++it) {
65 matrix.
insert(curr->first, it->first);
71 if(
const auto next = std::find_if(it, last, [](
const auto &value) {
return value.second; }); next != last) {
72 for(; it != next; ++it) {
73 matrix.
insert(it->first, next->first);
83 void transitive_closure(adjacency_matrix_type &matrix)
const {
84 const auto length = matrix.
size();
86 for(std::size_t vk{}; vk < length; ++vk) {
87 for(std::size_t vi{}; vi < length; ++vi) {
88 for(std::size_t vj{}; vj < length; ++vj) {
97 void transitive_reduction(adjacency_matrix_type &matrix)
const {
98 const auto length = matrix.
size();
100 for(std::size_t vert{}; vert < length; ++vert) {
101 matrix.
erase(vert, vert);
104 for(std::size_t vj{}; vj < length; ++vj) {
105 for(std::size_t vi{}; vi < length; ++vi) {
107 for(std::size_t vk{}; vk < length; ++vk) {
109 matrix.
erase(vi, vk);
136 : index{0u, allocator},
149 : index{other.index.first(), allocator},
150 vertices{other.vertices, allocator},
151 deps{other.deps, allocator},
152 sync_on{other.sync_on} {}
163 : index{other.index.first(), allocator},
164 vertices{std::move(other.vertices), allocator},
165 deps{std::move(other.deps), allocator},
166 sync_on{other.sync_on} {}
189 std::swap(index, other.index);
190 std::swap(vertices, other.vertices);
191 std::swap(deps, other.deps);
192 std::swap(sync_on, other.sync_on);
224 [[nodiscard]]
bool empty() const noexcept {
225 return vertices.empty();
233 return vertices.size();
242 sync_on += (sync_on == vertices.size());
243 const auto it = vertices.emplace(value).first;
244 index.first() =
size_type(it - vertices.begin());
253 ENTT_ASSERT(index.first() < vertices.size(),
"Invalid node");
254 sync_on = index.first();
256 for(
const auto &elem: deps) {
257 elem.second.emplace_back(sync_on,
true);
291 template<
typename It>
292 std::enable_if_t<std::is_same_v<std::remove_const_t<typename std::iterator_traits<It>::value_type>,
id_type>,
basic_flow &>
293 ro(It first, It last) {
294 for(; first != last; ++first) {
295 emplace(*first,
false);
318 template<
typename It>
319 std::enable_if_t<std::is_same_v<std::remove_const_t<typename std::iterator_traits<It>::value_type>,
id_type>,
basic_flow &>
320 rw(It first, It last) {
321 for(; first != last; ++first) {
322 emplace(*first,
true);
336 transitive_closure(matrix);
337 transitive_reduction(matrix);
344 task_container_type vertices;
345 deps_container_type deps;
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.
size_type size() const noexcept
Returns the number of vertices.
bool contains(const vertex_type lhs, const vertex_type rhs) const
Checks if an adjacency matrix contains a given edge.
size_type erase(const vertex_type lhs, const vertex_type rhs)
Removes the edge associated with a pair of given vertices.
Utility class for creating task graphs.
void clear() noexcept
Clears the flow builder.
id_type operator[](const size_type pos) const
Returns the identifier at specified location.
Allocator allocator_type
Allocator type.
size_type size() const noexcept
Returns the number of tasks.
iterable_adaptor< typename task_container_type::const_iterator > iterable
Iterable task list.
std::size_t size_type
Unsigned integer type.
basic_flow & sync()
Turns the current task into a sync point.
basic_flow & rw(const id_type res)
Assigns a writable resource to the current task.
std::enable_if_t< std::is_same_v< std::remove_const_t< typename std::iterator_traits< It >::value_type >, id_type >, basic_flow & > rw(It first, It last)
Assigns a range of writable resources to the current task.
constexpr allocator_type get_allocator() const noexcept
Returns the associated allocator.
graph_type graph() const
Generates a task graph for the current content.
basic_flow(const allocator_type &allocator)
Constructs a flow builder with a given allocator.
adjacency_matrix_type graph_type
Adjacency matrix type.
~basic_flow()=default
Default destructor.
basic_flow & ro(const id_type res)
Assigns a read-only resource to the current task.
basic_flow(basic_flow &&) noexcept=default
Default move constructor.
basic_flow & bind(const id_type value)
Binds a task to a flow builder.
basic_flow & set(const id_type res, bool is_rw=false)
Assigns a resource to the current task with a given access mode.
basic_flow & operator=(basic_flow &&) noexcept=default
Default move assignment operator.
basic_flow()
Default constructor.
basic_flow(const basic_flow &other, const allocator_type &allocator)
Allocator-extended copy constructor.
void swap(basic_flow &other) noexcept
bool empty() const noexcept
Returns true if a flow builder contains no tasks, false otherwise.
std::enable_if_t< std::is_same_v< std::remove_const_t< typename std::iterator_traits< It >::value_type >, id_type >, basic_flow & > ro(It first, It last)
Assigns a range of read-only resources to the current task.
basic_flow & operator=(const basic_flow &)=default
Default copy assignment operator.
basic_flow(const basic_flow &)=default
Default copy constructor.
Associative container for key-value pairs with unique keys.
Associative container for unique objects of a given type.
std::ptrdiff_t difference_type
std::uint32_t id_type
Alias declaration for type identifiers.
Utility class to create an iterable object from a pair of iterators.