1 #ifndef OSRM_CELLS_CUSTOMIZER_HPP 2 #define OSRM_CELLS_CUSTOMIZER_HPP 3 4 #include "partitioner/cell_storage.hpp" 5 #include "partitioner/multi_level_partition.hpp" 6 #include "util/query_heap.hpp" 7 8 #include <tbb/enumerable_thread_specific.h> 9 #include <tbb/parallel_for.h> 10 11 #include <unordered_set> 12 13 namespace osrm 14 { 15 namespace customizer 16 { 17 18 class CellCustomizer 19 { 20 private: 21 struct HeapData 22 { 23 bool from_clique; 24 EdgeDuration duration; 25 EdgeDistance distance; 26 }; 27 28 public: 29 using Heap = 30 util::QueryHeap<NodeID, NodeID, EdgeWeight, HeapData, util::ArrayStorage<NodeID, int>>; 31 using HeapPtr = tbb::enumerable_thread_specific<Heap>; 32 CellCustomizer(const partitioner::MultiLevelPartition & partition)33 CellCustomizer(const partitioner::MultiLevelPartition &partition) : partition(partition) {} 34 35 template <typename GraphT> Customize(const GraphT & graph,Heap & heap,const partitioner::CellStorage & cells,const std::vector<bool> & allowed_nodes,CellMetric & metric,LevelID level,CellID id) const36 void Customize(const GraphT &graph, 37 Heap &heap, 38 const partitioner::CellStorage &cells, 39 const std::vector<bool> &allowed_nodes, 40 CellMetric &metric, 41 LevelID level, 42 CellID id) const 43 { 44 auto cell = cells.GetCell(metric, level, id); 45 auto destinations = cell.GetDestinationNodes(); 46 47 // for each source do forward search 48 for (auto source : cell.GetSourceNodes()) 49 { 50 if (!allowed_nodes[source]) 51 { 52 continue; 53 } 54 55 std::unordered_set<NodeID> destinations_set; 56 for (const auto destination : destinations) 57 { 58 if (allowed_nodes[destination]) 59 { 60 destinations_set.insert(destination); 61 } 62 } 63 heap.Clear(); 64 heap.Insert(source, 0, {false, 0, 0}); 65 66 // explore search space 67 while (!heap.Empty() && !destinations_set.empty()) 68 { 69 const NodeID node = heap.DeleteMin(); 70 const EdgeWeight weight = heap.GetKey(node); 71 const EdgeDuration duration = heap.GetData(node).duration; 72 const EdgeDistance distance = heap.GetData(node).distance; 73 74 RelaxNode(graph, 75 cells, 76 allowed_nodes, 77 metric, 78 heap, 79 level, 80 node, 81 weight, 82 duration, 83 distance); 84 85 destinations_set.erase(node); 86 } 87 88 // fill a map of destination nodes to placeholder pointers 89 auto weights = cell.GetOutWeight(source); 90 auto durations = cell.GetOutDuration(source); 91 auto distances = cell.GetOutDistance(source); 92 for (auto &destination : destinations) 93 { 94 BOOST_ASSERT(!weights.empty()); 95 BOOST_ASSERT(!durations.empty()); 96 BOOST_ASSERT(!distances.empty()); 97 98 const bool inserted = heap.WasInserted(destination); 99 weights.front() = inserted ? heap.GetKey(destination) : INVALID_EDGE_WEIGHT; 100 durations.front() = 101 inserted ? heap.GetData(destination).duration : MAXIMAL_EDGE_DURATION; 102 distances.front() = 103 inserted ? heap.GetData(destination).distance : INVALID_EDGE_DISTANCE; 104 105 weights.advance_begin(1); 106 durations.advance_begin(1); 107 distances.advance_begin(1); 108 } 109 BOOST_ASSERT(weights.empty()); 110 BOOST_ASSERT(durations.empty()); 111 BOOST_ASSERT(distances.empty()); 112 } 113 } 114 115 template <typename GraphT> Customize(const GraphT & graph,const partitioner::CellStorage & cells,const std::vector<bool> & allowed_nodes,CellMetric & metric) const116 void Customize(const GraphT &graph, 117 const partitioner::CellStorage &cells, 118 const std::vector<bool> &allowed_nodes, 119 CellMetric &metric) const 120 { 121 Heap heap_exemplar(graph.GetNumberOfNodes()); 122 HeapPtr heaps(heap_exemplar); 123 124 for (std::size_t level = 1; level < partition.GetNumberOfLevels(); ++level) 125 { 126 tbb::parallel_for(tbb::blocked_range<std::size_t>(0, partition.GetNumberOfCells(level)), 127 [&](const tbb::blocked_range<std::size_t> &range) { 128 auto &heap = heaps.local(); 129 for (auto id = range.begin(), end = range.end(); id != end; ++id) 130 { 131 Customize( 132 graph, heap, cells, allowed_nodes, metric, level, id); 133 } 134 }); 135 } 136 } 137 138 private: 139 template <typename GraphT> RelaxNode(const GraphT & graph,const partitioner::CellStorage & cells,const std::vector<bool> & allowed_nodes,const CellMetric & metric,Heap & heap,LevelID level,NodeID node,EdgeWeight weight,EdgeDuration duration,EdgeDistance distance) const140 void RelaxNode(const GraphT &graph, 141 const partitioner::CellStorage &cells, 142 const std::vector<bool> &allowed_nodes, 143 const CellMetric &metric, 144 Heap &heap, 145 LevelID level, 146 NodeID node, 147 EdgeWeight weight, 148 EdgeDuration duration, 149 EdgeDistance distance) const 150 { 151 auto first_level = level == 1; 152 BOOST_ASSERT(heap.WasInserted(node)); 153 154 if (!first_level) 155 { 156 // if we reaches this node from a clique arc we don't need to scan 157 // the clique arcs again because of the triangle inequality 158 // 159 // d(parent, node) + d(node, v) >= d(parent, v) 160 // 161 // And if there is a path (parent, node, v) there must also be a 162 // clique arc (parent, v) with d(parent, v). 163 if (!heap.GetData(node).from_clique) 164 { 165 // Relax sub-cell nodes 166 auto subcell_id = partition.GetCell(level - 1, node); 167 auto subcell = cells.GetCell(metric, level - 1, subcell_id); 168 auto subcell_destination = subcell.GetDestinationNodes().begin(); 169 auto subcell_duration = subcell.GetOutDuration(node).begin(); 170 auto subcell_distance = subcell.GetOutDistance(node).begin(); 171 for (auto subcell_weight : subcell.GetOutWeight(node)) 172 { 173 if (subcell_weight != INVALID_EDGE_WEIGHT) 174 { 175 const NodeID to = *subcell_destination; 176 if (!allowed_nodes[to]) 177 { 178 continue; 179 } 180 181 const EdgeWeight to_weight = weight + subcell_weight; 182 const EdgeDuration to_duration = duration + *subcell_duration; 183 const EdgeDistance to_distance = distance + *subcell_distance; 184 if (!heap.WasInserted(to)) 185 { 186 heap.Insert(to, to_weight, {true, to_duration, to_distance}); 187 } 188 else if (std::tie(to_weight, to_duration, to_distance) < 189 std::tie(heap.GetKey(to), 190 heap.GetData(to).duration, 191 heap.GetData(to).distance)) 192 { 193 heap.DecreaseKey(to, to_weight); 194 heap.GetData(to) = {true, to_duration, to_distance}; 195 } 196 } 197 198 ++subcell_destination; 199 ++subcell_duration; 200 ++subcell_distance; 201 } 202 } 203 } 204 205 // Relax base graph edges if a sub-cell border edge 206 for (auto edge : graph.GetInternalEdgeRange(level, node)) 207 { 208 const NodeID to = graph.GetTarget(edge); 209 if (!allowed_nodes[to]) 210 { 211 continue; 212 } 213 214 const auto &data = graph.GetEdgeData(edge); 215 if (data.forward && (first_level || partition.GetCell(level - 1, node) != 216 partition.GetCell(level - 1, to))) 217 { 218 const EdgeWeight to_weight = weight + data.weight; 219 const EdgeDuration to_duration = duration + data.duration; 220 const EdgeDistance to_distance = distance + data.distance; 221 if (!heap.WasInserted(to)) 222 { 223 heap.Insert( 224 to, to_weight, {false, duration + data.duration, distance + data.distance}); 225 } 226 else if (std::tie(to_weight, to_duration, to_distance) < 227 std::tie( 228 heap.GetKey(to), heap.GetData(to).duration, heap.GetData(to).distance)) 229 { 230 heap.DecreaseKey(to, to_weight); 231 heap.GetData(to) = {false, to_duration, to_distance}; 232 } 233 } 234 } 235 } 236 237 const partitioner::MultiLevelPartition &partition; 238 }; 239 } // namespace customizer 240 } // namespace osrm 241 242 #endif // OSRM_CELLS_CUSTOMIZER_HPP 243