1 #ifndef OSRM_EXTRACTOR_RESTRICTION_GRAPH_HPP_ 2 #define OSRM_EXTRACTOR_RESTRICTION_GRAPH_HPP_ 3 4 #include <boost/assert.hpp> 5 #include <boost/unordered_map.hpp> 6 7 #include "extractor/restriction_filter.hpp" 8 #include "util/node_based_graph.hpp" 9 #include "util/typedefs.hpp" 10 11 namespace osrm 12 { 13 namespace extractor 14 { 15 16 namespace restriction_graph_details 17 { 18 struct transferBuilder; 19 struct pathBuilder; 20 } // namespace restriction_graph_details 21 22 struct RestrictionEdge 23 { 24 NodeID node_based_to; 25 RestrictionID target; 26 bool is_transfer; 27 }; 28 29 struct RestrictionNode 30 { 31 size_t restrictions_begin_idx; 32 size_t num_restrictions; 33 size_t edges_begin_idx; 34 size_t num_edges; 35 }; 36 37 /** 38 * The restriction graph is used to represent all possible restrictions within the routing graph. 39 * The graph uses an edge-based node representation. Each node represents a compressed 40 * node-based edge along a restriction path. 41 * 42 * Given a list of turn restrictions, the graph is created in multiple steps. 43 * 44 * INPUT 45 * a -> b -> d: no_e 46 * a -> b -> c: only_d 47 * b -> c -> d: only_f 48 * b -> c: no_g 49 * e -> b -> d: no_g 50 * 51 * Step 1: create a disjoint union of prefix trees for all restriction paths. 52 * The restriction instructions are added to the final node in its path. 53 * 54 * STEP 1 55 * (a,b) -> (b,d,[no_e]) 56 * \->(b,c,[only_d]) 57 * 58 * (b,c,[no_g]) -> (c,d,[only_f]) 59 * (e,b) -> (b,d,[no_g]) 60 * 61 * Step 2: add transfers between restriction paths that overlap. 62 * We do this by traversing each restriction path, tracking where the suffix of our current path 63 * matches the prefix of any other. If it does, there's opportunity to transfer to the suffix 64 * restriction path *if* the transfer would not be restricted *and* that edge does not take us 65 * further on our current path. Nested restrictions are also added from any of the suffix paths. 66 * 67 * STEP 2 68 * (a,b) -> (b,d,[no_e]) 69 * \->(b,c,[only_d,no_g]) 70 * \ 71 * (b,c,[no_g]) -> \-> (c,d,[only_f]) 72 * 73 * (e,b) -> (b,d,[no_g]) 74 * If a transfer applies to multiple suffix paths, we only add the edge to the largest suffix path. 75 * This ensures we correctly track all overlapping paths. 76 * 77 * 78 * Step 3: The nodes are split into 79 * start nodes - compressed edges that are entry points into a restriction path. 80 * via nodes - compressed edges that are intermediate steps along a restriction path. 81 * Start nodes and via nodes are indexed by the compressed node-based edge for easy retrieval 82 * 83 * STEP 3 84 * Start Node Index 85 * (a,b) => (a,b) 86 * (b,c) => (b,c,[no_g]) 87 * (e,b) => (e,b) 88 * 89 * Via Nodes Index 90 * (b,c) => (b,c,[only_d,no_g]) 91 * (b,d) => (b,d,[no_e]) , (b,d,[no_g]) 92 * (c,d) => (c,d,[only_f]) 93 * 94 * Duplicate Nodes: 95 * There is a 1-1 mapping between restriction graph via nodes and edge-based-graph duplicate nodes. 96 * This relationship is used in the creation of restrictions in the routing edge-based graph. 97 * */ 98 struct RestrictionGraph 99 { 100 friend restriction_graph_details::pathBuilder; 101 friend restriction_graph_details::transferBuilder; 102 friend RestrictionGraph constructRestrictionGraph(const std::vector<TurnRestriction> &); 103 104 using EdgeRange = boost::iterator_range<std::vector<RestrictionEdge>::const_iterator>; 105 using RestrictionRange = 106 boost::iterator_range<std::vector<const TurnRestriction *>::const_iterator>; 107 using EdgeKey = std::pair<NodeID, NodeID>; 108 109 // Helper functions for iterating over node restrictions and edges 110 EdgeRange GetEdges(RestrictionID id) const; 111 RestrictionRange GetRestrictions(RestrictionID id) const; 112 113 // A compressed node-based edge can only have one start node in the restriction graph. 114 boost::unordered_map<EdgeKey, RestrictionID> start_edge_to_node{}; 115 // A compressed node-based edge can have multiple via nodes in the restriction graph 116 // (as the compressed edge can appear in paths with different prefixes). 117 boost::unordered_multimap<EdgeKey, RestrictionID> via_edge_to_node{}; 118 std::vector<RestrictionNode> nodes; 119 // TODO: Investigate reusing DynamicGraph. Currently it requires specific attributes 120 // (e.g. reversed, weight) that would not make sense for restrictions. 121 std::vector<RestrictionEdge> edges; 122 std::vector<const TurnRestriction *> restrictions; 123 size_t num_via_nodes{}; 124 125 private: 126 RestrictionGraph() = default; 127 }; 128 129 RestrictionGraph constructRestrictionGraph(const std::vector<TurnRestriction> &turn_restrictions); 130 131 } // namespace extractor 132 } // namespace osrm 133 134 #endif // OSRM_EXTRACTOR_RESTRICTION_GRAPH_HPP_ 135