68 template<
class E,
class V,
class PF>
73 typedef double(*
Operation)(
const E*
const,
const V*
const, double);
110 typedef std::pair<const EdgeInfo*, const EdgeInfo*>
Meeting;
120 myAmForward(forward),
122 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
123 myEdgeInfos.push_back(
EdgeInfo(*i));
128 return myFound.count(edge) > 0;
132 return &(myEdgeInfos[edge->getNumericalID()]);
136 return &(myEdgeInfos[edge->getNumericalID()]);
148 return nod1->
edge->getNumericalID() > nod2->
edge->getNumericalID();
155 void init(
const E*
const start,
const V*
const vehicle) {
156 assert(vehicle != 0);
158 for (
typename std::vector<EdgeInfo*>::iterator i = myFrontier.begin(); i != myFrontier.end(); i++) {
162 for (
typename std::set<const E*>::const_iterator i = myFound.begin(); i != myFound.end(); i++) {
163 getEdgeInfo(*i)->reset();
167 EdgeInfo* startInfo = getEdgeInfo(start);
170 myFrontier.push_back(startInfo);
179 bool step(
const std::vector<ConnectionVector>& uplinks,
const Unidirectional& otherSearch,
double& minTTSeen, Meeting& meeting) {
181 EdgeInfo*
const minimumInfo = myFrontier.front();
182 pop_heap(myFrontier.begin(), myFrontier.end(), myComparator);
183 myFrontier.pop_back();
185 const E*
const minEdge = minimumInfo->
edge;
186 #ifdef CHRouter_DEBUG_QUERY 187 std::cout <<
"DEBUG: " << (myAmForward ?
"Forward" :
"Backward") <<
" hit '" << minEdge->getID() <<
"' Q: ";
188 for (
typename std::vector<EdgeInfo*>::iterator it = myFrontier.begin(); it != myFrontier.end(); it++) {
189 std::cout << (*it)->traveltime <<
"," << (*it)->edge->getID() <<
" ";
193 if (otherSearch.
found(minEdge)) {
196 #ifdef CHRouter_DEBUG_QUERY 197 std::cout <<
"DEBUG: " << (myAmForward ?
"Forward" :
"Backward") <<
"-Search hit other search at '" << minEdge->getID() <<
"', tt: " << ttSeen <<
" \n";
199 if (ttSeen < minTTSeen) {
202 meeting.first = minimumInfo;
203 meeting.second = otherInfo;
205 meeting.first = otherInfo;
206 meeting.second = minimumInfo;
213 myFound.insert(minimumInfo->
edge);
214 const ConnectionVector& upward = uplinks[minEdge->getNumericalID()];
215 for (
typename ConnectionVector::const_iterator it = upward.begin(); it != upward.end(); it++) {
216 EdgeInfo* upwardInfo = &myEdgeInfos[it->target];
220 if ((it->permissions & svc) != svc) {
223 const double oldTraveltime = upwardInfo->
traveltime;
224 if (!upwardInfo->
visited && traveltime < oldTraveltime) {
226 upwardInfo->
prev = minimumInfo;
228 myFrontier.push_back(upwardInfo);
229 push_heap(myFrontier.begin(), myFrontier.end(), myComparator);
231 push_heap(myFrontier.begin(),
232 find(myFrontier.begin(), myFrontier.end(), upwardInfo) + 1,
242 return !myFrontier.empty() && myFrontier.front()->traveltime < minTTSeen;
269 bool validatePermissions):
321 virtual bool compute(
const E* from,
const E* to,
const V*
const vehicle,
322 SUMOTime msTime, std::vector<const E*>& into) {
323 assert(from != 0 && to != 0);
337 Meeting meeting(static_cast<EdgeInfo*>(0), static_cast<EdgeInfo*>(0));
338 bool continueForward =
true;
339 bool continueBackward =
true;
340 int num_visited_fw = 0;
341 int num_visited_bw = 0;
343 while (continueForward || continueBackward) {
344 if (continueForward) {
348 if (continueBackward) {
356 myErrorMsgHandler->
inform(
"No connection between edge '" + from->getID() +
"' and edge '" + to->getID() +
"' found.");
359 #ifdef CHRouter_DEBUG_QUERY_PERF 360 std::cout <<
"visited " << num_visited_fw + num_visited_bw <<
" edges (" << num_visited_fw <<
"," << num_visited_bw <<
") ,final path length: " +
toString(into.size()) +
")\n";
362 this->
endQuery(num_visited_bw + num_visited_fw);
370 for (
typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
371 if (PF::operator()(*i, v)) {
374 costs += this->
getEffort(*i, v, time + costs);
383 std::deque<const E*> tmp;
384 const EdgeInfo* backtrack = meeting.first;
385 while (backtrack != 0) {
386 tmp.push_front((E*) backtrack->
edge);
387 backtrack = backtrack->
prev;
389 backtrack = meeting.second->
prev;
390 while (backtrack != 0) {
391 tmp.push_back((E*) backtrack->
edge);
392 backtrack = backtrack->
prev;
396 while (!tmp.empty()) {
397 const E* cur = tmp.front();
403 const E* via =
getVia(prev, cur);
430 const E*
getVia(
const E* forwardFrom,
const E* forwardTo)
const {
Computes the shortest path through a contracted network.
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
double getEffort(const E *const e, const V *const v, double t) const
double(* Operation)(const E *const, const V *const, double)
Type of the function that is used to retrieve the edge effort.
const SUMOTime myWeightPeriod
the validity duration of one weight interval
EdgeInfo * getEdgeInfo(const E *const edge)
std::vector< typename CHBuilder< E, V >::Connection > ConnectionVector
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
virtual ~CHRouter()
Destructor.
Unidirectional myForwardSearch
the unidirectional search queues
CHBuilder< E, V > * myHierarchyBuilder
std::string time2string(SUMOTime t)
std::vector< EdgeInfo * > myFrontier
the min edge heap
bool visited
Whether the shortest path to this edge is already found.
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
EdgeInfoByTTComparator myComparator
CHRouter(const std::vector< E *> &edges, bool unbuildIsWarning, Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, bool validatePermissions)
Constructor.
Unidirectional myBackwardSearch
void buildPathFromMeeting(Meeting meeting, std::vector< const E *> &into) const
normal routing methods
virtual SUMOAbstractRouter< E, V > * clone()
SUMOTime myValidUntil
the validity duration of the current hierarchy (exclusive)
double recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime) const
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Unidirectional(const std::vector< E *> &edges, bool forward)
Constructor.
void init(const E *const start, const V *const vehicle)
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
bool found(const E *edge) const
std::pair< const E *, const E * > ConstEdgePair
double traveltime
Effort to reach the edge.
std::pair< const EdgeInfo *, const EdgeInfo * > Meeting
A meeting point of the two search scopes.
StringBijection< SUMOVehicleClass > SumoVehicleClassStrings(sumoVehicleClassStringInitializer, SVC_CUSTOM2, false)
Operation myOperation
The object's operation to perform.
const E * getVia(const E *forwardFrom, const E *forwardTo) const
const std::vector< E * > & myEdges
all edges with numerical ids
MsgHandler *const myErrorMsgHandler
the handler for routing errors
void inform(std::string msg, bool addType=true)
adds a new error to the list
const EdgeInfo * getEdgeInfo(const E *const edge) const
bool myAmForward
the role of this search
void endQuery(int visits)
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E *> &into)
Builds the route between the given edges using the minimum traveltime in the contracted graph...
#define WRITE_MESSAGE(msg)
std::set< const E * > myFound
the set of visited (settled) Edges
EdgeInfo(const E *e)
Constructor.
const E * edge
The current edge.
const CHBuilder< E, V >::Hierarchy * myHierarchy
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...
void buildContractionHierarchy(SUMOTime time, const V *const vehicle)
EdgeInfo * prev
The previous edge.
CHRouter(const std::vector< E *> &edges, bool unbuildIsWarning, Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, const typename CHBuilder< E, V >::Hierarchy *hierarchy)
Cloning constructor.