1 /****************************************************************************/ 2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo 3 // Copyright (C) 2006-2019 German Aerospace Center (DLR) and others. 4 // This program and the accompanying materials 5 // are made available under the terms of the Eclipse Public License v2.0 6 // which accompanies this distribution, and is available at 7 // http://www.eclipse.org/legal/epl-v20.html 8 // SPDX-License-Identifier: EPL-2.0 9 /****************************************************************************/ 10 /// @file SUMOAbstractRouter.h 11 /// @author Daniel Krajzewicz 12 /// @author Michael Behrisch 13 /// @author Jakob Erdmann 14 /// @date 25.Jan 2006 15 /// @version $Id$ 16 /// 17 // An abstract router base class 18 /****************************************************************************/ 19 #ifndef SUMOAbstractRouter_h 20 #define SUMOAbstractRouter_h 21 22 23 // =========================================================================== 24 // included modules 25 // =========================================================================== 26 #include <config.h> 27 28 #include <string> 29 #include <vector> 30 #include <algorithm> 31 #include <iterator> 32 #include <assert.h> 33 #include <utils/common/SysUtils.h> 34 #include <utils/common/MsgHandler.h> 35 #include <utils/common/SUMOTime.h> 36 #include <utils/common/ToString.h> 37 38 39 // =========================================================================== 40 // class definitions 41 // =========================================================================== 42 /** 43 * @class SUMOAbstractRouter 44 * The interface for routing the vehicles over the network. 45 */ 46 template<class E, class V> 47 class SUMOAbstractRouter { 48 public: 49 /** 50 * @class EdgeInfo 51 * A definition about a route's edge with the effort needed to reach it and 52 * the information about the previous edge. 53 */ 54 class EdgeInfo { 55 public: 56 /// Constructor EdgeInfo(const E * const e)57 EdgeInfo(const E* const e) 58 : edge(e), effort(std::numeric_limits<double>::max()), 59 heuristicEffort(std::numeric_limits<double>::max()), 60 leaveTime(0.), prev(nullptr), visited(false) {} 61 62 /// The current edge 63 const E* const edge; 64 65 /// Effort to reach the edge 66 double effort; 67 68 /// Estimated effort to reach the edge (effort + lower bound on remaining effort) 69 // only used by A* 70 double heuristicEffort; 71 72 /// The time the vehicle leaves the edge 73 double leaveTime; 74 75 /// The previous edge 76 const EdgeInfo* prev; 77 78 /// The previous edge 79 bool visited; 80 reset()81 inline void reset() { 82 effort = std::numeric_limits<double>::max(); 83 heuristicEffort = std::numeric_limits<double>::max(); 84 visited = false; 85 } 86 87 private: 88 /// @brief Invalidated assignment operator 89 EdgeInfo& operator=(const EdgeInfo& s) = delete; 90 91 }; 92 93 /// Type of the function that is used to retrieve the edge effort. 94 typedef double(* Operation)(const E* const, const V* const, double); 95 96 /// Constructor 97 SUMOAbstractRouter(const std::string& type, bool unbuildIsWarning, Operation operation = nullptr, Operation ttOperation = nullptr) : 98 myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()), 99 myOperation(operation), myTTOperation(ttOperation), 100 myBulkMode(false), 101 myType(type), 102 myQueryVisits(0), 103 myNumQueries(0), 104 myQueryStartTime(0), 105 myQueryTimeSum(0) { 106 } 107 108 /// Destructor ~SUMOAbstractRouter()109 virtual ~SUMOAbstractRouter() { 110 if (myNumQueries > 0) { 111 WRITE_MESSAGE(myType + " answered " + toString(myNumQueries) + " queries and explored " + toString(double(myQueryVisits) / myNumQueries) + " edges on average."); 112 WRITE_MESSAGE(myType + " spent " + toString(myQueryTimeSum) + "ms answering queries (" + toString(double(myQueryTimeSum) / myNumQueries) + "ms on average)."); 113 } 114 } 115 116 virtual SUMOAbstractRouter* clone() = 0; 117 118 /** @brief Builds the route between the given edges using the minimum effort at the given time 119 The definition of the effort depends on the wished routing scheme */ 120 virtual bool compute(const E* from, const E* to, const V* const vehicle, 121 SUMOTime msTime, std::vector<const E*>& into, bool silent = false) = 0; 122 123 /** @brief Builds the route between the given edges using the minimum effort at the given time 124 * if from == to, return the shortest looped route */ 125 bool computeLooped(const E* from, const E* to, const V* const vehicle, 126 SUMOTime msTime, std::vector<const E*>& into, bool silent = false) { 127 if (from != to) { 128 return compute(from, to, vehicle, msTime, into, silent); 129 } 130 double minEffort = std::numeric_limits<double>::max(); 131 std::vector<const E*> best; 132 const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass(); 133 for (const std::pair<const E*, const E*>& follower : from->getViaSuccessors(vClass)) { 134 std::vector<const E*> tmp; 135 compute(follower.first, to, vehicle, msTime, tmp, true); 136 if (tmp.size() > 0) { 137 double effort = recomputeCosts(tmp, vehicle, msTime); 138 if (effort < minEffort) { 139 minEffort = effort; 140 best = tmp; 141 } 142 } 143 } 144 if (minEffort != std::numeric_limits<double>::max()) { 145 into.push_back(from); 146 std::copy(best.begin(), best.end(), std::back_inserter(into)); 147 return true; 148 } else if (!silent && myErrorMsgHandler != nullptr) { 149 myErrorMsgHandler->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found."); 150 } 151 return false; 152 } 153 isProhibited(const E * const,const V * const)154 virtual bool isProhibited(const E* const /* edge */, const V* const /* vehicle */) const { 155 return false; 156 } 157 158 getTravelTime(const E * const e,const V * const v,const double t,const double effort)159 inline double getTravelTime(const E* const e, const V* const v, const double t, const double effort) const { 160 return myTTOperation == nullptr ? effort : (*myTTOperation)(e, v, t); 161 } 162 updateViaEdgeCost(const E * viaEdge,const V * const v,double & time,double & effort,double & length)163 inline void updateViaEdgeCost(const E* viaEdge, const V* const v, double& time, double& effort, double& length) const { 164 while (viaEdge != nullptr && viaEdge->isInternal()) { 165 const double viaEffortDelta = this->getEffort(viaEdge, v, time); 166 time += getTravelTime(viaEdge, v, time, viaEffortDelta); 167 effort += viaEffortDelta; 168 length += viaEdge->getLength(); 169 viaEdge = viaEdge->getViaSuccessors().front().second; 170 } 171 } 172 updateViaCost(const E * const prev,const E * const e,const V * const v,double & time,double & effort,double & length)173 inline void updateViaCost(const E* const prev, const E* const e, const V* const v, double& time, double& effort, double& length) const { 174 if (prev != nullptr) { 175 for (const std::pair<const E*, const E*>& follower : prev->getViaSuccessors()) { 176 if (follower.first == e) { 177 updateViaEdgeCost(follower.second, v, time, effort, length); 178 break; 179 } 180 } 181 } 182 const double effortDelta = this->getEffort(e, v, time); 183 effort += effortDelta; 184 time += getTravelTime(e, v, time, effortDelta); 185 length += e->getLength(); 186 } 187 188 189 inline double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const { 190 double time = STEPS2TIME(msTime); 191 double effort = 0.; 192 double length = 0.; 193 if (lengthp == nullptr) { 194 lengthp = &length; 195 } else { 196 *lengthp = 0.; 197 } 198 const E* prev = nullptr; 199 for (const E* const e : edges) { 200 if (isProhibited(e, v)) { 201 return -1; 202 } 203 updateViaCost(prev, e, v, time, effort, *lengthp); 204 prev = e; 205 } 206 return effort; 207 } 208 209 getEffort(const E * const e,const V * const v,double t)210 inline double getEffort(const E* const e, const V* const v, double t) const { 211 return (*myOperation)(e, v, t); 212 } 213 startQuery()214 inline void startQuery() { 215 myNumQueries++; 216 myQueryStartTime = SysUtils::getCurrentMillis(); 217 } 218 endQuery(int visits)219 inline void endQuery(int visits) { 220 myQueryVisits += visits; 221 myQueryTimeSum += (SysUtils::getCurrentMillis() - myQueryStartTime); 222 } 223 setBulkMode(const bool mode)224 void setBulkMode(const bool mode) { 225 myBulkMode = mode; 226 } 227 228 protected: 229 /// @brief the handler for routing errors 230 MsgHandler* const myErrorMsgHandler; 231 232 /// @brief The object's operation to perform. 233 Operation myOperation; 234 235 /// @brief The object's operation to perform for travel times 236 Operation myTTOperation; 237 238 /// @brief whether we are currently operating several route queries in a bulk 239 bool myBulkMode; 240 241 private: 242 /// @brief the type of this router 243 const std::string myType; 244 245 /// @brief counters for performance logging 246 long long int myQueryVisits; 247 long long int myNumQueries; 248 /// @brief the time spent querying in milliseconds 249 long long int myQueryStartTime; 250 long long int myQueryTimeSum; 251 private: 252 /// @brief Invalidated assignment operator 253 SUMOAbstractRouter& operator=(const SUMOAbstractRouter& s); 254 }; 255 256 257 template<class E, class V> 258 class SUMOAbstractRouterPermissions : public SUMOAbstractRouter<E, V> { 259 public: 260 /// Constructor 261 SUMOAbstractRouterPermissions(const std::string& type, bool unbuildIsWarning, 262 typename SUMOAbstractRouter<E, V>::Operation operation = nullptr, typename SUMOAbstractRouter<E, V>::Operation ttOperation = nullptr) : 263 SUMOAbstractRouter<E, V>(type, unbuildIsWarning, operation, ttOperation) { 264 } 265 266 /// Destructor ~SUMOAbstractRouterPermissions()267 virtual ~SUMOAbstractRouterPermissions() { 268 } 269 isProhibited(const E * const edge,const V * const vehicle)270 bool isProhibited(const E* const edge, const V* const vehicle) const { 271 if (std::find(myProhibited.begin(), myProhibited.end(), edge) != myProhibited.end()) { 272 return true; 273 } 274 return edge->prohibits(vehicle); 275 } 276 prohibit(const std::vector<E * > & toProhibit)277 void prohibit(const std::vector<E*>& toProhibit) { 278 myProhibited = toProhibit; 279 } 280 281 protected: 282 std::vector<E*> myProhibited; 283 284 }; 285 286 287 #endif 288 289 /****************************************************************************/ 290