1 #include "extractor/restriction_graph.hpp"
2 #include "util/node_based_graph.hpp"
3 #include "util/timing_util.hpp"
4 #include <util/for_each_pair.hpp>
5
6 #include <boost/assign.hpp>
7 #include <boost/range/algorithm/copy.hpp>
8
9 namespace osrm
10 {
11 namespace extractor
12 {
13
14 namespace restriction_graph_details
15 {
16
insertEdge(RestrictionGraph & rg,const RestrictionID id,const RestrictionEdge & edge)17 void insertEdge(RestrictionGraph &rg, const RestrictionID id, const RestrictionEdge &edge)
18 {
19 const auto range = rg.GetEdges(id);
20 auto &node = rg.nodes[id];
21 if (node.edges_begin_idx + range.size() != rg.edges.size())
22 {
23 // Most nodes will only have one edge, so this copy will be infrequent
24 node.edges_begin_idx = rg.edges.size();
25 std::copy(range.begin(), range.end(), std::back_inserter(rg.edges));
26 }
27 rg.edges.push_back(edge);
28 node.num_edges += 1;
29 }
30
insertRestriction(RestrictionGraph & rg,const RestrictionID id,const TurnRestriction * restriction)31 void insertRestriction(RestrictionGraph &rg,
32 const RestrictionID id,
33 const TurnRestriction *restriction)
34 {
35 const auto range = rg.GetRestrictions(id);
36 auto &node = rg.nodes[id];
37 if (node.restrictions_begin_idx + range.size() != rg.restrictions.size())
38 {
39 // Most nodes will only have zero or one restriction, so this copy will be infrequent
40 node.restrictions_begin_idx = rg.restrictions.size();
41 std::copy(range.begin(), range.end(), std::back_inserter(rg.restrictions));
42 }
43 rg.restrictions.push_back(restriction);
44 node.num_restrictions += 1;
45 }
46
getOrInsertStartNode(RestrictionGraph & rg,NodeID from,NodeID to)47 RestrictionID getOrInsertStartNode(RestrictionGraph &rg, NodeID from, NodeID to)
48 {
49 auto start_edge = std::make_pair(from, to);
50 auto start_node_idx_itr = rg.start_edge_to_node.find(start_edge);
51 if (start_node_idx_itr == rg.start_edge_to_node.end())
52 {
53 // First time we have seen a restriction start from this edge.
54 auto start_node_idx = rg.nodes.size();
55 rg.nodes.push_back(RestrictionNode{rg.restrictions.size(), 0, rg.edges.size(), 0});
56 start_node_idx_itr = rg.start_edge_to_node.insert({start_edge, start_node_idx}).first;
57 }
58 return start_node_idx_itr->second;
59 }
60
insertViaNode(RestrictionGraph & rg,NodeID from,NodeID to)61 RestrictionID insertViaNode(RestrictionGraph &rg, NodeID from, NodeID to)
62 {
63 auto new_via_node_idx = rg.nodes.size();
64 rg.nodes.push_back(RestrictionNode{rg.restrictions.size(), 0, rg.edges.size(), 0});
65 rg.via_edge_to_node.insert({{from, to}, new_via_node_idx});
66 return new_via_node_idx;
67 }
68
69 // pathBuilder builds the prefix tree structure that is used to first insert turn restrictions
70 // into the graph.
71 struct pathBuilder
72 {
73 RestrictionGraph &rg;
74 RestrictionID cur_node;
75
pathBuilderosrm::extractor::restriction_graph_details::pathBuilder76 pathBuilder(RestrictionGraph &rg_) : rg(rg_) { cur_node = SPECIAL_RESTRICTIONID; }
77
nameosrm::extractor::restriction_graph_details::pathBuilder78 static std::string name() { return "path builder"; };
79
startosrm::extractor::restriction_graph_details::pathBuilder80 void start(NodeID from, NodeID to) { cur_node = getOrInsertStartNode(rg, from, to); }
81
nextosrm::extractor::restriction_graph_details::pathBuilder82 void next(NodeID from, NodeID to)
83 {
84 const auto &edge_range = rg.GetEdges(cur_node);
85 auto edge_to_itr = std::find_if(edge_range.begin(),
86 edge_range.end(),
87 [&](const auto &edge) { return edge.node_based_to == to; });
88 if (edge_to_itr != edge_range.end())
89 {
90 cur_node = edge_to_itr->target;
91 return;
92 }
93
94 // This is a new restriction path we have not seen before.
95 // Add a new via node and edge to the tree.
96 auto new_via_node_idx = insertViaNode(rg, from, to);
97 insertEdge(rg, cur_node, RestrictionEdge{to, new_via_node_idx, false});
98
99 cur_node = new_via_node_idx;
100 }
101
endosrm::extractor::restriction_graph_details::pathBuilder102 void end(const TurnRestriction &restriction) { insertRestriction(rg, cur_node, &restriction); }
103 };
104
105 // transferBuilder adds the transfer edges between overlapping restriction paths. It does this
106 // by tracking paths in the graph that can be equal to a suffix of a restriction path, and
107 // attempting to connect the them with a new edge.
108 struct transferBuilder
109 {
110 RestrictionGraph &rg;
111 std::vector<RestrictionID> suffix_nodes;
112 RestrictionID cur_node;
113
transferBuilderosrm::extractor::restriction_graph_details::transferBuilder114 transferBuilder(RestrictionGraph &rg_) : rg(rg_) { cur_node = SPECIAL_RESTRICTIONID; }
115
nameosrm::extractor::restriction_graph_details::transferBuilder116 static std::string name() { return "transfer builder"; };
117
startosrm::extractor::restriction_graph_details::transferBuilder118 void start(NodeID from, NodeID to) { cur_node = getOrInsertStartNode(rg, from, to); }
119
next_suffixesosrm::extractor::restriction_graph_details::transferBuilder120 void next_suffixes(NodeID from, NodeID to)
121 {
122 // Update the suffix paths to include those that also have this edge
123 auto new_suffix_it = suffix_nodes.begin();
124 for (const auto &suffix_node : suffix_nodes)
125 {
126 const auto &edges = rg.GetEdges(suffix_node);
127 const auto edge_it = std::find_if(edges.begin(), edges.end(), [&to](const auto &edge) {
128 return edge.node_based_to == to && !edge.is_transfer;
129 });
130 if (edge_it != edges.end())
131 {
132 *(new_suffix_it++) = edge_it->target;
133 }
134 }
135 suffix_nodes.erase(new_suffix_it, suffix_nodes.end());
136
137 // Add a start node if it is a trivial suffix
138 auto start_way_it = rg.start_edge_to_node.find({from, to});
139 if (start_way_it != rg.start_edge_to_node.end())
140 {
141 suffix_nodes.push_back({start_way_it->second});
142 }
143 }
144
145 // For each edge on path, if there is an edge in the suffix path not on the current
146 // path, add as a transfer.
add_suffix_transferosrm::extractor::restriction_graph_details::transferBuilder147 void add_suffix_transfer(const RestrictionID &suffix_node)
148 {
149 for (const auto &suffix_edge : rg.GetEdges(suffix_node))
150 {
151 if (suffix_edge.is_transfer)
152 continue;
153
154 // Check there are no unconditional restrictions at the current node that would prevent
155 // the transfer
156 const auto &restrictions = rg.GetRestrictions(cur_node);
157 const auto is_restricted =
158 std::any_of(restrictions.begin(), restrictions.end(), [&](const auto &restriction) {
159 return restriction->IsTurnRestricted(suffix_edge.node_based_to) &&
160 restriction->IsUnconditional();
161 });
162 if (is_restricted)
163 continue;
164
165 const auto &edges = rg.GetEdges(cur_node);
166 // Check that the suffix edge is not a next edge along the current path.
167 const auto can_transfer = std::none_of(edges.begin(), edges.end(), [&](auto &edge) {
168 return edge.node_based_to == suffix_edge.node_based_to;
169 });
170 if (can_transfer)
171 {
172 insertEdge(rg,
173 cur_node,
174 RestrictionEdge{suffix_edge.node_based_to, suffix_edge.target, true});
175 }
176 }
177 };
178
nextosrm::extractor::restriction_graph_details::transferBuilder179 void next(NodeID from, NodeID to)
180 {
181 const auto &edges = rg.GetEdges(cur_node);
182 auto next_edge_itr = std::find_if(
183 edges.begin(), edges.end(), [&](const auto edge) { return edge.node_based_to == to; });
184
185 // We know this edge exists
186 cur_node = next_edge_itr->target;
187
188 this->next_suffixes(from, to);
189
190 std::for_each(suffix_nodes.begin(), suffix_nodes.end(), [&](const auto &suffix_node) {
191 this->add_suffix_transfer(suffix_node);
192 });
193
194 for (const auto &suffix_node : suffix_nodes)
195 {
196 // Also add any restrictions from suffix paths to the current node in the
197 // restriction graph.
198 for (const auto &restriction : rg.GetRestrictions(suffix_node))
199 {
200 insertRestriction(rg, cur_node, restriction);
201 }
202 }
203 }
204
endosrm::extractor::restriction_graph_details::transferBuilder205 void end(const TurnRestriction & /*unused*/) {}
206 };
207
208 template <typename builder_type>
buildGraph(RestrictionGraph & rg,const std::vector<TurnRestriction> & restrictions)209 void buildGraph(RestrictionGraph &rg, const std::vector<TurnRestriction> &restrictions)
210 {
211 const auto run_builder = [&](const auto &restriction) {
212 builder_type builder(rg);
213
214 builder.start(restriction.From(), restriction.FirstVia());
215 if (restriction.Type() == RestrictionType::WAY_RESTRICTION)
216 {
217 const auto &way_restriction = restriction.AsWayRestriction();
218 util::for_each_pair(way_restriction.via.begin(),
219 way_restriction.via.end(),
220 [&](NodeID from, NodeID to) { builder.next(from, to); });
221 }
222 builder.end(restriction);
223 };
224
225 std::for_each(restrictions.begin(), restrictions.end(), run_builder);
226 }
227 } // namespace restriction_graph_details
228
constructRestrictionGraph(const std::vector<TurnRestriction> & turn_restrictions)229 RestrictionGraph constructRestrictionGraph(const std::vector<TurnRestriction> &turn_restrictions)
230 {
231 util::UnbufferedLog log;
232 log << "Constructing restriction graph on " << turn_restrictions.size() << " restrictions...";
233 TIMER_START(construct_restriction_graph);
234
235 namespace rgd = restriction_graph_details;
236 RestrictionGraph rg;
237 rgd::buildGraph<rgd::pathBuilder>(rg, turn_restrictions);
238 rgd::buildGraph<rgd::transferBuilder>(rg, turn_restrictions);
239
240 // Reorder nodes so that via nodes are at the front. This makes it easier to represent the
241 // bijection between restriction graph via nodes and edge-based graph duplicate nodes.
242 std::vector<bool> is_via_node(rg.nodes.size(), false);
243 for (const auto &entry : rg.via_edge_to_node)
244 {
245 is_via_node[entry.second] = true;
246 }
247 std::vector<RestrictionID> ordering(rg.nodes.size());
248 std::iota(ordering.begin(), ordering.end(), 0);
249 std::partition(ordering.begin(), ordering.end(), [&](const auto i) { return is_via_node[i]; });
250 // Start renumbering
251 const auto permutation = util::orderingToPermutation(ordering);
252 util::inplacePermutation(rg.nodes.begin(), rg.nodes.end(), permutation);
253 std::for_each(rg.edges.begin(), rg.edges.end(), [&](auto &edge) {
254 edge.target = permutation[edge.target];
255 });
256 rg.num_via_nodes = std::count(is_via_node.begin(), is_via_node.end(), true);
257 for (auto &entry : rg.via_edge_to_node)
258 {
259 entry.second = permutation[entry.second];
260 }
261 for (auto &entry : rg.start_edge_to_node)
262 {
263 entry.second = permutation[entry.second];
264 }
265
266 TIMER_STOP(construct_restriction_graph);
267 log << "ok, after " << TIMER_SEC(construct_restriction_graph) << "s";
268
269 return rg;
270 }
271
GetRestrictions(RestrictionID id) const272 RestrictionGraph::RestrictionRange RestrictionGraph::GetRestrictions(RestrictionID id) const
273 {
274 const auto &node = nodes[id];
275 return boost::make_iterator_range(restrictions.begin() + node.restrictions_begin_idx,
276 restrictions.begin() + node.restrictions_begin_idx +
277 node.num_restrictions);
278 }
279
GetEdges(RestrictionID id) const280 RestrictionGraph::EdgeRange RestrictionGraph::GetEdges(RestrictionID id) const
281 {
282 const auto &node = nodes[id];
283 return boost::make_iterator_range(edges.begin() + node.edges_begin_idx,
284 edges.begin() + node.edges_begin_idx + node.num_edges);
285 }
286
287 } // namespace extractor
288 } // namespace osrm
289