CCHRouter.h

Go to the documentation of this file.

/****************************************************************************/
// Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
// Copyright (C) 2001-2026 German Aerospace Center (DLR) and others.
// This program and the accompanying materials are made available under the
// terms of the Eclipse Public License 2.0 which is available at
// https://www.eclipse.org/legal/epl-2.0/
// This Source Code may also be made available under the following Secondary
// Licenses when the conditions for such availability set forth in the Eclipse
// Public License 2.0 are satisfied: GNU General Public License, version 2
// or later which is available at
// https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
// SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
/****************************************************************************/
// A SUMOAbstractRouter that answers queries via a RoutingKit Customizable
// Contraction Hierarchy over the edge graph. The metric is re-customized
// out-of-band (MSRoutingEngine::adaptEdgeEfforts) and published as a
// shared_ptr snapshot; each query snapshots the current metric, so a
// publish that lands mid-query is safe (double buffer).
//
// Following the AStarRouter<E, V, M> lookup-table pattern, the graph-mapping
// class is the GRAPH template parameter (the simulation supplies its concrete
// mapper, e.g. microsim's CCHGraph), so this header carries no simulation
// dependencies. GRAPH must provide:
//   unsigned nodeOf(const E*)                          (INVALID_NODE if not a node)
//   const E* edgeOf(unsigned node)
//   const std::vector<unsigned>& tazSources(const E*)  (entry-edge node sets)
//   const std::vector<unsigned>& tazSinks(const E*)    (exit-edge node sets)
//   void expandNodePath(const std::vector<unsigned>&, std::vector<const E*>&)
//   static const unsigned INVALID_NODE
//
// Every vehicle class routes on CCH via its own published metric. Closures are
// permission changes the per-class metric encodes as inf_weight once they have
// been customized in; the simulation's metric provider hands out nullptr while
// a permission flip is still pending, so those queries route exactly. The
// embedded A* fallback is used when a class has no (fresh) metric, when the
// vehicle routes on the ORIGINAL permissions (ignoreTransientPermissions --
// the shared metric bakes in the live ones), or when a prohibition is NOT
// expressible as a live permission closure (an arbitrary per-query
// prohibition, which no shared CCH metric can represent) -- see compute() /
// prohibitionsCoveredByMetric().
/****************************************************************************/
#pragma once
#include <config.h>
 
 
#include <memory>
#include <vector>
#include <cmath>
#include <utils/common/Named.h>
#include <utils/common/SUMOTime.h>
#include <utils/common/MsgHandler.h>
#include <utils/common/SUMOVehicleClass.h>
#include <utils/router/SUMOAbstractRouter.h>
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif
#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable: 4267 4458)
#endif
#include <routingkit/customizable_contraction_hierarchy.h>
#ifdef _MSC_VER
#pragma warning(pop)
#endif
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif
 
 
// ===========================================================================
// class definitions
// ===========================================================================
template<class E, class V, class GRAPH>
class CCHRouter : public SUMOAbstractRouter<E, V> {
public:
    typedef const RoutingKit::CustomizableContractionHierarchyMetric* MetricPtr;
    typedef MetricPtr(*MetricProvider)(SUMOVehicleClass, SUMOTime, const V*);
    typedef SUMOTime(*PeriodEnd)(SUMOTime);
    typedef void (*ResetHook)(const V*);
    typedef typename SUMOAbstractRouter<E, V>::Operation Operation;
    typedef typename SUMOAbstractRouter<E, V>::Prohibitions Prohibitions;
 
    CCHRouter(const GRAPH* graph, MetricProvider provider,
              Operation operation, const bool unbuildIsWarning,
              SUMOAbstractRouter<E, V>* fallback,
              PeriodEnd periodEnd = nullptr, ResetHook onReset = nullptr) :
        SUMOAbstractRouter<E, V>("CCHRouter", unbuildIsWarning, operation, nullptr, false, false),
        myGraph(graph), myMetricProvider(provider), myFallback(fallback),
        myPeriodEnd(periodEnd), myOnReset(onReset), myProhibitionActive(false) {
    }
 
    CCHRouter(CCHRouter* other) :
        SUMOAbstractRouter<E, V>(other),
        myGraph(other->myGraph), myMetricProvider(other->myMetricProvider),
        myFallback(other->myFallback->clone()), myPeriodEnd(other->myPeriodEnd),
        myOnReset(other->myOnReset),
        myProhibitionActive(other->myProhibitionActive), myProhibited(other->myProhibited) {
    }
 
    virtual ~CCHRouter() {
        delete myFallback;
    }
 
    virtual SUMOAbstractRouter<E, V>* clone() {
        return new CCHRouter<E, V, GRAPH>(this);
    }
 
