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