16 #ifndef IOX_UTILS_GRAPHS_DIRECTED_GRAPH_HPP
17 #define IOX_UTILS_GRAPHS_DIRECTED_GRAPH_HPP
19 #include "iceoryx_utils/cxx/vector.hpp"
27 template <
typename VertexType,
int32_t VERTEX_LIMIT,
int32_t DEGREE_LIMIT>
31 using Index_t = int32_t;
34 static constexpr Index_t INVALID_INDEX = -1;
49 if (findVertex(vertex) >= 0)
55 m_vertices.emplace_back(std::move(data));
64 virtual bool addEdge(VertexType* fromVertex, VertexType* toVertex)
66 auto from = findVertex(fromVertex);
67 auto to = findVertex(toVertex);
68 if (from < 0 || to < 0 || from == to)
75 if (
static_cast<size_t>(fromData.successorIndices.
size()) >= DEGREE_LIMIT
76 ||
static_cast<size_t>(toData.predecessorIndices.
size()) >= DEGREE_LIMIT)
99 return findVertex(vertex);
125 return &m_vertices[index].successors;
137 return &m_vertices[index].predecessors;
148 for (
auto& vertexData : m_vertices)
150 if (vertexData.predecessors.size() == 0u)
163 for (
auto& vertexData : m_vertices)
165 if (vertexData.successors.size() == 0)
178 auto index = findVertex(vertex);
181 if (m_vertices[index].predecessors.size() == 0)
194 auto index = findVertex(vertex);
197 if (m_vertices[index].successors.size() == 0)
210 return m_vertices.size();
240 size_t m_numEdges{0};
244 Index_t findVertex(VertexType
const* vertex)
const
248 Index_t n =
static_cast<Index_t
>(m_vertices.
size());
249 for (Index_t i = 0; i < n; ++i)
251 const auto& compareVertex = m_vertices[i].vertex;
252 if (vertex == compareVertex)
257 return INVALID_INDEX;
260 bool isValid(Index_t index)
262 return index >= 0 && index < static_cast<Index_t>(m_vertices.
size());
Definition: directed_graph.hpp:29
bool addVertex(VertexType *vertex)
Definition: directed_graph.hpp:42
Index_t getIndex(VertexType const *vertex)
Definition: directed_graph.hpp:97
const AdjacencyList * getSuccessors(VertexType const *vertex)
Definition: directed_graph.hpp:105
virtual bool addEdge(VertexType *fromVertex, VertexType *toVertex)
Definition: directed_graph.hpp:64
bool isSource(VertexType const *vertex)
Definition: directed_graph.hpp:176
iox::cxx::vector< VertexType *, VERTEX_LIMIT > getSinks()
Definition: directed_graph.hpp:160
size_t numberOfVertices()
Definition: directed_graph.hpp:208
const AdjacencyList * getPredecessors(VertexType const *vertex)
Definition: directed_graph.hpp:113
const AdjacencyList * getPredecessors(Index_t index)
Definition: directed_graph.hpp:133
size_t numberOfEdges()
Definition: directed_graph.hpp:215
iox::cxx::vector< VertexType *, VERTEX_LIMIT > getSources()
Definition: directed_graph.hpp:145
bool isSink(VertexType const *vertex)
Definition: directed_graph.hpp:192
const AdjacencyList * getSuccessors(Index_t index)
Definition: directed_graph.hpp:121
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
uint64_t size() const noexcept
returns the number of elements which are currently stored in the vector
Definition: vector.inl:145
Definition: directed_graph.hpp:224