16 #ifndef IOX_UTILS_GRAPHS_DIRECTED_ACYCLIC_GRAPH_HPP
17 #define IOX_UTILS_GRAPHS_DIRECTED_ACYCLIC_GRAPH_HPP
19 #include "iceoryx_utils/internal/cxx/set.hpp"
20 #include "iceoryx_utils/internal/graphs/directed_graph.hpp"
28 template <
typename VertexType,
int32_t VERTEX_LIMIT,
int32_t DEGREE_LIMIT>
35 using Index_t =
typename base_type::Index_t;
47 virtual bool addEdge(VertexType* fromVertex, VertexType* toVertex)
49 auto from = this->findVertex(fromVertex);
50 auto to = this->findVertex(toVertex);
51 if (from < 0 || to < 0 || from == to)
56 if (createsCycle(from, to))
63 updateConnectivity(from, to);
86 bool createsCycle(
const Index_t from,
const Index_t to)
90 if (iox::cxx::set::hasElement(m_leadsTo[to], from))
101 void updateConnectivity(
const Index_t from,
const Index_t to)
105 auto& inTo = m_reachableFrom[to];
106 iox::cxx::set::add(inTo, from);
107 iox::cxx::set::unify(inTo, m_reachableFrom[from]);
111 auto& outFrom = m_leadsTo[from];
112 iox::cxx::set::add(outFrom, to);
113 iox::cxx::set::unify(outFrom, m_leadsTo[to]);
117 for (
auto pred : m_reachableFrom[from])
119 iox::cxx::set::unify(m_leadsTo[pred], outFrom);
124 auto& inFrom = m_reachableFrom[from];
125 for (
auto succ : m_leadsTo[to])
127 iox::cxx::set::unify(m_reachableFrom[succ], inFrom);
136 for (decltype(VERTEX_LIMIT) i = 0; i < VERTEX_LIMIT; ++i)
Definition: directed_acyclic_graph.hpp:30
virtual bool addEdge(VertexType *fromVertex, VertexType *toVertex)
Definition: directed_acyclic_graph.hpp:47
Definition: directed_graph.hpp:29
virtual bool addEdge(VertexType *fromVertex, VertexType *toVertex)
Definition: directed_graph.hpp:64
C++11 compatible vector implementation. We needed to do some adjustments in the API since we do not u...
Definition: vector.hpp:34
bool emplace_back(Targs &&... args) noexcept
forwards all arguments to the constructor of the contained element and performs a placement new at th...
Definition: vector.inl:166