 |
Eclipse SUMO - Simulation of Urban MObility
|
Go to the documentation of this file.
60 template<
class E,
class V>
77 for (
const E*
const e : edges) {
82 inline bool found(
const E*
const edge)
const {
103 return nod1->
edge->getNumericalID() > nod2->
edge->getNumericalID();
110 void init(
const E*
const start,
const V*
const vehicle) {
111 assert(vehicle != 0);
123 startInfo->effort = 0.;
124 startInfo->prev =
nullptr;
140 const E*
const minEdge = minimumInfo->edge;
141 #ifdef CHRouter_DEBUG_QUERY
142 std::cout <<
"DEBUG: " << (
myAmForward ?
"Forward" :
"Backward") <<
" hit '" << minEdge->getID() <<
"' Q: ";
143 for (
typename std::vector<EdgeInfo*>::iterator it =
myFrontier.begin(); it !=
myFrontier.end(); it++) {
144 std::cout << (*it)->traveltime <<
"," << (*it)->edge->getID() <<
" ";
148 if (otherSearch.
found(minEdge)) {
149 const auto*
const otherInfo = otherSearch.
getEdgeInfo(minEdge);
150 const double ttSeen = minimumInfo->effort + otherInfo->effort;
151 #ifdef CHRouter_DEBUG_QUERY
152 std::cout <<
"DEBUG: " << (
myAmForward ?
"Forward" :
"Backward") <<
"-Search hit other search at '" << minEdge->getID() <<
"', tt: " << ttSeen <<
" \n";
154 if (ttSeen < minTTSeen) {
157 meeting.first = minimumInfo;
158 meeting.second = otherInfo;
160 meeting.first = otherInfo;
161 meeting.second = minimumInfo;
166 minimumInfo->visited =
true;
168 myFound.insert(minimumInfo->edge);
169 for (
const auto& uplink : uplinks[minEdge->getNumericalID()]) {
170 const auto upwardInfo = &
myEdgeInfos[uplink.target];
171 const double effort = minimumInfo->effort + uplink.cost;
174 if ((uplink.permissions & svc) != svc) {
177 const double oldEffort = upwardInfo->effort;
178 if (!upwardInfo->visited && effort < oldEffort) {
179 upwardInfo->effort = effort;
180 upwardInfo->prev = minimumInfo;
181 if (oldEffort == std::numeric_limits<double>::max()) {
203 std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*>
myFrontier;
207 std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo>
myEdgeInfos;
223 const bool havePermissions,
const bool haveRestrictions):
224 SUMOAbstractRouter<E, V>(
"CHRouter", unbuildIsWarning, operation, nullptr, havePermissions, haveRestrictions),
255 virtual bool compute(
const E* from,
const E* to,
const V*
const vehicle,
256 SUMOTime msTime, std::vector<const E*>& into,
bool silent =
false) {
257 assert(from != 0 && to != 0);
270 double minTTSeen = std::numeric_limits<double>::max();
271 Meeting meeting(
nullptr,
nullptr);
272 bool continueForward =
true;
273 bool continueBackward =
true;
274 int num_visited_fw = 0;
275 int num_visited_bw = 0;
277 while (continueForward || continueBackward) {
278 if (continueForward) {
282 if (continueBackward) {
287 if (minTTSeen < std::numeric_limits<double>::max()) {
295 #ifdef CHRouter_DEBUG_QUERY_PERF
296 std::cout <<
"visited " << num_visited_fw + num_visited_bw <<
" edges (" << num_visited_fw <<
"," << num_visited_bw <<
") ,final path length: " +
toString(into.size()) +
")\n";
298 this->
endQuery(num_visited_bw + num_visited_fw);
306 std::deque<const E*> tmp;
307 const auto* backtrack = meeting.first;
308 while (backtrack != 0) {
309 tmp.push_front((E*) backtrack->edge);
310 backtrack = backtrack->prev;
312 backtrack = meeting.second->prev;
313 while (backtrack != 0) {
314 tmp.push_back((E*) backtrack->edge);
315 backtrack = backtrack->prev;
319 while (!tmp.empty()) {
320 const E* cur = tmp.front();
326 const E* via =
getVia(prev, cur);
353 const E*
getVia(
const E* forwardFrom,
const E* forwardTo)
const {
std::pair< const E *, const E * > ConstEdgePair
EdgeInfoByTTComparator myComparator
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFrontier
the min edge heap
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
const SUMOTime myWeightPeriod
the validity duration of one weight interval
std::pair< const typename SUMOAbstractRouter< E, V >::EdgeInfo *, const typename SUMOAbstractRouter< E, V >::EdgeInfo * > Meeting
A meeting point of the two search scopes.
const bool myHavePermissions
whether edge permissions need to be considered
const CHBuilder< E, V >::Hierarchy * myHierarchy
CHRouter(const std::vector< E * > &edges, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, const bool havePermissions, const bool haveRestrictions)
Constructor.
virtual ~CHRouter()
Destructor.
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
SUMOTime myValidUntil
the validity duration of the current hierarchy (exclusive)
double effort
Effort to reach the edge.
Operation myOperation
The object's operation to perform.
virtual SUMOAbstractRouter< E, V > * clone()
Unidirectional(const std::vector< E * > &edges, bool forward)
Constructor.
bool myAmForward
the role of this search
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
const bool myHaveRestrictions
whether edge restrictions need to be considered
CHBuilder< E, V > * myHierarchyBuilder
std::set< const E * > myFound
the set of visited (settled) Edges
std::vector< typename CHBuilder< E, V >::Connection > ConnectionVector
const E *const edge
The current edge.
void buildPathFromMeeting(Meeting meeting, std::vector< const E * > &into) const
normal routing methods
void endQuery(int visits)
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Computes the shortest path through a contracted network.
const std::vector< E * > & myEdges
all edges with numerical ids
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > myEdgeInfos
The container of edge information.
const SUMOAbstractRouter< E, V >::EdgeInfo * getEdgeInfo(const E *const edge) const
const E * getVia(const E *forwardFrom, const E *forwardTo) const
SUMOAbstractRouter< E, V >::EdgeInfo * getEdgeInfo(const E *const edge)
void init(const E *const start, const V *const vehicle)
void informf(const std::string &format, T value, Targs... Fargs)
adds a new formatted message
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)
Builds the route between the given edges using the minimum traveltime in the contracted graph.
bool operator()(const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod1, const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod2) const
Comparing method.
bool found(const E *const edge) const
void buildContractionHierarchy(SUMOTime time, const V *const vehicle)
Unidirectional myBackwardSearch
Unidirectional myForwardSearch
the unidirectional search queues
bool step(const std::vector< ConnectionVector > &uplinks, const Unidirectional &otherSearch, double &minTTSeen, Meeting &meeting)
explore on element from the frontier,update minTTSeen and meeting if an EdgeInfo found by the otherSe...