    virtual void reset(const V* const vehicle) {
        if (myOnReset != nullptr) {
            myOnReset(vehicle);
        }
        myFallback->reset(vehicle);
    }
 
    bool compute(const E* from, const E* to, const V* const vehicle,
                 SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
        // A CCH query can only avoid an edge the metric already encodes as inf:
        // RoutingKit's query has no per-arc blacklist, and a query-time skip is
        // unsound because shortcut arcs bake in shortest paths THROUGH the edge
        // (SUMO's own CHRouter refuses prohibitions for the same reason). So we
        // run CCH when the metric can express the request and fall back to the
        // exact A* router otherwise: (a) no metric for this class, or (b) an
        // active prohibition that is NOT already a live permission-closure this
        // class's metric encodes (prohibitionsCoveredByMetric).
        const SUMOVehicleClass vClass = vehicle == nullptr ? SVC_PASSENGER : vehicle->getVClass();
        // A vehicle that routes on the ORIGINAL permissions (routing mode bit
        // ROUTING_MODE_IGNORE_TRANSIENT_PERMISSIONS) cannot use the shared
        // metric, which bakes in the LIVE permissions, transient closures
        // included -- route it exactly, like Dijkstra/A* do natively.
        if (vehicle != nullptr && vehicle->ignoreTransientPermissions()) {
            return myFallback->compute(from, to, vehicle, msTime, into, silent);
        }
        MetricPtr metric = myMetricProvider(vClass, msTime, vehicle);
        if (metric == nullptr || (myProhibitionActive && !prohibitionsCoveredByMetric(vClass))) {
            return myFallback->compute(from, to, vehicle, msTime, into, silent);
        }
        // Endpoints -> node SETS: a district star connector expands to its
        // member edges (phantom-node seeding); everything that is a graph
        // node -- including legacy function="connector" net edges -- routes
        // as a single node. TAZ member edges are the class-union set, so
        // filter to edges this class may enter.
        const bool fromTaz = from->isTazConnector() && myGraph->nodeOf(from) == GRAPH::INVALID_NODE;
        const bool toTaz = to->isTazConnector() && myGraph->nodeOf(to) == GRAPH::INVALID_NODE;
        // Mirror the exact routers' endpoint rejection (AStarRouter::compute):
        // an endpoint the vehicle may not use fails loudly instead of quietly
        // seeding a query on it. The metric masks only arcs BETWEEN nodes --
        // the source edge's own closure never enters it (its effort is added
        // as a plain source seed), so without this check a query from a
        // hard-closed edge would "succeed". TAZ members are filtered below.
        if (vehicle != nullptr) {
            if (!fromTaz && from->prohibits(vehicle)) {
                if (!silent && this->myErrorMsgHandler != nullptr) {
                    this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on source edge '" + from->getID() + "'.");
                }
                return false;
            }
            if (!toTaz && to->prohibits(vehicle)) {
                if (!silent && this->myErrorMsgHandler != nullptr) {
                    this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on destination edge '" + to->getID() + "'.");
                }
                return false;
            }
        }
        std::vector<unsigned> srcBuf, tgtBuf;
        const std::vector<unsigned>* sources;
        const std::vector<unsigned>* targets;
        if (fromTaz) {
            for (const unsigned m : myGraph->tazSources(from)) {
                if ((myGraph->edgeOf(m)->getPermissions() & vClass) != 0) {
                    srcBuf.push_back(m);
                }
            }
            sources = &srcBuf;
        } else {
            const unsigned s = myGraph->nodeOf(from);
            if (s != GRAPH::INVALID_NODE) {
                srcBuf.push_back(s);
            }
            sources = &srcBuf;
        }
        if (toTaz) {
            for (const unsigned m : myGraph->tazSinks(to)) {
                if ((myGraph->edgeOf(m)->getPermissions() & vClass) != 0) {
                    tgtBuf.push_back(m);
                }
            }
            targets = &tgtBuf;
        } else {
            const unsigned t = myGraph->nodeOf(to);
            if (t != GRAPH::INVALID_NODE) {
                tgtBuf.push_back(t);
            }
            targets = &tgtBuf;
        }
        if (sources->empty() || targets->empty()) {
            // unmappable endpoint (e.g. internal edge, or a TAZ with no member
            // in this class's graph) -> exact fallback.
            return myFallback->compute(from, to, vehicle, msTime, into, silent);
        }
 
        this->startQuery();
        const double t = STEPS2TIME(msTime);
        if (!runQuery(metric, *sources, *targets, vehicle, t)) {
            this->endQuery(0);
            if (!silent && this->myErrorMsgHandler != nullptr) {
                this->myErrorMsgHandler->informf(TL("No connection between edge '%' and edge '%' found."),
                                                 from->getID(), to->getID());
            }
            return false;
        }
        std::vector<const E*> path;
        buildPath(from, to, fromTaz, toTaz, path);
        int visited = (int)path.size();
        // Weight-period boundary: the metric of the depart period is exact as
        // long as the trip finishes inside that period (efforts are constant
        // within it, and no time-propagated optimum can cross the boundary if
        // this trip does not: any path entering the next period costs at
        // least the remaining period, which already exceeds this result).
        // When the trip does cross, ALSO query the next period's metric and
        // keep whichever path is cheaper under the true time-propagating
        // walk (recomputeCosts). Exact for the common single-crossing case
        // where the optimum follows one period's structure; trips spanning
        // several periods keep the better of the two candidates.
        if (myPeriodEnd != nullptr && myQuery.get_distance() > 0) {
            const SUMOTime boundary = myPeriodEnd(msTime);
            if (boundary != SUMOTime_MAX
                    && msTime + TIME2STEPS((double)myQuery.get_distance() / 100.) >= boundary) {
                MetricPtr altMetric = myMetricProvider(vClass, boundary, vehicle);
                if (altMetric != nullptr && altMetric != metric
                        && runQuery(altMetric, *sources, *targets, vehicle, t)) {
                    std::vector<const E*> altPath;
                    buildPath(from, to, fromTaz, toTaz, altPath);
                    visited += (int)altPath.size();
                    if (this->recomputeCosts(altPath, vehicle, msTime)
                            < this->recomputeCosts(path, vehicle, msTime)) {
                        path.swap(altPath);
                    }
                }
            }
        }
        into.insert(into.end(), path.begin(), path.end());
        this->endQuery(visited);
        return true;
    }
 
