45 template<
class E,
class C>
61 if (a->traveltime == b->traveltime) {
62 return a->edge->getNumericalID() > b->edge->getNumericalID();
64 return a->traveltime > b->traveltime;
84 for (
typename std::vector<E*>::iterator i =
myFound.begin(); i !=
myFound.end(); i++) {
97 start->traveltime = 0;
99 start->permissions = start->edge->getPermissions();
109 for (
typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
111 E* follower = con.target;
112 if (follower == excluded) {
115 const SUMOReal traveltime = min->traveltime + con.cost;
116 const SUMOReal oldTraveltime = follower->traveltime;
117 if (!follower->visited && traveltime < oldTraveltime) {
118 follower->traveltime = traveltime;
119 follower->depth = min->depth + 1;
120 follower->permissions = (min->permissions & con.permissions);
154 const C*
const aInfo = it->first;
155 const C*
const fInfo = it->second;
157 aInfo->target, fInfo->target, excluded, (aInfo->permissions & fInfo->permissions));
158 const SUMOReal viaCost = aInfo->cost + fInfo->cost;
159 if (viaCost < bestWitness) {
172 start->traveltime = 0;
179 return dest->traveltime;
186 for (
typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
188 E* follower = con.target;
189 if (follower == excluded) {
192 if ((con.permissions & permissions) != permissions) {
195 const SUMOReal traveltime = min->traveltime + con.cost;
196 const SUMOReal oldTraveltime = follower->traveltime;
197 if (!follower->visited && traveltime < oldTraveltime) {
198 follower->traveltime = traveltime;
199 follower->depth = min->depth + 1;
200 follower->permissions = (min->permissions & con.permissions);
213 return dest->traveltime;
219 std::cout <<
"computed SPT from '" << start->edge->getID() <<
"' (excluding " << excluded->edge->getID() <<
") with " <<
myFound.size() <<
" edges\n";
220 for (
typename std::vector<E*>::iterator it = vec.begin(); it != vec.end(); it++) {
222 std::cout <<
"(" << e->edge->getID() <<
"," << e->traveltime <<
") ";
SUMOReal dijkstraTT(E *start, E *dest, const E *excluded, SVCPermissions permissions)
SPTree(int maxDepth, bool validatePermissions)
Constructor.
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