62 template<
class E,
class V,
class BASE>
67 typedef double(*
Operation)(
const E*
const,
const V*
const, double);
70 typedef std::pair<const typename BASE::EdgeInfo*, const typename BASE::EdgeInfo*>
Meeting;
82 for (
const E*
const e : edges) {
87 inline bool found(
const E*
const edge)
const {
91 inline typename BASE::EdgeInfo*
getEdgeInfo(
const E*
const edge) {
95 inline const typename BASE::EdgeInfo*
getEdgeInfo(
const E*
const edge)
const {
106 bool operator()(
const typename BASE::EdgeInfo* nod1,
const typename BASE::EdgeInfo* nod2)
const {
107 if (nod1->effort == nod2->effort) {
108 return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
110 return nod1->effort > nod2->effort;
115 void init(
const E*
const start,
const V*
const vehicle) {
116 assert(vehicle != 0);
128 startInfo->effort = 0.;
129 startInfo->prev =
nullptr;
130 myFrontier.push_back(startInfo);
139 bool step(
const std::vector<ConnectionVector>& uplinks,
const Unidirectional& otherSearch,
double& minTTSeen, Meeting& meeting) {
145 const E*
const minEdge = minimumInfo->edge;
146 #ifdef CHRouter_DEBUG_QUERY 147 std::cout <<
"DEBUG: " << (
myAmForward ?
"Forward" :
"Backward") <<
" hit '" << minEdge->getID() <<
"' Q: ";
148 for (
typename std::vector<EdgeInfo*>::iterator it =
myFrontier.begin(); it !=
myFrontier.end(); it++) {
149 std::cout << (*it)->traveltime <<
"," << (*it)->edge->getID() <<
" ";
153 if (otherSearch.
found(minEdge)) {
154 const auto*
const otherInfo = otherSearch.
getEdgeInfo(minEdge);
155 const double ttSeen = minimumInfo->effort + otherInfo->effort;
156 #ifdef CHRouter_DEBUG_QUERY 157 std::cout <<
"DEBUG: " << (
myAmForward ?
"Forward" :
"Backward") <<
"-Search hit other search at '" << minEdge->getID() <<
"', tt: " << ttSeen <<
" \n";
159 if (ttSeen < minTTSeen) {
162 meeting.first = minimumInfo;
163 meeting.second = otherInfo;
165 meeting.first = otherInfo;
166 meeting.second = minimumInfo;
171 minimumInfo->visited =
true;
173 myFound.insert(minimumInfo->edge);
174 for (
const auto& uplink : uplinks[minEdge->getNumericalID()]) {
175 const auto upwardInfo = &
myEdgeInfos[uplink.target];
176 const double effort = minimumInfo->effort + uplink.cost;
179 if ((uplink.permissions & svc) != svc) {
182 const double oldEffort = upwardInfo->effort;
183 if (!upwardInfo->visited && effort < oldEffort) {
184 upwardInfo->effort = effort;
185 upwardInfo->prev = minimumInfo;
186 if (oldEffort == std::numeric_limits<double>::max()) {
225 CHRouter(
const std::vector<E*>& edges,
bool unbuildIsWarning,
typename BASE::Operation operation,
228 bool validatePermissions):
229 BASE(
"CHRouter", unbuildIsWarning, operation),
242 CHRouter(
const std::vector<E*>& edges,
bool unbuildIsWarning,
typename BASE::Operation operation,
246 BASE(
"CHRouterClone", unbuildIsWarning, operation),
278 virtual bool compute(
const E* from,
const E* to,
const V*
const vehicle,
279 SUMOTime msTime, std::vector<const E*>& into,
bool silent =
false) {
280 assert(from != 0 && to != 0);
293 double minTTSeen = std::numeric_limits<double>::max();
294 Meeting meeting(
nullptr,
nullptr);
295 bool continueForward =
true;
296 bool continueBackward =
true;
297 int num_visited_fw = 0;
298 int num_visited_bw = 0;
300 while (continueForward || continueBackward) {
301 if (continueForward) {
305 if (continueBackward) {
310 if (minTTSeen < std::numeric_limits<double>::max()) {
314 this->myErrorMsgHandler->inform(
"No connection between edge '" + from->getID() +
"' and edge '" + to->getID() +
"' found.");
318 #ifdef CHRouter_DEBUG_QUERY_PERF 319 std::cout <<
"visited " << num_visited_fw + num_visited_bw <<
" edges (" << num_visited_fw <<
"," << num_visited_bw <<
") ,final path length: " +
toString(into.size()) +
")\n";
321 this->endQuery(num_visited_bw + num_visited_fw);
329 std::deque<const E*> tmp;
330 const auto* backtrack = meeting.first;
331 while (backtrack != 0) {
332 tmp.push_front((E*) backtrack->edge);
333 backtrack = backtrack->prev;
335 backtrack = meeting.second->prev;
336 while (backtrack != 0) {
337 tmp.push_back((E*) backtrack->edge);
338 backtrack = backtrack->prev;
342 while (!tmp.empty()) {
343 const E* cur = tmp.front();
349 const E* via =
getVia(prev, cur);
376 const E*
getVia(
const E* forwardFrom,
const E* forwardTo)
const {
Computes the shortest path through a contracted network.
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
SUMOTime myValidUntil
the validity duration of the current hierarchy (exclusive)
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
std::vector< typename CHBuilder< E, V >::Connection > ConnectionVector
void buildContractionHierarchy(SUMOTime time, const V *const vehicle)
std::string time2string(SUMOTime t)
void init(const E *const start, const V *const vehicle)
void buildPathFromMeeting(Meeting meeting, std::vector< const E *> &into) const
normal routing methods
bool operator()(const typename BASE::EdgeInfo *nod1, const typename BASE::EdgeInfo *nod2) const
Comparing method.
virtual ~CHRouter()
Destructor.
CHRouter(const std::vector< E *> &edges, bool unbuildIsWarning, typename BASE::Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, bool validatePermissions)
Constructor.
Unidirectional myBackwardSearch
std::vector< typename BASE::EdgeInfo * > myFrontier
the min edge heap
std::vector< typename BASE::EdgeInfo > myEdgeInfos
The container of edge information.
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
const CHBuilder< E, V >::Hierarchy * myHierarchy
BASE::EdgeInfo * getEdgeInfo(const E *const edge)
const E * getVia(const E *forwardFrom, const E *forwardTo) const
const std::vector< E * > & myEdges
all edges with numerical ids
std::pair< const E *, const E * > ConstEdgePair
StringBijection< SUMOVehicleClass > SumoVehicleClassStrings(sumoVehicleClassStringInitializer, SVC_CUSTOM2, false)
bool found(const E *const edge) const
std::set< const E * > myFound
the set of visited (settled) Edges
const SUMOTime myWeightPeriod
the validity duration of one weight interval
double(* Operation)(const E *const, const V *const, double)
Type of the function that is used to retrieve the edge effort.
const BASE::EdgeInfo * getEdgeInfo(const E *const edge) const
Unidirectional(const std::vector< E *> &edges, bool forward)
Constructor.
Unidirectional myForwardSearch
the unidirectional search queues
virtual SUMOAbstractRouter< E, V > * clone()
bool myAmForward
the role of this search
#define WRITE_MESSAGE(msg)
EdgeInfoByTTComparator myComparator
std::pair< const typename BASE::EdgeInfo *, const typename BASE::EdgeInfo * > Meeting
A meeting point of the two search scopes.
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...
CHBuilder< E, V > * myHierarchyBuilder
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...
CHRouter(const std::vector< E *> &edges, bool unbuildIsWarning, typename BASE::Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, const typename CHBuilder< E, V >::Hierarchy *hierarchy)
Cloning constructor.