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 CCHGraph.h
15 : /// @author Pranav Sateesh
16 : /// @date 2026
17 : ///
18 : // Edge-graph <-> RoutingKit CCH graph mapping, shared between the
19 : // simulation (CCHGraph over MSEdge) and duarouter (RODUACCHGraph over
20 : // ROEdge) -- the GRAPH template argument of CCHRouter.
21 : //
22 : // RoutingKit node = one non-internal, non-taz edge (densely re-indexed).
23 : // RoutingKit arc = one edge-to-edge connection (u -> to) from
24 : // getViaSuccessors, with any internal/via edge chain
25 : // between them folded into the arc weight.
26 : //
27 : // The topology (arcs/order/CCH) is metric-INDEPENDENT and built once from
28 : // the class-union successor sets. Weights are metric-DEPENDENT centisecond
29 : // integers recomputed from the caller's effort function (fillInputWeights /
30 : // computeArcWeight); forbidden arcs get exactly RoutingKit::inf_weight so
31 : // the arc set (topology) never changes.
32 : //
33 : // ARC WEIGHT CONVENTION (load-bearing):
34 : // w(u -> to) = round(100 * ( viaEffort(u..to) + effort(to) )) [centiseconds]
35 : // so a path u0->u1->...->uk sums arc weights = via + effort(u1..uk), and the
36 : // FULL route cost equals query_distance + effort(u0) (the source edge's
37 : // own effort, added back by the caller as the source seed). This is NOT
38 : // round(100*recomputeCosts({u,to})): that would double-count effort(u) on
39 : // every hop of a multi-edge path.
40 : /****************************************************************************/
41 : #pragma once
42 : #include <config.h>
43 :
44 : #include <cmath>
45 : #include <limits>
46 : #include <map>
47 : #include <vector>
48 : #include <utils/common/MsgHandler.h>
49 : #include <utils/common/StdDefs.h>
50 : #include <utils/common/SUMOVehicleClass.h>
51 : #include <utils/common/ToString.h>
52 : #include <utils/geom/GeoConvHelper.h>
53 : #include <utils/geom/Position.h>
54 : #ifdef __GNUC__
55 : #pragma GCC diagnostic push
56 : #pragma GCC diagnostic ignored "-Wunused-parameter"
57 : #endif
58 : #ifdef _MSC_VER
59 : #pragma warning(push)
60 : #pragma warning(disable: 4267 4458)
61 : #endif
62 : #include <routingkit/customizable_contraction_hierarchy.h>
63 : #include <routingkit/nested_dissection.h>
64 : #ifdef _MSC_VER
65 : #pragma warning(pop)
66 : #endif
67 : #ifdef __GNUC__
68 : #pragma GCC diagnostic pop
69 : #endif
70 :
71 : // #define CCH_DEBUG
72 :
73 :
74 : // ===========================================================================
75 : // class definitions
76 : // ===========================================================================
77 : /**
78 : * @class CCHGraph
79 : * @brief Metric-independent RoutingKit CCH topology over the PURE road graph.
80 : *
81 : * Nodes are the non-internal, non-TAZ edges. TAZ connectors are deliberately
82 : * NOT nodes: a connector is a high-degree "star" (it links every member edge
83 : * of its zone), and eliminating a degree-d node in a contraction hierarchy
84 : * forms a d-clique => treewidth >= d, which poisons the whole hierarchy
85 : * regardless of elimination order. Instead, TAZ connectors are kept host-side
86 : * as query-time source/target SETS (the "phantom node" pattern) and resolved
87 : * with RoutingKit's native multi-source/multi-target query.
88 : *
89 : * Build once at start; hold a single owned instance and hand out a const
90 : * reference to every router clone (the CustomizableContractionHierarchy is
91 : * read-only after construction and safe to share across threads).
92 : *
93 : * @tparam E the edge type (MSEdge / ROEdge)
94 : * @tparam V the vehicle type of the effort callback (SUMOVehicle / ROVehicle)
95 : */
96 : template<class E, class V>
97 : class CCHGraph {
98 : public:
99 : /// @brief effort callback signature, matching SUMOAbstractRouter::Operation
100 : typedef double (*EffortOperation)(const E* const, const V* const, double);
101 :
102 : /// @brief sentinel for "not a routable node"
103 : static const unsigned INVALID_NODE;
104 :
105 : /** @brief Build the union line graph + CCH from the given edges.
106 : *
107 : * Arcs come from getViaSuccessors(SVC_IGNORING) (the raw, unfiltered
108 : * successor set): the arc set must be class-independent so every class
109 : * (including e.g. tram-only rail arcs) exists. Per-class permissions are
110 : * applied later as inf_weight in the metric, never by removing arcs.
111 : */
112 860 : explicit CCHGraph(const std::vector<E*>& allEdges) {
113 : // 1. dense node indexing over real (non-internal, non-taz) edges.
114 : unsigned maxNumID = 0;
115 49441 : for (const E* e : allEdges) {
116 48581 : maxNumID = MAX2(maxNumID, (unsigned)e->getNumericalID());
117 : }
118 860 : myEdgeToNode.assign(maxNumID + 1, INVALID_NODE);
119 49441 : for (const E* e : allEdges) {
120 : // excluded are junction-internal edges and the district STAR
121 : // connectors ("<taz>-source"/"-sink", the high-degree phantom
122 : // edges -- see the class documentation). Legacy net edges with
123 : // function="connector" are ordinary routable geometry for the
124 : // exact routers and therefore stay ordinary nodes here; only the
125 : // paired district connectors (identified by their
126 : // otherTazConnector link) are kept out of the hierarchy.
127 48581 : if (e->isInternal() || isStarConnector(e)) {
128 32963 : continue;
129 : }
130 15618 : const unsigned node = (unsigned)myNodeToEdge.size();
131 15618 : myEdgeToNode[e->getNumericalID()] = node;
132 15618 : myNodeToEdge.push_back(e);
133 : }
134 860 : const unsigned nNodes = (unsigned)myNodeToEdge.size();
135 :
136 : // 2. arcs from the union successors; coordinates for the orderer.
137 860 : std::vector<float> lon(nNodes);
138 860 : std::vector<float> lat(nNodes);
139 16478 : for (unsigned n = 0; n < nNodes; n++) {
140 15618 : const E* e = myNodeToEdge[n];
141 : Position p;
142 15618 : if (!e->getLanes().empty()) {
143 15618 : p = e->getLanes()[0]->geometryPositionAtOffset(e->getLength() * 0.5);
144 : } else {
145 0 : const auto* j = e->getToJunction() != nullptr ? e->getToJunction() : e->getFromJunction();
146 0 : p = (j != nullptr) ? j->getPosition() : Position(0., 0.);
147 : }
148 15618 : if (GeoConvHelper::getFinal().usingGeoProjection()) {
149 1443 : GeoConvHelper::getFinal().cartesian2geo(p);
150 : }
151 15618 : lon[n] = (float)p.x();
152 15618 : lat[n] = (float)p.y();
153 : }
154 16478 : for (unsigned n = 0; n < nNodes; n++) {
155 15618 : const E* u = myNodeToEdge[n];
156 51516 : for (const auto& follower : u->getViaSuccessors(SVC_IGNORING)) {
157 35898 : const E* to = follower.first;
158 35898 : if (to == nullptr || to->getNumericalID() >= (int)myEdgeToNode.size()) {
159 1510 : continue;
160 : }
161 35898 : const unsigned toNode = myEdgeToNode[to->getNumericalID()];
162 35898 : if (toNode == INVALID_NODE) {
163 1510 : continue; // successor is internal/taz -> not a routable node
164 : }
165 34388 : myArcOf[std::make_pair(n, toNode)] = (unsigned)myArcTail.size();
166 34388 : myArcTail.push_back(n);
167 34388 : myArcHead.push_back(toNode);
168 34388 : myArcVia.push_back(follower.second); // leading internal edge or nullptr
169 : }
170 : }
171 860 : myArcPerm.assign(myArcTail.size(), 0);
172 860 : myPrimedClasses = 0;
173 : // 2b. reverse image for sparse re-customization: for every arc, the
174 : // edges its weight reads at fill time (head edge + folded via chain;
175 : // the tail edge is deliberately absent from the weight, see the arc
176 : // weight convention above)
177 860 : myEdgeToArcs.resize(myEdgeToNode.size());
178 35248 : for (unsigned a = 0; a < (unsigned)myArcHead.size(); a++) {
179 34388 : myEdgeToArcs[myNodeToEdge[myArcHead[a]]->getNumericalID()].push_back(a);
180 34388 : const E* via = myArcVia[a];
181 64854 : while (via != nullptr && via->isInternal()) {
182 30466 : if (via->getNumericalID() >= 0 && via->getNumericalID() < (int)myEdgeToArcs.size()) {
183 30466 : myEdgeToArcs[via->getNumericalID()].push_back(a);
184 : }
185 30466 : const auto& vs = via->getViaSuccessors();
186 30466 : via = vs.empty() ? nullptr : vs.front().second;
187 : }
188 : }
189 :
190 : // 3. TAZ member sets (query-time "phantom nodes"): successors for a
191 : // source connector (entry edges), predecessors for a sink connector.
192 51565 : for (const E* e : allEdges) {
193 46457 : if (!isStarConnector(e)) {
194 46457 : continue;
195 : }
196 732 : std::vector<unsigned> srcNodes;
197 3641 : for (const auto& follower : e->getViaSuccessors(SVC_IGNORING)) {
198 3034 : const unsigned m = nodeOf(follower.first);
199 1517 : if (m != INVALID_NODE) {
200 1517 : srcNodes.push_back(m);
201 : }
202 : }
203 732 : std::vector<unsigned> snkNodes;
204 3634 : for (const E* pred : e->getPredecessors()) {
205 1510 : const unsigned m = nodeOf(pred);
206 1510 : if (m != INVALID_NODE) {
207 1510 : snkNodes.push_back(m);
208 : }
209 : }
210 2124 : if (!srcNodes.empty()) {
211 622 : myTazSrcNodes[e] = std::move(srcNodes);
212 : }
213 2124 : if (!snkNodes.empty()) {
214 619 : myTazSnkNodes[e] = std::move(snkNodes);
215 : }
216 : }
217 :
218 : // 4. metric-independent order + CCH topology (the one-time work).
219 : // @todo persist the order keyed by a network hash (recompute is fast)
220 860 : std::vector<unsigned> order = RoutingKit::compute_nested_node_dissection_order_using_inertial_flow(
221 860 : nNodes, myArcTail, myArcHead, lat, lon);
222 860 : myCCH = RoutingKit::CustomizableContractionHierarchy(order, myArcTail, myArcHead);
223 : #ifdef CCH_DEBUG
224 : std::cout << "CCH: " << nNodes << " road nodes, "
225 : << arcCount() << " arcs, "
226 : << myCCH.cch_arc_count() << " cch-arcs (fill x" << (double)myCCH.cch_arc_count() / MAX2((unsigned)1, arcCount())
227 : << "), " << myTazSrcNodes.size() << " TAZ sources, " << myTazSnkNodes.size() << " TAZ sinks." << std::endl;
228 : #endif
229 1414 : }
230 :
231 1224 : virtual ~CCHGraph() {}
232 :
233 : /// @brief the immutable CCH (share const& across clones)
234 : const RoutingKit::CustomizableContractionHierarchy& cch() const {
235 1355381 : return myCCH;
236 : }
237 :
238 : /// @brief number of input arcs (== number of mapped connections)
239 : unsigned arcCount() const {
240 238443 : return (unsigned)myArcTail.size();
241 : }
242 :
243 : /// @brief size of the edge numerical-id space the graph was built over
244 : /// (for callers keeping per-edge-id side arrays, e.g. CCHMetricFamily)
245 : unsigned edgeIdSpace() const {
246 : return (unsigned)myEdgeToNode.size();
247 : }
248 :
249 : /// @brief RoutingKit node index for an edge, or INVALID_NODE if not a node
250 : unsigned nodeOf(const E* e) const {
251 284942 : if (e == nullptr || e->getNumericalID() < 0 || e->getNumericalID() >= (int)myEdgeToNode.size()) {
252 : return INVALID_NODE;
253 : }
254 284942 : return myEdgeToNode[e->getNumericalID()];
255 : }
256 :
257 : /// @brief the edge backing a RoutingKit node
258 : const E* edgeOf(unsigned node) const {
259 89881 : return myNodeToEdge[node];
260 : }
261 :
262 : /// @brief road member nodes of a TAZ-source connector (its entry edges),
263 : /// to seed multi-SOURCE queries; empty if @p taz is not a known TAZ source.
264 253 : const std::vector<unsigned>& tazSources(const E* taz) const {
265 253 : static const std::vector<unsigned> empty;
266 : const auto it = myTazSrcNodes.find(taz);
267 253 : return it == myTazSrcNodes.end() ? empty : it->second;
268 : }
269 :
270 : /// @brief road member nodes of a TAZ-sink connector (its exit edges),
271 : /// to seed multi-TARGET queries; empty if @p taz is not a known TAZ sink.
272 268 : const std::vector<unsigned>& tazSinks(const E* taz) const {
273 268 : static const std::vector<unsigned> empty;
274 : const auto it = myTazSnkNodes.find(taz);
275 268 : return it == myTazSnkNodes.end() ? empty : it->second;
276 : }
277 :
278 : /// @brief the arcs whose weight depends on the given edge (arcs it heads
279 : /// plus arcs whose folded via chain contains it), for sparse
280 : /// re-customization; empty for edges that are not part of the graph
281 7212915 : const std::vector<unsigned>& arcsOfEdge(const E* e) const {
282 7212915 : static const std::vector<unsigned> empty;
283 7212915 : if (e == nullptr || e->getNumericalID() < 0 || e->getNumericalID() >= (int)myEdgeToArcs.size()) {
284 : return empty;
285 : }
286 7212915 : return myEdgeToArcs[e->getNumericalID()];
287 : }
288 :
289 : /** @brief Map a RoutingKit node path back to the edge sequence.
290 : *
291 : * The result lists REAL edges only, exactly like the exact routers:
292 : * junction-internal edges are never part of SUMO route vectors -- their
293 : * cost is folded into the arc weights for the query and re-added from
294 : * consecutive real edges by SUMOAbstractRouter::recomputeCosts. */
295 79754 : void expandNodePath(const std::vector<unsigned>& nodePath,
296 : std::vector<const E*>& into) const {
297 79754 : into.reserve(into.size() + nodePath.size());
298 442880 : for (unsigned node : nodePath) {
299 363126 : into.push_back(myNodeToEdge[node]);
300 : }
301 79754 : }
302 :
303 : /// @brief effort accumulated crossing the internal/via chain that leads from
304 : /// one real edge onto its successor (mirrors SUMOAbstractRouter::updateViaEdgeCost).
305 16453314 : static double viaChainEffort(const E* via, EffortOperation effort,
306 : const V* veh, double time) {
307 : double sum = 0.;
308 37232037 : while (via != nullptr && via->isInternal()) {
309 20778723 : sum += effort(via, veh, time);
310 20778723 : const auto& vs = via->getViaSuccessors();
311 20778723 : via = vs.empty() ? nullptr : vs.front().second;
312 : }
313 16453314 : return sum;
314 : }
315 :
316 : public:
317 : /** @brief Recompute the input weight of one arc -- the exact per-arc body
318 : * of fillInputWeights (same masking, folding and rounding), exposed so a
319 : * sparse update can refresh only the arcs of edges that actually moved.
320 : *
321 : * Forbidden (inf_weight) if EITHER the connection does not permit the
322 : * class (static, connection-level, matches getViaSuccessors(vClass); see
323 : * primeClassMask) OR the destination edge does not currently permit the
324 : * class (dynamic, edge-level -- catches runtime closures via
325 : * MSLane::setPermissions; a no-op where permissions are static). */
326 17170289 : unsigned computeArcWeight(unsigned a, EffortOperation effort, SUMOVehicleClass maskClass,
327 : const V* veh, double time) const {
328 : if (maskClass != SVC_IGNORING
329 17170289 : && (((myArcPerm[a] & maskClass) == 0)
330 16453284 : || ((edgeOf(myArcHead[a])->getPermissions() & maskClass) == 0))) {
331 : return RoutingKit::inf_weight;
332 : }
333 16453314 : return computeArcWeightRaw(a, effort, veh, time);
334 : }
335 :
336 : /** @brief Fill a centisecond input-weight buffer for one vehicle class.
337 : *
338 : * Primes the class's connection mask on first use (see primeClassMask for
339 : * the synchronization contract), then applies computeArcWeight per arc.
340 : * @param[in] effort the effort Operation
341 : * @param[in] maskClass arcs whose connection or destination edge does NOT
342 : * permit this class become inf_weight; SVC_IGNORING masks nothing
343 : * @param[in] veh reference vehicle for the effort floor (may be null)
344 : * @param[in] time seconds, passed to the effort fn
345 : * @param[out] weight resized to arcCount(); w[a] in [0, inf_weight]
346 : */
347 3518 : void fillInputWeights(EffortOperation effort, SUMOVehicleClass maskClass,
348 : const V* veh, double time,
349 : std::vector<unsigned>& weight) const {
350 3518 : primeClassMask(maskClass);
351 3518 : weight.resize(arcCount());
352 238443 : for (unsigned a = 0; a < arcCount(); a++) {
353 234925 : weight[a] = computeArcWeight(a, effort, maskClass, veh, time);
354 : }
355 3518 : }
356 :
357 : /** @brief Drop every primed connection mask so the next fill re-primes
358 : * from the CURRENT successor lists.
359 : *
360 : * Runtime permission changes (closingReroute / closingLaneReroute) alter
361 : * getViaSuccessors(vClass); a mask primed before the change keeps serving
362 : * the old connection set -- a closure active at first customize would
363 : * even outlive its re-opening. Same synchronization contract as
364 : * primeClassMask: call only while no query is in flight. */
365 : void invalidateClassMasks() const {
366 43 : myArcPerm.assign(myArcPerm.size(), 0);
367 43 : myPrimedClasses = 0;
368 : }
369 :
370 : private:
371 : /// @brief whether the edge is a district star connector (the paired
372 : /// "<taz>-source"/"-sink" phantom edge) as opposed to a legacy
373 : /// function="connector" net edge, which stays routable
374 : static bool isStarConnector(const E* e) {
375 66323 : return e->isTazConnector() && e->getOtherTazConnector() != nullptr;
376 : }
377 :
378 : /** @brief Record which arcs @p vClass may traverse in the per-arc
379 : * CONNECTION-level permission bitmask -- exactly the arcs
380 : * getViaSuccessors(vClass) yields (edge-level getPermissions() is too
381 : * coarse on mixed-lane edges). No-op if the class was primed before.
382 : *
383 : * NOT internally synchronized: concurrent calls for an unprimed class
384 : * must be serialized by the caller. In practice the simulation primes on
385 : * the main thread at the customization barrier (no query in flight) and
386 : * duarouter primes under the RODUACCHMetrics mutex; primed classes make
387 : * this a lock-free bit test on the hot path. */
388 3518 : void primeClassMask(SUMOVehicleClass vClass) const {
389 3518 : if (vClass == SVC_IGNORING || (myPrimedClasses & vClass) == vClass) {
390 : return;
391 : }
392 48597 : for (unsigned n = 0; n < (unsigned)myNodeToEdge.size(); n++) {
393 168790 : for (const auto& follower : myNodeToEdge[n]->getViaSuccessors(vClass)) {
394 122075 : const unsigned toNode = nodeOf(follower.first);
395 122075 : if (toNode == INVALID_NODE) {
396 : continue;
397 : }
398 117496 : const auto it = myArcOf.find(std::make_pair(n, toNode));
399 117496 : if (it != myArcOf.end()) {
400 117496 : myArcPerm[it->second] |= (SVCPermissions)vClass;
401 : }
402 : }
403 : }
404 1882 : myPrimedClasses |= (SVCPermissions)vClass;
405 : }
406 :
407 : /** @brief The unmasked weight of one arc: via-chain effort + head-edge
408 : * effort, rounded to centiseconds and clamped below inf_weight (NaN /
409 : * inf / overflow become inf_weight = forbidden). */
410 16453314 : unsigned computeArcWeightRaw(unsigned a, EffortOperation effort,
411 : const V* veh, double time) const {
412 16453314 : const E* to = myNodeToEdge[myArcHead[a]];
413 : const double bigEffort = (double)(RoutingKit::inf_weight - 1) / 100.0;
414 16453314 : const double eff = viaChainEffort(myArcVia[a], effort, veh, time)
415 16453314 : + effort(to, veh, time);
416 16453314 : if (!(eff < bigEffort)) {
417 : return RoutingKit::inf_weight;
418 : }
419 16453314 : const long long cs = std::llround(eff * 100.0);
420 : return (unsigned)(cs < 0 ? 0 : (cs >= (long long)RoutingKit::inf_weight
421 16453314 : ? RoutingKit::inf_weight - 1 : cs));
422 : }
423 :
424 : /// @brief node index -> backing edge
425 : std::vector<const E*> myNodeToEdge;
426 : /// @brief edge numerical id -> node index (INVALID_NODE if not a node)
427 : std::vector<unsigned> myEdgeToNode;
428 : /// @brief per-arc endpoints
429 : std::vector<unsigned> myArcTail;
430 : std::vector<unsigned> myArcHead;
431 : /// @brief per-arc leading via/internal edge (nullptr if none) for path re-expansion
432 : std::vector<const E*> myArcVia;
433 : /// @brief (tail node, head node) -> arc index
434 : std::map<std::pair<unsigned, unsigned>, unsigned> myArcOf;
435 : /// @brief per-arc CONNECTION-level permission bitmask, accumulated per
436 : /// primed class (see primeClassMask); mutable lazy cache
437 : mutable std::vector<SVCPermissions> myArcPerm;
438 : /// @brief the classes already primed into myArcPerm
439 : mutable SVCPermissions myPrimedClasses;
440 : /// @brief edge numerical id -> arcs whose weight reads that edge (head +
441 : /// folded via edges); the reverse image of computeArcWeightRaw's inputs
442 : std::vector<std::vector<unsigned> > myEdgeToArcs;
443 : /// @brief TAZ-source connector edge -> its entry-edge road node ids
444 : std::map<const E*, std::vector<unsigned> > myTazSrcNodes;
445 : /// @brief TAZ-sink connector edge -> its exit-edge road node ids
446 : std::map<const E*, std::vector<unsigned> > myTazSnkNodes;
447 : /// @brief the immutable hierarchy
448 : RoutingKit::CustomizableContractionHierarchy myCCH;
449 :
450 : private:
451 : CCHGraph(const CCHGraph&) = delete;
452 : CCHGraph& operator=(const CCHGraph&) = delete;
453 : };
454 :
455 :
456 : template<class E, class V>
457 : const unsigned CCHGraph<E, V>::INVALID_NODE = RoutingKit::invalid_id;
|
