1 #ifndef STATIC_GRAPH_HPP 2 #define STATIC_GRAPH_HPP 3 4 #include "util/graph_traits.hpp" 5 #include "util/integer_range.hpp" 6 #include "util/percent.hpp" 7 #include "util/permutation.hpp" 8 #include "util/typedefs.hpp" 9 #include "util/vector_view.hpp" 10 11 #include "storage/shared_memory_ownership.hpp" 12 #include "storage/tar_fwd.hpp" 13 14 #include <boost/assert.hpp> 15 16 #include <algorithm> 17 #include <limits> 18 #include <type_traits> 19 #include <utility> 20 #include <vector> 21 22 namespace osrm 23 { 24 namespace util 25 { 26 template <typename EdgeDataT, storage::Ownership Ownership> class StaticGraph; 27 28 namespace serialization 29 { 30 template <typename EdgeDataT, storage::Ownership Ownership> 31 void read(storage::tar::FileReader &reader, 32 const std::string &name, 33 StaticGraph<EdgeDataT, Ownership> &graph); 34 35 template <typename EdgeDataT, storage::Ownership Ownership> 36 void write(storage::tar::FileWriter &writer, 37 const std::string &name, 38 const StaticGraph<EdgeDataT, Ownership> &graph); 39 } // namespace serialization 40 41 namespace static_graph_details 42 { 43 44 using NodeIterator = NodeID; 45 using EdgeIterator = NodeID; 46 47 struct NodeArrayEntry 48 { 49 // index of the first edge 50 EdgeIterator first_edge; 51 }; 52 53 template <typename EdgeDataT> struct EdgeArrayEntry; 54 55 template <typename EdgeDataT> struct EdgeArrayEntry 56 { 57 NodeID target; 58 EdgeDataT data; 59 }; 60 61 template <> struct EdgeArrayEntry<void> 62 { 63 NodeID target; 64 }; 65 66 template <typename EdgeDataT> struct SortableEdgeWithData; 67 68 template <> struct SortableEdgeWithData<void> 69 { 70 NodeIterator source; 71 NodeIterator target; 72 73 SortableEdgeWithData() = default; 74 SortableEdgeWithDataosrm::util::static_graph_details::SortableEdgeWithData75 SortableEdgeWithData(NodeIterator source, NodeIterator target) : source(source), target(target) 76 { 77 } 78 operator <osrm::util::static_graph_details::SortableEdgeWithData79 bool operator<(const SortableEdgeWithData &right) const 80 { 81 return std::tie(source, target) < std::tie(right.source, right.target); 82 } 83 operator ==osrm::util::static_graph_details::SortableEdgeWithData84 bool operator==(const SortableEdgeWithData &right) const 85 { 86 return std::tie(source, target) == std::tie(right.source, right.target); 87 } 88 }; 89 90 template <typename EdgeDataT> struct SortableEdgeWithData : SortableEdgeWithData<void> 91 { 92 using Base = SortableEdgeWithData<void>; 93 94 EdgeDataT data; 95 96 SortableEdgeWithData() = default; 97 98 template <typename... Ts> SortableEdgeWithDataosrm::util::static_graph_details::SortableEdgeWithData99 SortableEdgeWithData(NodeIterator source, NodeIterator target, Ts &&... data) 100 : Base{source, target}, data{std::forward<Ts>(data)...} 101 { 102 } 103 }; 104 105 template <typename EntryT, typename OtherEdge> 106 EntryT edgeToEntry(const OtherEdge &from, std::true_type) 107 { 108 return EntryT{from.target, from.data}; 109 } 110 template <typename EntryT, typename OtherEdge> 111 EntryT edgeToEntry(const OtherEdge &from, std::false_type) 112 { 113 return EntryT{from.target}; 114 } 115 116 } // namespace static_graph_details 117 118 template <typename EdgeDataT, storage::Ownership Ownership = storage::Ownership::Container> 119 class StaticGraph 120 { 121 template <typename T> using Vector = util::ViewOrVector<T, Ownership>; 122 123 public: 124 using InputEdge = static_graph_details::SortableEdgeWithData<EdgeDataT>; 125 using NodeIterator = static_graph_details::NodeIterator; 126 using EdgeIterator = static_graph_details::EdgeIterator; 127 using EdgeRange = range<EdgeIterator>; 128 using NodeArrayEntry = static_graph_details::NodeArrayEntry; 129 using EdgeArrayEntry = static_graph_details::EdgeArrayEntry<EdgeDataT>; 130 GetAdjacentEdgeRange(const NodeID node) const131 EdgeRange GetAdjacentEdgeRange(const NodeID node) const 132 { 133 return irange(BeginEdges(node), EndEdges(node)); 134 } 135 StaticGraph()136 StaticGraph() {} 137 StaticGraph(const std::uint32_t nodes,const ContainerT & edges)138 template <typename ContainerT> StaticGraph(const std::uint32_t nodes, const ContainerT &edges) 139 { 140 BOOST_ASSERT(std::is_sorted(const_cast<ContainerT &>(edges).begin(), 141 const_cast<ContainerT &>(edges).end())); 142 143 InitializeFromSortedEdgeRange(nodes, edges.begin(), edges.end()); 144 } 145 StaticGraph(Vector<NodeArrayEntry> node_array_,Vector<EdgeArrayEntry> edge_array_)146 StaticGraph(Vector<NodeArrayEntry> node_array_, Vector<EdgeArrayEntry> edge_array_) 147 : node_array(std::move(node_array_)), edge_array(std::move(edge_array_)) 148 { 149 BOOST_ASSERT(!node_array.empty()); 150 151 number_of_nodes = static_cast<decltype(number_of_nodes)>(node_array.size() - 1); 152 number_of_edges = static_cast<decltype(number_of_edges)>(node_array.back().first_edge); 153 BOOST_ASSERT(number_of_edges <= edge_array.size()); 154 BOOST_ASSERT(number_of_nodes == node_array.size() - 1); 155 } 156 GetNumberOfNodes() const157 unsigned GetNumberOfNodes() const { return number_of_nodes; } 158 GetNumberOfEdges() const159 unsigned GetNumberOfEdges() const { return number_of_edges; } 160 GetOutDegree(const NodeIterator n) const161 unsigned GetOutDegree(const NodeIterator n) const { return EndEdges(n) - BeginEdges(n); } 162 GetTarget(const EdgeIterator e) const163 inline NodeIterator GetTarget(const EdgeIterator e) const 164 { 165 return NodeIterator(edge_array[e].target); 166 } 167 GetEdgeData(const EdgeIterator e)168 auto &GetEdgeData(const EdgeIterator e) { return edge_array[e].data; } 169 GetEdgeData(const EdgeIterator e) const170 const auto &GetEdgeData(const EdgeIterator e) const { return edge_array[e].data; } 171 BeginEdges(const NodeIterator n) const172 EdgeIterator BeginEdges(const NodeIterator n) const 173 { 174 return EdgeIterator(node_array.at(n).first_edge); 175 } 176 EndEdges(const NodeIterator n) const177 EdgeIterator EndEdges(const NodeIterator n) const 178 { 179 return EdgeIterator(node_array.at(n + 1).first_edge); 180 } 181 182 // searches for a specific edge FindEdge(const NodeIterator from,const NodeIterator to) const183 EdgeIterator FindEdge(const NodeIterator from, const NodeIterator to) const 184 { 185 for (const auto i : irange(BeginEdges(from), EndEdges(from))) 186 { 187 if (to == edge_array[i].target) 188 { 189 return i; 190 } 191 } 192 return SPECIAL_EDGEID; 193 } 194 195 /** 196 * Finds the edge with the smallest `.weight` going from `from` to `to` 197 * @param from the source node ID 198 * @param to the target node ID 199 * @param filter a functor that returns a `bool` that determines whether an edge should be 200 * tested or not. 201 * Takes `EdgeData` as a parameter. 202 * @return the ID of the smallest edge if any were found that satisfied *filter*, or 203 * `SPECIAL_EDGEID` if no 204 * matching edge is found. 205 */ 206 template <typename FilterFunction> 207 EdgeIterator FindSmallestEdge(const NodeIterator from,const NodeIterator to,FilterFunction && filter) const208 FindSmallestEdge(const NodeIterator from, const NodeIterator to, FilterFunction &&filter) const 209 { 210 static_assert(traits::HasDataMember<EdgeArrayEntry>::value, 211 "Filtering on .data not possible without .data member attribute"); 212 213 EdgeIterator smallest_edge = SPECIAL_EDGEID; 214 EdgeWeight smallest_weight = INVALID_EDGE_WEIGHT; 215 for (auto edge : GetAdjacentEdgeRange(from)) 216 { 217 const NodeID target = GetTarget(edge); 218 const auto &data = GetEdgeData(edge); 219 if (target == to && data.weight < smallest_weight && 220 std::forward<FilterFunction>(filter)(data)) 221 { 222 smallest_edge = edge; 223 smallest_weight = data.weight; 224 } 225 } 226 return smallest_edge; 227 } 228 FindEdgeInEitherDirection(const NodeIterator from,const NodeIterator to) const229 EdgeIterator FindEdgeInEitherDirection(const NodeIterator from, const NodeIterator to) const 230 { 231 EdgeIterator tmp = FindEdge(from, to); 232 return (SPECIAL_NODEID != tmp ? tmp : FindEdge(to, from)); 233 } 234 235 EdgeIterator FindEdgeIndicateIfReverse(const NodeIterator from,const NodeIterator to,bool & result) const236 FindEdgeIndicateIfReverse(const NodeIterator from, const NodeIterator to, bool &result) const 237 { 238 EdgeIterator current_iterator = FindEdge(from, to); 239 if (SPECIAL_NODEID == current_iterator) 240 { 241 current_iterator = FindEdge(to, from); 242 if (SPECIAL_NODEID != current_iterator) 243 { 244 result = true; 245 } 246 } 247 return current_iterator; 248 } 249 Renumber(const std::vector<NodeID> & old_to_new_node)250 void Renumber(const std::vector<NodeID> &old_to_new_node) 251 { 252 std::vector<NodeID> new_to_old_node(number_of_nodes); 253 for (auto node : util::irange<NodeID>(0, number_of_nodes)) 254 new_to_old_node[old_to_new_node[node]] = node; 255 256 Vector<NodeArrayEntry> new_node_array(node_array.size()); 257 258 // Build up edge permutation 259 auto new_edge_index = 0; 260 std::vector<EdgeID> old_to_new_edge(edge_array.size(), SPECIAL_EDGEID); 261 for (auto node : util::irange<NodeID>(0, number_of_nodes)) 262 { 263 auto new_first_edge = new_edge_index; 264 for (auto edge : GetAdjacentEdgeRange(new_to_old_node[node])) 265 { 266 edge_array[edge].target = old_to_new_node[edge_array[edge].target]; 267 old_to_new_edge[edge] = new_edge_index++; 268 } 269 new_node_array[node].first_edge = new_first_edge; 270 } 271 new_node_array.back().first_edge = new_edge_index; 272 node_array = std::move(new_node_array); 273 BOOST_ASSERT(std::find(old_to_new_edge.begin(), old_to_new_edge.end(), SPECIAL_EDGEID) == 274 old_to_new_edge.end()); 275 276 util::inplacePermutation(edge_array.begin(), edge_array.end(), old_to_new_edge); 277 } 278 279 friend void serialization::read<EdgeDataT, Ownership>(storage::tar::FileReader &reader, 280 const std::string &name, 281 StaticGraph<EdgeDataT, Ownership> &graph); 282 friend void 283 serialization::write<EdgeDataT, Ownership>(storage::tar::FileWriter &writer, 284 const std::string &name, 285 const StaticGraph<EdgeDataT, Ownership> &graph); 286 287 protected: 288 template <typename IterT> InitializeFromSortedEdgeRange(const std::uint32_t nodes,IterT begin,IterT end)289 void InitializeFromSortedEdgeRange(const std::uint32_t nodes, IterT begin, IterT end) 290 { 291 number_of_nodes = nodes; 292 number_of_edges = static_cast<EdgeIterator>(std::distance(begin, end)); 293 node_array.reserve(number_of_nodes + 1); 294 node_array.push_back(NodeArrayEntry{0u}); 295 auto iter = begin; 296 for (auto node : util::irange(0u, nodes)) 297 { 298 iter = 299 std::find_if(iter, end, [node](const auto &edge) { return edge.source != node; }); 300 unsigned offset = std::distance(begin, iter); 301 node_array.push_back(NodeArrayEntry{offset}); 302 } 303 BOOST_ASSERT_MSG( 304 iter == end, 305 ("Still " + std::to_string(std::distance(iter, end)) + " edges left.").c_str()); 306 BOOST_ASSERT(node_array.size() == number_of_nodes + 1); 307 308 edge_array.resize(number_of_edges); 309 std::transform(begin, end, edge_array.begin(), [](const auto &from) { 310 return static_graph_details::edgeToEntry<EdgeArrayEntry>( 311 from, traits::HasDataMember<EdgeArrayEntry>{}); 312 }); 313 } 314 315 protected: 316 NodeIterator number_of_nodes; 317 EdgeIterator number_of_edges; 318 319 Vector<NodeArrayEntry> node_array; 320 Vector<EdgeArrayEntry> edge_array; 321 }; 322 323 } // namespace util 324 } // namespace osrm 325 326 #endif // STATIC_GRAPH_HPP 327