    void prohibit(const Prohibitions& toProhibit) {
        myProhibited = toProhibit;
        myProhibitionActive = !toProhibit.empty();
        myFallback->prohibit(toProhibit);
    }
 
    bool supportsProhibitions() const {
        return true;  // handled by delegating to the fallback
    }
 
    void setBulkMode(const bool mode) {
        SUMOAbstractRouter<E, V>::setBulkMode(mode);
        myFallback->setBulkMode(mode);
    }
 
    void setMsgHandler(MsgHandler* const errorMsgHandler) {
        SUMOAbstractRouter<E, V>::setMsgHandler(errorMsgHandler);
        myFallback->setMsgHandler(errorMsgHandler);
    }
 
private:
    bool runQuery(MetricPtr metric, const std::vector<unsigned>& sources,
                  const std::vector<unsigned>& targets, const V* const vehicle, double t) {
        if (metric != myBoundMetric) {
            myQuery.reset(*metric);
            myBoundMetric = metric;
        } else {
            myQuery.reset();
        }
        const double bigEff = (double)(RoutingKit::inf_weight - 1) / 100.0;
        for (const unsigned s : sources) {
            const double eff = this->getEffort(myGraph->edgeOf(s), vehicle, t);
            const unsigned d = eff < bigEff ? (unsigned)llround(eff * 100.0) : RoutingKit::inf_weight - 1;
            myQuery.add_source(s, d);
        }
        for (const unsigned tt : targets) {
            myQuery.add_target(tt, 0);
        }
        myQuery.run();
        return myQuery.get_distance() < RoutingKit::inf_weight;
    }
 
    void buildPath(const E* from, const E* to, bool fromTaz, bool toTaz,
                   std::vector<const E*>& path) {
        const std::vector<unsigned> nodePath = myQuery.get_node_path();
        if (fromTaz) {
            path.push_back(from);
        }
        myGraph->expandNodePath(nodePath, path);
        if (toTaz) {
            path.push_back(to);
        }
    }
 
    bool prohibitionsCoveredByMetric(SUMOVehicleClass vClass) const {
        for (const auto& item : myProhibited) {
            if ((item.second.permissions & vClass) != vClass          // forbids vClass here...
                    && (item.first->getPermissions() & vClass) != 0) {  // ...but edge still permits it live
                return false;
            }
        }
        return true;
    }
 
private:
    const GRAPH* myGraph;                    // shared, immutable, not owned
    MetricProvider myMetricProvider;
    RoutingKit::CustomizableContractionHierarchyQuery myQuery;  // per-clone scratch
    MetricPtr myBoundMetric = nullptr;       // metric myQuery is currently bound to
    SUMOAbstractRouter<E, V>* myFallback;    // owned
    PeriodEnd myPeriodEnd;                   // may be nullptr (static weights)
    ResetHook myOnReset;                     // may be nullptr (nobody to notify)
    bool myProhibitionActive;
    Prohibitions myProhibited;               // last set installed via prohibit()
 
private:
    CCHRouter& operator=(const CCHRouter&) = delete;
};