1 #ifndef DYNAMICGRAPH_HPP 2 #define DYNAMICGRAPH_HPP 3 4 #include "util/deallocating_vector.hpp" 5 #include "util/exception.hpp" 6 #include "util/exception_utils.hpp" 7 #include "util/integer_range.hpp" 8 #include "util/permutation.hpp" 9 #include "util/typedefs.hpp" 10 11 #include <boost/assert.hpp> 12 13 #include <cstdint> 14 15 #include <algorithm> 16 #include <atomic> 17 #include <limits> 18 #include <tuple> 19 #include <vector> 20 21 namespace osrm 22 { 23 namespace util 24 { 25 namespace detail 26 { 27 // These types need to live outside of DynamicGraph 28 // to be not dependable. We need this for transforming graphs 29 // with different data. 30 31 template <typename EdgeIterator> struct DynamicNode 32 { 33 // index of the first edge 34 EdgeIterator first_edge; 35 // amount of edges 36 unsigned edges; 37 }; 38 39 template <typename NodeIterator, typename EdgeDataT> struct DynamicEdge 40 { 41 NodeIterator target; 42 EdgeDataT data; 43 }; 44 } // namespace detail 45 46 template <typename EdgeDataT> class DynamicGraph 47 { 48 public: 49 using EdgeData = EdgeDataT; 50 using NodeIterator = std::uint32_t; 51 using EdgeIterator = std::uint32_t; 52 using EdgeRange = range<EdgeIterator>; 53 54 using Node = detail::DynamicNode<EdgeIterator>; 55 using Edge = detail::DynamicEdge<NodeIterator, EdgeDataT>; 56 57 template <typename E> friend class DynamicGraph; 58 59 class InputEdge 60 { 61 public: 62 NodeIterator source; 63 NodeIterator target; 64 EdgeDataT data; 65 InputEdge()66 InputEdge() 67 : source(std::numeric_limits<NodeIterator>::max()), 68 target(std::numeric_limits<NodeIterator>::max()) 69 { 70 } 71 72 template <typename... Ts> InputEdge(NodeIterator source,NodeIterator target,Ts &&...data)73 InputEdge(NodeIterator source, NodeIterator target, Ts &&... data) 74 : source(source), target(target), data(std::forward<Ts>(data)...) 75 { 76 } 77 operator <(const InputEdge & rhs) const78 bool operator<(const InputEdge &rhs) const 79 { 80 return std::tie(source, target) < std::tie(rhs.source, rhs.target); 81 } 82 }; 83 DynamicGraph()84 DynamicGraph() : DynamicGraph(0) {} 85 86 // Constructs an empty graph with a given number of nodes. DynamicGraph(NodeIterator nodes)87 explicit DynamicGraph(NodeIterator nodes) : number_of_nodes(nodes), number_of_edges(0) 88 { 89 node_array.reserve(number_of_nodes); 90 node_array.resize(number_of_nodes); 91 92 edge_list.reserve(number_of_nodes * 1.1); 93 edge_list.resize(number_of_nodes); 94 } 95 96 /** 97 * Constructs a DynamicGraph from a list of edges sorted by source node id. 98 */ DynamicGraph(const NodeIterator nodes,const ContainerT & graph)99 template <class ContainerT> DynamicGraph(const NodeIterator nodes, const ContainerT &graph) 100 { 101 // we need to cast here because DeallocatingVector does not have a valid const iterator 102 BOOST_ASSERT(std::is_sorted(const_cast<ContainerT &>(graph).begin(), 103 const_cast<ContainerT &>(graph).end())); 104 105 number_of_nodes = nodes; 106 number_of_edges = static_cast<EdgeIterator>(graph.size()); 107 node_array.resize(number_of_nodes); 108 EdgeIterator edge = 0; 109 EdgeIterator position = 0; 110 for (const auto node : irange(0u, number_of_nodes)) 111 { 112 EdgeIterator last_edge = edge; 113 while (edge < number_of_edges && graph[edge].source == node) 114 { 115 ++edge; 116 } 117 node_array[node].first_edge = position; 118 node_array[node].edges = edge - last_edge; 119 position += node_array[node].edges; 120 } 121 edge_list.reserve(static_cast<std::size_t>(edge_list.size() * 1.1)); 122 edge_list.resize(position); 123 edge = 0; 124 for (const auto node : irange(0u, number_of_nodes)) 125 { 126 for (const auto i : irange(node_array[node].first_edge, 127 node_array[node].first_edge + node_array[node].edges)) 128 { 129 edge_list[i].target = graph[edge].target; 130 BOOST_ASSERT(edge_list[i].target < number_of_nodes); 131 edge_list[i].data = graph[edge].data; 132 ++edge; 133 } 134 } 135 136 BOOST_ASSERT(node_array.size() == number_of_nodes); 137 } 138 139 // Copy&move for the same data 140 // 141 DynamicGraph(const DynamicGraph & other)142 DynamicGraph(const DynamicGraph &other) 143 { 144 number_of_nodes = other.number_of_nodes; 145 // atomics can't be moved this is why we need an own constructor 146 number_of_edges = static_cast<std::uint32_t>(other.number_of_edges); 147 148 node_array = other.node_array; 149 edge_list = other.edge_list; 150 } 151 operator =(const DynamicGraph & other)152 DynamicGraph &operator=(const DynamicGraph &other) 153 { 154 auto copy_other = other; 155 *this = std::move(other); 156 return *this; 157 } 158 DynamicGraph(DynamicGraph && other)159 DynamicGraph(DynamicGraph &&other) 160 { 161 number_of_nodes = other.number_of_nodes; 162 // atomics can't be moved this is why we need an own constructor 163 number_of_edges = static_cast<std::uint32_t>(other.number_of_edges); 164 165 node_array = std::move(other.node_array); 166 edge_list = std::move(other.edge_list); 167 } 168 operator =(DynamicGraph && other)169 DynamicGraph &operator=(DynamicGraph &&other) 170 { 171 number_of_nodes = other.number_of_nodes; 172 // atomics can't be moved this is why we need an own constructor 173 number_of_edges = static_cast<std::uint32_t>(other.number_of_edges); 174 175 node_array = std::move(other.node_array); 176 edge_list = std::move(other.edge_list); 177 178 return *this; 179 } 180 181 // Removes all edges to and from nodes for which filter(node_id) returns false Filter(Pred filter) const182 template <typename Pred> auto Filter(Pred filter) const & 183 { 184 BOOST_ASSERT(node_array.size() == number_of_nodes); 185 186 DynamicGraph other; 187 188 other.number_of_nodes = number_of_nodes; 189 other.number_of_edges = static_cast<std::uint32_t>(number_of_edges); 190 other.edge_list.reserve(edge_list.size()); 191 other.node_array.resize(node_array.size()); 192 193 NodeID node_id = 0; 194 std::transform( 195 node_array.begin(), node_array.end(), other.node_array.begin(), [&](const Node &node) { 196 const EdgeIterator first_edge = other.edge_list.size(); 197 198 BOOST_ASSERT(node_id < number_of_nodes); 199 if (filter(node_id++)) 200 { 201 std::copy_if(edge_list.begin() + node.first_edge, 202 edge_list.begin() + node.first_edge + node.edges, 203 std::back_inserter(other.edge_list), 204 [&](const auto &edge) { return filter(edge.target); }); 205 const unsigned num_edges = other.edge_list.size() - first_edge; 206 return Node{first_edge, num_edges}; 207 } 208 else 209 { 210 return Node{first_edge, 0}; 211 } 212 }); 213 214 return other; 215 } 216 GetNumberOfNodes() const217 unsigned GetNumberOfNodes() const { return number_of_nodes; } 218 GetNumberOfEdges() const219 unsigned GetNumberOfEdges() const { return number_of_edges; } GetEdgeCapacity() const220 auto GetEdgeCapacity() const { return edge_list.size(); } 221 GetOutDegree(const NodeIterator n) const222 unsigned GetOutDegree(const NodeIterator n) const { return node_array[n].edges; } 223 GetDirectedOutDegree(const NodeIterator n) const224 unsigned GetDirectedOutDegree(const NodeIterator n) const 225 { 226 unsigned degree = 0; 227 for (const auto edge : irange(BeginEdges(n), EndEdges(n))) 228 { 229 if (!GetEdgeData(edge).reversed) 230 { 231 ++degree; 232 } 233 } 234 return degree; 235 } 236 GetTarget(const EdgeIterator e) const237 NodeIterator GetTarget(const EdgeIterator e) const { return NodeIterator(edge_list[e].target); } 238 SetTarget(const EdgeIterator e,const NodeIterator n)239 void SetTarget(const EdgeIterator e, const NodeIterator n) { edge_list[e].target = n; } 240 GetEdgeData(const EdgeIterator e)241 EdgeDataT &GetEdgeData(const EdgeIterator e) { return edge_list[e].data; } 242 GetEdgeData(const EdgeIterator e) const243 const EdgeDataT &GetEdgeData(const EdgeIterator e) const { return edge_list[e].data; } 244 BeginEdges(const NodeIterator n) const245 EdgeIterator BeginEdges(const NodeIterator n) const 246 { 247 return EdgeIterator(node_array[n].first_edge); 248 } 249 EndEdges(const NodeIterator n) const250 EdgeIterator EndEdges(const NodeIterator n) const 251 { 252 return EdgeIterator(node_array[n].first_edge + node_array[n].edges); 253 } 254 GetAdjacentEdgeRange(const NodeIterator node) const255 EdgeRange GetAdjacentEdgeRange(const NodeIterator node) const 256 { 257 return irange(BeginEdges(node), EndEdges(node)); 258 } 259 InsertNode()260 NodeIterator InsertNode() 261 { 262 node_array.emplace_back(node_array.back()); 263 number_of_nodes += 1; 264 265 return number_of_nodes; 266 } 267 268 // adds an edge. Invalidates edge iterators for the source node InsertEdge(const NodeIterator from,const NodeIterator to,const EdgeDataT & data)269 EdgeIterator InsertEdge(const NodeIterator from, const NodeIterator to, const EdgeDataT &data) 270 { 271 Node &node = node_array[from]; 272 EdgeIterator one_beyond_last_of_node = node.edges + node.first_edge; 273 // if we can't write at the end of this nodes edges 274 // that is: the end is the end of the edge_list, 275 // or the beginning of the next nodes edges 276 if (one_beyond_last_of_node == edge_list.size() || !isDummy(one_beyond_last_of_node)) 277 { 278 // can we write before this nodes edges? 279 if (node.first_edge != 0 && isDummy(node.first_edge - 1)) 280 { 281 node.first_edge--; 282 edge_list[node.first_edge] = edge_list[node.first_edge + node.edges]; 283 } 284 else 285 { 286 // we have to move this nodes edges to the end of the edge_list 287 EdgeIterator newFirstEdge = (EdgeIterator)edge_list.size(); 288 unsigned newSize = node.edges * 1.1 + 2; 289 EdgeIterator requiredCapacity = newSize + edge_list.size(); 290 EdgeIterator oldCapacity = edge_list.capacity(); 291 // make sure there is enough space at the end 292 if (requiredCapacity >= oldCapacity) 293 { 294 edge_list.reserve(requiredCapacity * 1.1); 295 } 296 edge_list.resize(edge_list.size() + newSize); 297 // move the edges over and invalidate the old ones 298 for (const auto i : irange(0u, node.edges)) 299 { 300 edge_list[newFirstEdge + i] = edge_list[node.first_edge + i]; 301 makeDummy(node.first_edge + i); 302 } 303 // invalidate until the end of edge_list 304 for (const auto i : irange(node.edges + 1, newSize)) 305 { 306 makeDummy(newFirstEdge + i); 307 } 308 node.first_edge = newFirstEdge; 309 } 310 } 311 // get the position for the edge that is to be inserted 312 // and write it 313 Edge &edge = edge_list[node.first_edge + node.edges]; 314 edge.target = to; 315 edge.data = data; 316 ++number_of_edges; 317 ++node.edges; 318 return EdgeIterator(node.first_edge + node.edges); 319 } 320 321 // removes an edge. Invalidates edge iterators for the source node DeleteEdge(const NodeIterator source,const EdgeIterator e)322 void DeleteEdge(const NodeIterator source, const EdgeIterator e) 323 { 324 Node &node = node_array[source]; 325 --number_of_edges; 326 --node.edges; 327 BOOST_ASSERT(std::numeric_limits<unsigned>::max() != node.edges); 328 const unsigned last = node.first_edge + node.edges; 329 BOOST_ASSERT(std::numeric_limits<unsigned>::max() != last); 330 // swap with last edge 331 edge_list[e] = edge_list[last]; 332 makeDummy(last); 333 } 334 335 // removes all edges (source,target) DeleteEdgesTo(const NodeIterator source,const NodeIterator target)336 int32_t DeleteEdgesTo(const NodeIterator source, const NodeIterator target) 337 { 338 int32_t deleted = 0; 339 for (EdgeIterator i = BeginEdges(source), iend = EndEdges(source); i < iend - deleted; ++i) 340 { 341 if (edge_list[i].target == target) 342 { 343 do 344 { 345 deleted++; 346 edge_list[i] = edge_list[iend - deleted]; 347 makeDummy(iend - deleted); 348 } while (i < iend - deleted && edge_list[i].target == target); 349 } 350 } 351 352 number_of_edges -= deleted; 353 node_array[source].edges -= deleted; 354 355 return deleted; 356 } 357 358 // searches for a specific edge FindEdge(const NodeIterator from,const NodeIterator to) const359 EdgeIterator FindEdge(const NodeIterator from, const NodeIterator to) const 360 { 361 for (const auto i : irange(BeginEdges(from), EndEdges(from))) 362 { 363 if (to == edge_list[i].target) 364 { 365 return i; 366 } 367 } 368 return SPECIAL_EDGEID; 369 } 370 371 // searches for a specific edge FindSmallestEdge(const NodeIterator from,const NodeIterator to) const372 EdgeIterator FindSmallestEdge(const NodeIterator from, const NodeIterator to) const 373 { 374 EdgeIterator smallest_edge = SPECIAL_EDGEID; 375 EdgeWeight smallest_weight = INVALID_EDGE_WEIGHT; 376 for (auto edge : GetAdjacentEdgeRange(from)) 377 { 378 const NodeID target = GetTarget(edge); 379 const EdgeWeight weight = GetEdgeData(edge).distance; 380 if (target == to && weight < smallest_weight) 381 { 382 smallest_edge = edge; 383 smallest_weight = weight; 384 } 385 } 386 return smallest_edge; 387 } 388 FindEdgeInEitherDirection(const NodeIterator from,const NodeIterator to) const389 EdgeIterator FindEdgeInEitherDirection(const NodeIterator from, const NodeIterator to) const 390 { 391 EdgeIterator tmp = FindEdge(from, to); 392 return (SPECIAL_NODEID != tmp ? tmp : FindEdge(to, from)); 393 } 394 395 EdgeIterator FindEdgeIndicateIfReverse(const NodeIterator from,const NodeIterator to,bool & result) const396 FindEdgeIndicateIfReverse(const NodeIterator from, const NodeIterator to, bool &result) const 397 { 398 EdgeIterator current_iterator = FindEdge(from, to); 399 if (SPECIAL_NODEID == current_iterator) 400 { 401 current_iterator = FindEdge(to, from); 402 if (SPECIAL_NODEID != current_iterator) 403 { 404 result = true; 405 } 406 } 407 return current_iterator; 408 } 409 Renumber(const std::vector<NodeID> & old_to_new_node)410 void Renumber(const std::vector<NodeID> &old_to_new_node) 411 { 412 // permutate everything but the sentinel 413 util::inplacePermutation(node_array.begin(), node_array.end(), old_to_new_node); 414 415 // Build up edge permutation 416 if (edge_list.size() >= std::numeric_limits<EdgeID>::max()) 417 { 418 throw util::exception("There are too many edges, OSRM only supports 2^32" + SOURCE_REF); 419 } 420 421 EdgeID new_edge_index = 0; 422 std::vector<EdgeID> old_to_new_edge(edge_list.size(), SPECIAL_EDGEID); 423 for (auto node : util::irange<NodeID>(0, number_of_nodes)) 424 { 425 auto new_first_edge = new_edge_index; 426 // move all filled edges 427 for (auto edge : GetAdjacentEdgeRange(node)) 428 { 429 edge_list[edge].target = old_to_new_node[edge_list[edge].target]; 430 BOOST_ASSERT(edge_list[edge].target != SPECIAL_NODEID); 431 old_to_new_edge[edge] = new_edge_index++; 432 } 433 node_array[node].first_edge = new_first_edge; 434 } 435 auto number_of_valid_edges = new_edge_index; 436 437 // move all dummy edges to the end of the renumbered range 438 for (auto edge : util::irange<NodeID>(0, edge_list.size())) 439 { 440 if (old_to_new_edge[edge] == SPECIAL_EDGEID) 441 { 442 BOOST_ASSERT(isDummy(edge)); 443 old_to_new_edge[edge] = new_edge_index++; 444 } 445 } 446 BOOST_ASSERT(std::find(old_to_new_edge.begin(), old_to_new_edge.end(), SPECIAL_EDGEID) == 447 old_to_new_edge.end()); 448 util::inplacePermutation(edge_list.begin(), edge_list.end(), old_to_new_edge); 449 // Remove useless dummy nodes at the end 450 edge_list.resize(number_of_valid_edges); 451 number_of_edges = number_of_valid_edges; 452 } 453 454 protected: isDummy(const EdgeIterator edge) const455 bool isDummy(const EdgeIterator edge) const 456 { 457 return edge_list[edge].target == (std::numeric_limits<NodeIterator>::max)(); 458 } 459 makeDummy(const EdgeIterator edge)460 void makeDummy(const EdgeIterator edge) 461 { 462 edge_list[edge].target = (std::numeric_limits<NodeIterator>::max)(); 463 } 464 465 NodeIterator number_of_nodes; 466 std::atomic_uint number_of_edges; 467 468 std::vector<Node> node_array; 469 DeallocatingVector<Edge> edge_list; 470 }; 471 } // namespace util 472 } // namespace osrm 473 474 #endif // DYNAMICGRAPH_HPP 475