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