iceoryx_doc  1.0.1
directed_acyclic_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_ACYCLIC_GRAPH_HPP
17 #define IOX_UTILS_GRAPHS_DIRECTED_ACYCLIC_GRAPH_HPP
18 
19 #include "iceoryx_utils/internal/cxx/set.hpp"
20 #include "iceoryx_utils/internal/graphs/directed_graph.hpp"
21 #include <cassert>
22 
23 #include <cstdint>
24 
28 template <typename VertexType, int32_t VERTEX_LIMIT, int32_t DEGREE_LIMIT>
29 class DirectedAcyclicGraph : public DirectedGraph<VertexType, VERTEX_LIMIT, DEGREE_LIMIT>
30 {
31  private:
33 
34  public:
35  using Index_t = typename base_type::Index_t;
36 
38  {
39  init();
40  }
41 
47  virtual bool addEdge(VertexType* fromVertex, VertexType* toVertex)
48  {
49  auto from = this->findVertex(fromVertex);
50  auto to = this->findVertex(toVertex);
51  if (from < 0 || to < 0 || from == to)
52  {
53  return false; // need to add vertices first or there would be a self loop
54  }
55 
56  if (createsCycle(from, to))
57  {
58  return false; // new edge would create a cycle, do not add it
59  }
60 
61  if (base_type::addEdge(fromVertex, toVertex))
62  {
63  updateConnectivity(from, to);
64  return true;
65  }
66 
67  return false;
68  }
69 
70  private:
76  // max of int32) the cast will change the value
78 
79  // contains for each vertex index the indices of the vertices it can be reached from
81 
82  // contains for each vertex index the indices of vertices that can be reached from it
84 
85  // check whether the graph where we add an edge between from and to would be cyclic
86  bool createsCycle(const Index_t from, const Index_t to)
87  {
88  // if there is already is a path from the to-vertex to the from-vertex
89  // adding an edge from the from-vertex to the to-vertex would create a cycle
90  if (iox::cxx::set::hasElement(m_leadsTo[to], from))
91  {
92  return true;
93  }
94  return false;
95  }
96 
97  // update the connectivity data (m_reachableFrom and m_leadsTo) when we add an edge between from and to
98  // note that this is quite expensive for large graphs, but we do not expect large graphs
99  // also note that this cannot easily be avoided in general, e.g. depth first search would be
100  // even more costly
101  void updateConnectivity(const Index_t from, const Index_t to)
102  {
103  // update predecessors of to-vertex
104  // (due to the new edge it can now be reached by every vertex with a path to the from-vertex)
105  auto& inTo = m_reachableFrom[to];
106  iox::cxx::set::add(inTo, from);
107  iox::cxx::set::unify(inTo, m_reachableFrom[from]);
108 
109  // update successors of from-vertex
110  // (due to the new edge we can now reach every vertex that can be reached by the from-vertex)
111  auto& outFrom = m_leadsTo[from];
112  iox::cxx::set::add(outFrom, to);
113  iox::cxx::set::unify(outFrom, m_leadsTo[to]);
114 
115  // update every predecessor of from-vertex
116  //(from them we can reach every vertex that can be reached from the to-vertex )
117  for (auto pred : m_reachableFrom[from])
118  {
119  iox::cxx::set::unify(m_leadsTo[pred], outFrom);
120  }
121 
122  // update every successor of to-vertex
123  //(they can now be reached from every predecessor of from-vertex )
124  auto& inFrom = m_reachableFrom[from];
125  for (auto succ : m_leadsTo[to])
126  {
127  iox::cxx::set::unify(m_reachableFrom[succ], inFrom);
128  }
129  }
130 
131  void init()
132  {
133  bool stat = true;
134  // as a small optimization we could defer the
135  // initialization to the time the vertex is actually added
136  for (decltype(VERTEX_LIMIT) i = 0; i < VERTEX_LIMIT; ++i)
137  {
138  stat &= m_reachableFrom.emplace_back(IndexSet());
139  stat &= m_leadsTo.emplace_back(IndexSet());
140  }
141  assert(stat);
142  }
143 };
144 
145 #endif // IOX_UTILS_GRAPHS_DIRECTED_ACYCLIC_GRAPH_HPP
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