Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2026 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file CCHRouter.h
15 : /// @author Pranav Sateesh
16 : /// @date 2026
17 : ///
18 : // A SUMOAbstractRouter that answers queries via a RoutingKit Customizable
19 : // Contraction Hierarchy over the edge graph. The metric is re-customized
20 : // out-of-band (MSRoutingEngine::adaptEdgeEfforts) and published as a
21 : // shared_ptr snapshot; each query snapshots the current metric, so a
22 : // publish that lands mid-query is safe (double buffer).
23 : //
24 : // Following the AStarRouter<E, V, M> lookup-table pattern, the graph-mapping
25 : // class is the GRAPH template parameter (the simulation supplies its concrete
26 : // mapper, e.g. microsim's CCHGraph), so this header carries no simulation
27 : // dependencies. GRAPH must provide:
28 : // unsigned nodeOf(const E*) (INVALID_NODE if not a node)
29 : // const E* edgeOf(unsigned node)
30 : // const std::vector<unsigned>& tazSources(const E*) (entry-edge node sets)
31 : // const std::vector<unsigned>& tazSinks(const E*) (exit-edge node sets)
32 : // void expandNodePath(const std::vector<unsigned>&, std::vector<const E*>&)
33 : // static const unsigned INVALID_NODE
34 : //
35 : // Every vehicle class routes on CCH via its own published metric. Closures are
36 : // permission changes the per-class metric encodes as inf_weight once they have
37 : // been customized in; the simulation's metric provider hands out nullptr while
38 : // a permission flip is still pending, so those queries route exactly. The
39 : // embedded A* fallback is used when a class has no (fresh) metric, when the
40 : // vehicle routes on the ORIGINAL permissions (ignoreTransientPermissions --
41 : // the shared metric bakes in the live ones), or when a prohibition is NOT
42 : // expressible as a live permission closure (an arbitrary per-query
43 : // prohibition, which no shared CCH metric can represent) -- see compute() /
44 : // prohibitionsCoveredByMetric().
45 : /****************************************************************************/
46 : #pragma once
47 : #include <config.h>
48 :
49 :
50 : #include <memory>
51 : #include <vector>
52 : #include <cmath>
53 : #include <utils/common/Named.h>
54 : #include <utils/common/SUMOTime.h>
55 : #include <utils/common/MsgHandler.h>
56 : #include <utils/common/SUMOVehicleClass.h>
57 : #include <utils/router/SUMOAbstractRouter.h>
58 : #ifdef __GNUC__
59 : #pragma GCC diagnostic push
60 : #pragma GCC diagnostic ignored "-Wunused-parameter"
61 : #endif
62 : #ifdef _MSC_VER
63 : #pragma warning(push)
64 : #pragma warning(disable: 4267 4458)
65 : #endif
66 : #include <routingkit/customizable_contraction_hierarchy.h>
67 : #ifdef _MSC_VER
68 : #pragma warning(pop)
69 : #endif
70 : #ifdef __GNUC__
71 : #pragma GCC diagnostic pop
72 : #endif
73 :
74 :
75 : // ===========================================================================
76 : // class definitions
77 : // ===========================================================================
78 : /**
79 : * @class CCHRouter
80 : * @brief Contraction-hierarchy router over the edge graph mapped by GRAPH.
81 : */
82 : template<class E, class V, class GRAPH>
83 : class CCHRouter : public SUMOAbstractRouter<E, V> {
84 : public:
85 : typedef const RoutingKit::CustomizableContractionHierarchyMetric* MetricPtr;
86 : /// @brief supplies the metric for a vehicle class at a query time, or
87 : /// nullptr => fall back. The simulation ignores time and vehicle (its
88 : /// single metric tracks the live speeds); duarouter keys one metric per
89 : /// (class, restriction profile, weight period) with them.
90 : typedef MetricPtr(*MetricProvider)(SUMOVehicleClass, SUMOTime, const V*);
91 : /// @brief the end of the weight period containing the given time
92 : /// (SUMOTime_MAX = weights are static). Lets compute() detect queries
93 : /// whose trip crosses into the next period and re-query on that
94 : /// period's metric (see the boundary handling in compute()).
95 : typedef SUMOTime(*PeriodEnd)(SUMOTime);
96 : /// @brief the host's efforts changed behind the metrics and it reset the
97 : /// router (SUMOAbstractRouter::reset -- marouter does so after every
98 : /// assignment iteration, which is where CH rebuilds its hierarchy): the
99 : /// metric store should re-customize before the next query
100 : typedef void (*ResetHook)(const V*);
101 : typedef typename SUMOAbstractRouter<E, V>::Operation Operation;
102 : typedef typename SUMOAbstractRouter<E, V>::Prohibitions Prohibitions;
103 :
104 : /** @brief Constructor.
105 : * @param[in] graph the shared immutable CCH topology mapper (not owned)
106 : * @param[in] provider static accessor for the published metric snapshot
107 : * @param[in] operation the effort callback (same one A-star and CH use)
108 : * @param[in] fallback embedded router for non-CCH cases (OWNED)
109 : * @param[in] periodEnd weight-period boundary hook (nullptr = static weights)
110 : * @param[in] onReset hook run by reset() (nullptr = nobody to notify)
111 : */
112 894 : CCHRouter(const GRAPH* graph, MetricProvider provider,
113 : Operation operation, const bool unbuildIsWarning,
114 : SUMOAbstractRouter<E, V>* fallback,
115 : PeriodEnd periodEnd = nullptr, ResetHook onReset = nullptr) :
116 : SUMOAbstractRouter<E, V>("CCHRouter", unbuildIsWarning, operation, nullptr, false, false),
117 1788 : myGraph(graph), myMetricProvider(provider), myFallback(fallback),
118 1788 : myPeriodEnd(periodEnd), myOnReset(onReset), myProhibitionActive(false) {
119 894 : }
120 :
121 : /// @brief clone constructor: share graph + provider, clone the fallback, fresh query scratch
122 19 : CCHRouter(CCHRouter* other) :
123 : SUMOAbstractRouter<E, V>(other),
124 19 : myGraph(other->myGraph), myMetricProvider(other->myMetricProvider),
125 38 : myFallback(other->myFallback->clone()), myPeriodEnd(other->myPeriodEnd),
126 19 : myOnReset(other->myOnReset),
127 19 : myProhibitionActive(other->myProhibitionActive), myProhibited(other->myProhibited) {
128 19 : }
129 :
130 1826 : virtual ~CCHRouter() {
131 913 : delete myFallback;
132 2739 : }
133 :
134 19 : virtual SUMOAbstractRouter<E, V>* clone() {
135 19 : return new CCHRouter<E, V, GRAPH>(this);
136 : }
137 :
138 : /// @brief the host's efforts changed (see ResetHook): notify the metric
139 : /// store and reset the fallback's caches. Must not run while another
140 : /// clone is mid-query; marouter resets once its worker threads have
141 : /// finished the iteration.
142 48 : virtual void reset(const V* const vehicle) {
143 48 : if (myOnReset != nullptr) {
144 48 : myOnReset(vehicle);
145 : }
146 48 : myFallback->reset(vehicle);
147 48 : }
148 :
149 80504 : bool compute(const E* from, const E* to, const V* const vehicle,
150 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
151 : // A CCH query can only avoid an edge the metric already encodes as inf:
152 : // RoutingKit's query has no per-arc blacklist, and a query-time skip is
153 : // unsound because shortcut arcs bake in shortest paths THROUGH the edge
154 : // (SUMO's own CHRouter refuses prohibitions for the same reason). So we
155 : // run CCH when the metric can express the request and fall back to the
156 : // exact A* router otherwise: (a) no metric for this class, or (b) an
157 : // active prohibition that is NOT already a live permission-closure this
158 : // class's metric encodes (prohibitionsCoveredByMetric).
159 80504 : const SUMOVehicleClass vClass = vehicle == nullptr ? SVC_PASSENGER : vehicle->getVClass();
160 : // A vehicle that routes on the ORIGINAL permissions (routing mode bit
161 : // ROUTING_MODE_IGNORE_TRANSIENT_PERMISSIONS) cannot use the shared
162 : // metric, which bakes in the LIVE permissions, transient closures
163 : // included -- route it exactly, like Dijkstra/A* do natively.
164 75691 : if (vehicle != nullptr && vehicle->ignoreTransientPermissions()) {
165 381 : return myFallback->compute(from, to, vehicle, msTime, into, silent);
166 : }
167 80123 : MetricPtr metric = myMetricProvider(vClass, msTime, vehicle);
168 80123 : if (metric == nullptr || (myProhibitionActive && !prohibitionsCoveredByMetric(vClass))) {
169 192 : return myFallback->compute(from, to, vehicle, msTime, into, silent);
170 : }
171 : // Endpoints -> node SETS: a district star connector expands to its
172 : // member edges (phantom-node seeding); everything that is a graph
173 : // node -- including legacy function="connector" net edges -- routes
174 : // as a single node. TAZ member edges are the class-union set, so
175 : // filter to edges this class may enter.
176 80184 : const bool fromTaz = from->isTazConnector() && myGraph->nodeOf(from) == GRAPH::INVALID_NODE;
177 80199 : const bool toTaz = to->isTazConnector() && myGraph->nodeOf(to) == GRAPH::INVALID_NODE;
178 : // Mirror the exact routers' endpoint rejection (AStarRouter::compute):
179 : // an endpoint the vehicle may not use fails loudly instead of quietly
180 : // seeding a query on it. The metric masks only arcs BETWEEN nodes --
181 : // the source edge's own closure never enters it (its effort is added
182 : // as a plain source seed), so without this check a query from a
183 : // hard-closed edge would "succeed". TAZ members are filtered below.
184 79931 : if (vehicle != nullptr) {
185 79931 : if (!fromTaz && from->prohibits(vehicle)) {
186 6 : if (!silent && this->myErrorMsgHandler != nullptr) {
187 18 : this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on source edge '" + from->getID() + "'.");
188 : }
189 6 : return false;
190 : }
191 79925 : if (!toTaz && to->prohibits(vehicle)) {
192 5 : if (!silent && this->myErrorMsgHandler != nullptr) {
193 6 : this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on destination edge '" + to->getID() + "'.");
194 : }
195 5 : return false;
196 : }
197 : }
198 4808 : std::vector<unsigned> srcBuf, tgtBuf;
199 : const std::vector<unsigned>* sources;
200 : const std::vector<unsigned>* targets;
201 79920 : if (fromTaz) {
202 660 : for (const unsigned m : myGraph->tazSources(from)) {
203 407 : if ((myGraph->edgeOf(m)->getPermissions() & vClass) != 0) {
204 407 : srcBuf.push_back(m);
205 : }
206 : }
207 : sources = &srcBuf;
208 : } else {
209 79667 : const unsigned s = myGraph->nodeOf(from);
210 79667 : if (s != GRAPH::INVALID_NODE) {
211 79667 : srcBuf.push_back(s);
212 : }
213 : sources = &srcBuf;
214 : }
215 79920 : if (toTaz) {
216 702 : for (const unsigned m : myGraph->tazSinks(to)) {
217 434 : if ((myGraph->edgeOf(m)->getPermissions() & vClass) != 0) {
218 434 : tgtBuf.push_back(m);
219 : }
220 : }
221 : targets = &tgtBuf;
222 : } else {
223 79652 : const unsigned t = myGraph->nodeOf(to);
224 79652 : if (t != GRAPH::INVALID_NODE) {
225 79652 : tgtBuf.push_back(t);
226 : }
227 : targets = &tgtBuf;
228 : }
229 79920 : if (sources->empty() || targets->empty()) {
230 : // unmappable endpoint (e.g. internal edge, or a TAZ with no member
231 : // in this class's graph) -> exact fallback.
232 0 : return myFallback->compute(from, to, vehicle, msTime, into, silent);
233 : }
234 :
235 : this->startQuery();
236 79920 : const double t = STEPS2TIME(msTime);
237 79920 : if (!runQuery(metric, *sources, *targets, vehicle, t)) {
238 : this->endQuery(0);
239 166 : if (!silent && this->myErrorMsgHandler != nullptr) {
240 284 : this->myErrorMsgHandler->informf(TL("No connection between edge '%' and edge '%' found."),
241 : from->getID(), to->getID());
242 : }
243 166 : return false;
244 : }
245 4690 : std::vector<const E*> path;
246 79754 : buildPath(from, to, fromTaz, toTaz, path);
247 79754 : int visited = (int)path.size();
248 : // Weight-period boundary: the metric of the depart period is exact as
249 : // long as the trip finishes inside that period (efforts are constant
250 : // within it, and no time-propagated optimum can cross the boundary if
251 : // this trip does not: any path entering the next period costs at
252 : // least the remaining period, which already exceeds this result).
253 : // When the trip does cross, ALSO query the next period's metric and
254 : // keep whichever path is cheaper under the true time-propagating
255 : // walk (recomputeCosts). Exact for the common single-crossing case
256 : // where the optimum follows one period's structure; trips spanning
257 : // several periods keep the better of the two candidates.
258 79754 : if (myPeriodEnd != nullptr && myQuery.get_distance() > 0) {
259 788 : const SUMOTime boundary = myPeriodEnd(msTime);
260 : if (boundary != SUMOTime_MAX
261 788 : && msTime + TIME2STEPS((double)myQuery.get_distance() / 100.) >= boundary) {
262 0 : MetricPtr altMetric = myMetricProvider(vClass, boundary, vehicle);
263 0 : if (altMetric != nullptr && altMetric != metric
264 0 : && runQuery(altMetric, *sources, *targets, vehicle, t)) {
265 0 : std::vector<const E*> altPath;
266 0 : buildPath(from, to, fromTaz, toTaz, altPath);
267 0 : visited += (int)altPath.size();
268 0 : if (this->recomputeCosts(altPath, vehicle, msTime)
269 0 : < this->recomputeCosts(path, vehicle, msTime)) {
270 : path.swap(altPath);
271 : }
272 0 : }
273 : }
274 : }
275 79754 : into.insert(into.end(), path.begin(), path.end());
276 : this->endQuery(visited);
277 : return true;
278 79920 : }
279 :
280 : /// @brief prohibitions: a closure that is already a live permission change
281 : /// is served by the per-class metric (CCH); anything else routes via the
282 : /// exact fallback. Keep our own copy of the set so compute() can classify
283 : /// each query -- deliberately NOT delegating to the base implementation,
284 : /// which writes per-edge prohibition state into myEdgeInfos that this
285 : /// router never populates.
286 27291 : void prohibit(const Prohibitions& toProhibit) {
287 : myProhibited = toProhibit;
288 27291 : myProhibitionActive = !toProhibit.empty();
289 27291 : myFallback->prohibit(toProhibit);
290 27291 : }
291 :
292 10 : bool supportsProhibitions() const {
293 10 : return true; // handled by delegating to the fallback
294 : }
295 :
296 161 : void setBulkMode(const bool mode) {
297 : SUMOAbstractRouter<E, V>::setBulkMode(mode);
298 161 : myFallback->setBulkMode(mode);
299 161 : }
300 :
301 : /// @brief keep the fallback reporting through the same handler (duarouter
302 : /// swaps handlers around route repair; CHRouterWrapper propagates likewise)
303 4727 : void setMsgHandler(MsgHandler* const errorMsgHandler) {
304 : SUMOAbstractRouter<E, V>::setMsgHandler(errorMsgHandler);
305 4727 : myFallback->setMsgHandler(errorMsgHandler);
306 4727 : }
307 :
308 : private:
309 : /** @brief Bind the query to @p metric (rebinding only on change), seed
310 : * all sources and targets and run it; true iff a connection was found.
311 : *
312 : * Source seed = the entry edge's OWN centisecond effort. The arc-weight
313 : * convention (arc weight = effort of destination) omits the source
314 : * edge's effort, so choosing the cheapest zone-entry among members
315 : * requires adding it back per source -- otherwise the argmin ignores
316 : * how expensive each entry edge is and picks a different entry than A*.
317 : * Targets seed 0: the arc INTO a target already carries its effort. */
318 79920 : bool runQuery(MetricPtr metric, const std::vector<unsigned>& sources,
319 : const std::vector<unsigned>& targets, const V* const vehicle, double t) {
320 79920 : if (metric != myBoundMetric) {
321 9098 : myQuery.reset(*metric);
322 9098 : myBoundMetric = metric;
323 : } else {
324 70822 : myQuery.reset();
325 : }
326 : const double bigEff = (double)(RoutingKit::inf_weight - 1) / 100.0;
327 159994 : for (const unsigned s : sources) {
328 80074 : const double eff = this->getEffort(myGraph->edgeOf(s), vehicle, t);
329 80074 : const unsigned d = eff < bigEff ? (unsigned)llround(eff * 100.0) : RoutingKit::inf_weight - 1;
330 80074 : myQuery.add_source(s, d);
331 : }
332 160006 : for (const unsigned tt : targets) {
333 80086 : myQuery.add_target(tt, 0);
334 : }
335 79920 : myQuery.run();
336 79920 : return myQuery.get_distance() < RoutingKit::inf_weight;
337 : }
338 :
339 : /// @brief expand the last query's node path, bracketing it with the TAZ
340 : /// connectors where the endpoints are zones
341 79754 : void buildPath(const E* from, const E* to, bool fromTaz, bool toTaz,
342 : std::vector<const E*>& path) {
343 79754 : const std::vector<unsigned> nodePath = myQuery.get_node_path();
344 79754 : if (fromTaz) {
345 249 : path.push_back(from);
346 : }
347 79754 : myGraph->expandNodePath(nodePath, path);
348 79754 : if (toTaz) {
349 264 : path.push_back(to);
350 : }
351 79754 : }
352 :
353 : /** @brief Can the per-class CCH metric already express every edge this
354 : * prohibition set forbids for @p vClass? True iff each forbidden edge is
355 : * ALSO closed for the class in the live network (getPermissions()) -- the
356 : * exact condition fillInputWeights() turns into inf_weight. A prohibited
357 : * edge that still permits the class is an arbitrary per-query prohibition
358 : * no shared metric can encode, so the caller must use the exact fallback.
359 : * (For time-bounded closures A* itself avoids the edge via this same live
360 : * permission signal -- SUMOAbstractRouter::isProhibited -- not the
361 : * per-query branch, so this is faithful to A*'s own behavior.)
362 : */
363 225 : bool prohibitionsCoveredByMetric(SUMOVehicleClass vClass) const {
364 306 : for (const auto& item : myProhibited) {
365 231 : if ((item.second.permissions & vClass) != vClass // forbids vClass here...
366 231 : && (item.first->getPermissions() & vClass) != 0) { // ...but edge still permits it live
367 : return false;
368 : }
369 : }
370 : return true;
371 : }
372 :
373 : private:
374 : const GRAPH* myGraph; // shared, immutable, not owned
375 : MetricProvider myMetricProvider;
376 : RoutingKit::CustomizableContractionHierarchyQuery myQuery; // per-clone scratch
377 : MetricPtr myBoundMetric = nullptr; // metric myQuery is currently bound to
378 : SUMOAbstractRouter<E, V>* myFallback; // owned
379 : PeriodEnd myPeriodEnd; // may be nullptr (static weights)
380 : ResetHook myOnReset; // may be nullptr (nobody to notify)
381 : bool myProhibitionActive;
382 : Prohibitions myProhibited; // last set installed via prohibit()
383 :
384 : private:
385 : CCHRouter& operator=(const CCHRouter&) = delete;
386 : };
|
