iceoryx_doc  1.0.1
directed_graph.hpp
1 // Copyright (c) 2019 by Robert Bosch GmbH. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // SPDX-License-Identifier: Apache-2.0
16 #ifndef IOX_UTILS_GRAPHS_DIRECTED_GRAPH_HPP
17 #define IOX_UTILS_GRAPHS_DIRECTED_GRAPH_HPP
18 
19 #include "iceoryx_utils/cxx/vector.hpp"
20 
21 #include <cstdint>
22 #include <limits>
23 
25 // remark: only supports adding but no removal of vertices or edges
26 // and this graph is not necessarily acyclic
27 template <typename VertexType, int32_t VERTEX_LIMIT, int32_t DEGREE_LIMIT>
29 {
30  public:
31  using Index_t = int32_t;
33 
34  static constexpr Index_t INVALID_INDEX = -1;
35 
36  virtual ~DirectedGraph() = default;
37 
42  bool addVertex(VertexType* vertex)
43  {
44  if (numberOfVertices() >= VERTEX_LIMIT)
45  {
46  return false;
47  }
48 
49  if (findVertex(vertex) >= 0)
50  {
51  return false; // already exists
52  }
53 
54  VertexData data(vertex);
55  m_vertices.emplace_back(std::move(data));
56  return true;
57  }
58 
64  virtual bool addEdge(VertexType* fromVertex, VertexType* toVertex)
65  {
66  auto from = findVertex(fromVertex);
67  auto to = findVertex(toVertex);
68  if (from < 0 || to < 0 || from == to)
69  {
70  return false; // need to add vertices first (could do this here as well)
71  }
72  VertexData& fromData = m_vertices[from];
73  VertexData& toData = m_vertices[to];
74 
75  if (static_cast<size_t>(fromData.successorIndices.size()) >= DEGREE_LIMIT
76  || static_cast<size_t>(toData.predecessorIndices.size()) >= DEGREE_LIMIT)
77  {
78  return false; // degree limit of at least one vertex would be exceeded
79  }
80 
81  // only store indices, value can be found at this index
82  fromData.successorIndices.emplace_back(to);
83  toData.predecessorIndices.emplace_back(from);
84 
85  // add to successor/predecessor lists to return on demand
86  fromData.successors.emplace_back(toVertex);
87  toData.predecessors.emplace_back(fromVertex);
88 
89  ++m_numEdges;
90 
91  return true;
92  }
93 
97  Index_t getIndex(VertexType const* vertex)
98  {
99  return findVertex(vertex);
100  }
101 
105  const AdjacencyList* getSuccessors(VertexType const* vertex)
106  {
107  return getSuccessors(findVertex(vertex));
108  }
109 
113  const AdjacencyList* getPredecessors(VertexType const* vertex)
114  {
115  return getPredecessors(findVertex(vertex));
116  }
117 
121  const AdjacencyList* getSuccessors(Index_t index)
122  {
123  if (index >= 0 && index < static_cast<Index_t>(numberOfVertices()))
124  {
125  return &m_vertices[index].successors;
126  }
127  return nullptr;
128  }
129 
133  const AdjacencyList* getPredecessors(Index_t index)
134  {
135  if (index >= 0 && index < static_cast<Index_t>(numberOfVertices()))
136  {
137  return &m_vertices[index].predecessors;
138  }
139  return nullptr;
140  }
141 
142 
146  {
148  for (auto& vertexData : m_vertices)
149  {
150  if (vertexData.predecessors.size() == 0u)
151  {
152  result.emplace_back(vertexData.vertex);
153  }
154  }
155  return result;
156  }
157 
161  {
163  for (auto& vertexData : m_vertices)
164  {
165  if (vertexData.successors.size() == 0)
166  {
167  result.emplace_back(vertexData.vertex);
168  }
169  }
170  return result;
171  }
172 
176  bool isSource(VertexType const* vertex)
177  {
178  auto index = findVertex(vertex);
179  if (isValid(index))
180  {
181  if (m_vertices[index].predecessors.size() == 0)
182  {
183  return true;
184  }
185  }
186  return false;
187  }
188 
192  bool isSink(VertexType const* vertex)
193  {
194  auto index = findVertex(vertex);
195  if (isValid(index))
196  {
197  if (m_vertices[index].successors.size() == 0)
198  {
199  return true;
200  }
201  }
202  return false;
203  }
204 
205 
209  {
210  return m_vertices.size();
211  }
212 
215  size_t numberOfEdges()
216  {
217  return m_numEdges;
218  }
219 
220  protected:
221  using AdjacencyIndexList = iox::cxx::vector<Index_t, DEGREE_LIMIT>;
222 
223  struct VertexData
224  {
225  explicit VertexData(VertexType* vertex)
226  : vertex(vertex)
227  {
228  }
229 
230  VertexType* vertex;
231 
232  AdjacencyIndexList predecessorIndices; // indices to navigate the graph
233  AdjacencyIndexList successorIndices;
234 
235  AdjacencyList predecessors; // values to provide references externally
236  AdjacencyList successors;
237  };
238 
240  size_t m_numEdges{0};
241 
242  // static assert to check comparison operator?
243  // requires ==operator
244  Index_t findVertex(VertexType const* vertex) const
245  {
246  // linear search for now, could be improved using binary search if we store the vertices sorted
247  // (but would require insertion in the middle)
248  Index_t n = static_cast<Index_t>(m_vertices.size());
249  for (Index_t i = 0; i < n; ++i)
250  {
251  const auto& compareVertex = m_vertices[i].vertex;
252  if (vertex == compareVertex)
253  {
254  return i;
255  }
256  }
257  return INVALID_INDEX; // not found
258  }
259 
260  bool isValid(Index_t index)
261  {
262  return index >= 0 && index < static_cast<Index_t>(m_vertices.size());
263  }
264 };
265 
266 #endif // IOX_UTILS_GRAPHS_DIRECTED_GRAPH_HPP
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