38 template<
class E,
class C>
54 if (a->traveltime == b->traveltime) {
55 return a->edge->getNumericalID() > b->edge->getNumericalID();
57 return a->traveltime > b->traveltime;
77 for (
typename std::vector<E*>::iterator i =
myFound.begin(); i !=
myFound.end(); i++) {
90 start->traveltime = 0;
92 start->permissions = start->edge->getPermissions();
102 for (
typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
104 E* follower = con.target;
105 if (follower == excluded) {
108 const double traveltime = min->traveltime + con.cost;
109 const double oldTraveltime = follower->traveltime;
110 if (!follower->visited && traveltime < oldTraveltime) {
111 follower->traveltime = traveltime;
112 follower->depth = min->depth + 1;
113 follower->permissions = (min->permissions & con.permissions);
114 if (oldTraveltime == std::numeric_limits<double>::max()) {
147 const C*
const aInfo = it->first;
148 const C*
const fInfo = it->second;
150 aInfo->target, fInfo->target, excluded, (aInfo->permissions & fInfo->permissions));
151 const double viaCost = aInfo->cost + fInfo->cost;
152 if (viaCost < bestWitness) {
165 start->traveltime = 0;
172 return dest->traveltime;
179 for (
typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
181 E* follower = con.target;
182 if (follower == excluded) {
185 if ((con.permissions & permissions) != permissions) {
188 const double traveltime = min->traveltime + con.cost;
189 const double oldTraveltime = follower->traveltime;
190 if (!follower->visited && traveltime < oldTraveltime) {
191 follower->traveltime = traveltime;
192 follower->depth = min->depth + 1;
193 follower->permissions = (min->permissions & con.permissions);
194 if (oldTraveltime == std::numeric_limits<double>::max()) {
206 return dest->traveltime;
212 std::cout <<
"computed SPT from '" << start->edge->getID() <<
"' (excluding " << excluded->edge->getID() <<
") with " <<
myFound.size() <<
" edges\n";
213 for (
typename std::vector<E*>::iterator it = vec.begin(); it != vec.end(); it++) {
215 std::cout <<
"(" << e->edge->getID() <<
"," << e->traveltime <<
") ";
double dijkstraTT(E *start, E *dest, const E *excluded, SVCPermissions permissions)
SPTree(int maxDepth, bool validatePermissions)
Constructor.
int SVCPermissions
bitset where each bit declares whether a certain SVC may use this edge/lane
EdgeByTTComparator myCmp
comparator for search queue
CHConnectionPairs myNeededShortcuts
vector of needed shortcuts after validation
std::vector< CHConnectionPair > CHConnectionPairs
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
std::vector< E * > myFound
the list of visited edges (used when resetting)
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
std::pair< const C *, const C * > CHConnectionPair
std::vector< E * > myFrontier
the min edge heap
void debugPrintVector(std::vector< E *> &vec, E *start, const E *excluded)
bool myValidatePermissions
whether permissions should be validated
std::vector< C > CHConnections
void rebuildFrom(E *start, const E *excluded)
build a shortest path tree from start to a depth of myMaxdepth. The given edge is excluded from this ...
CHConnectionPairs myShortcutsToValidate
vector of needed shortcuts after validation
bool validatePermissions()
whether permissions should be validated;
bool operator()(const E *a, const E *b) const
Comparing method.
int myMaxDepth
maximum search depth