1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2001-2019 German Aerospace Center (DLR) and others.
4 // This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v2.0
6 // which accompanies this distribution, and is available at
7 // http://www.eclipse.org/legal/epl-v20.html
8 // SPDX-License-Identifier: EPL-2.0
9 /****************************************************************************/
10 /// @file RODFNet.cpp
11 /// @author Daniel Krajzewicz
12 /// @author Eric Nicolay
13 /// @author Jakob Erdmann
14 /// @author Michael Behrisch
15 /// @date Thu, 16.03.2006
16 /// @version $Id$
17 ///
18 // A DFROUTER-network
19 /****************************************************************************/
20 // ===========================================================================
21 // included modules
22 // ===========================================================================
23 #include <config.h>
24
25 #include <cassert>
26 #include <iostream>
27 #include <map>
28 #include <queue>
29 #include <vector>
30 #include <iterator>
31 #include "RODFNet.h"
32 #include "RODFDetector.h"
33 #include "RODFRouteDesc.h"
34 #include "RODFDetectorFlow.h"
35 #include "RODFEdge.h"
36 #include <cmath>
37 #include <utils/common/MsgHandler.h>
38 #include <utils/common/ToString.h>
39 #include <utils/common/UtilExceptions.h>
40 #include <utils/geom/GeomHelper.h>
41
42
43 // ===========================================================================
44 // method definitions
45 // ===========================================================================
RODFNet(bool amInHighwayMode)46 RODFNet::RODFNet(bool amInHighwayMode) :
47 RONet(), myAmInHighwayMode(amInHighwayMode),
48 mySourceNumber(0), mySinkNumber(0), myInBetweenNumber(0), myInvalidNumber(0),
49 myMaxSpeedFactorPKW(1),
50 myMaxSpeedFactorLKW(1),
51 myAvgSpeedFactorPKW(1),
52 myAvgSpeedFactorLKW(1) {
53 myDisallowedEdges = OptionsCont::getOptions().getStringVector("disallowed-edges");
54 myKeepTurnarounds = OptionsCont::getOptions().getBool("keep-turnarounds");
55 }
56
57
~RODFNet()58 RODFNet::~RODFNet() {
59 }
60
61
62 void
buildApproachList()63 RODFNet::buildApproachList() {
64 for (const auto& rit : getEdgeMap()) {
65 ROEdge* ce = rit.second;
66 if (ce->isInternal()) {
67 continue;
68 }
69 const ROEdgeVector& successors = ce->getSuccessors();
70 for (ROEdgeVector::const_iterator it = successors.begin(); it != successors.end(); ++it) {
71 ROEdge* help = *it;
72 if (find(myDisallowedEdges.begin(), myDisallowedEdges.end(), help->getID()) != myDisallowedEdges.end()) {
73 // edges in sinks will not be used
74 continue;
75 }
76 if (!myKeepTurnarounds && help->getToJunction() == ce->getFromJunction()) {
77 // do not use turnarounds
78 continue;
79 }
80 // add the connection help->ce to myApproachingEdges
81 if (myApproachingEdges.find(help) == myApproachingEdges.end()) {
82 myApproachingEdges[help] = ROEdgeVector();
83 }
84 myApproachingEdges[help].push_back(ce);
85 // add the connection ce->help to myApproachingEdges
86 if (myApproachedEdges.find(ce) == myApproachedEdges.end()) {
87 myApproachedEdges[ce] = ROEdgeVector();
88 }
89 myApproachedEdges[ce].push_back(help);
90 }
91 }
92 }
93
94
95 void
buildDetectorEdgeDependencies(RODFDetectorCon & detcont) const96 RODFNet::buildDetectorEdgeDependencies(RODFDetectorCon& detcont) const {
97 myDetectorsOnEdges.clear();
98 myDetectorEdges.clear();
99 const std::vector<RODFDetector*>& dets = detcont.getDetectors();
100 for (std::vector<RODFDetector*>::const_iterator i = dets.begin(); i != dets.end(); ++i) {
101 ROEdge* e = getDetectorEdge(**i);
102 myDetectorsOnEdges[e].push_back((*i)->getID());
103 myDetectorEdges[(*i)->getID()] = e;
104 }
105 }
106
107
108 void
computeTypes(RODFDetectorCon & detcont,bool sourcesStrict) const109 RODFNet::computeTypes(RODFDetectorCon& detcont,
110 bool sourcesStrict) const {
111 PROGRESS_BEGIN_MESSAGE("Computing detector types");
112 const std::vector< RODFDetector*>& dets = detcont.getDetectors();
113 // build needed information. first
114 buildDetectorEdgeDependencies(detcont);
115 // compute detector types then
116 for (std::vector< RODFDetector*>::const_iterator i = dets.begin(); i != dets.end(); ++i) {
117 if (isSource(**i, detcont, sourcesStrict)) {
118 (*i)->setType(SOURCE_DETECTOR);
119 mySourceNumber++;
120 }
121 if (isDestination(**i, detcont)) {
122 (*i)->setType(SINK_DETECTOR);
123 mySinkNumber++;
124 }
125 if ((*i)->getType() == TYPE_NOT_DEFINED) {
126 (*i)->setType(BETWEEN_DETECTOR);
127 myInBetweenNumber++;
128 }
129 }
130 // recheck sources
131 for (std::vector< RODFDetector*>::const_iterator i = dets.begin(); i != dets.end(); ++i) {
132 if ((*i)->getType() == SOURCE_DETECTOR && isFalseSource(**i, detcont)) {
133 (*i)->setType(DISCARDED_DETECTOR);
134 myInvalidNumber++;
135 mySourceNumber--;
136 }
137 }
138 // print results
139 PROGRESS_DONE_MESSAGE();
140 WRITE_MESSAGE("Computed detector types:");
141 WRITE_MESSAGE(" " + toString(mySourceNumber) + " source detectors");
142 WRITE_MESSAGE(" " + toString(mySinkNumber) + " sink detectors");
143 WRITE_MESSAGE(" " + toString(myInBetweenNumber) + " in-between detectors");
144 WRITE_MESSAGE(" " + toString(myInvalidNumber) + " invalid detectors");
145 }
146
147
148 bool
hasInBetweenDetectorsOnly(ROEdge * edge,const RODFDetectorCon & detectors) const149 RODFNet::hasInBetweenDetectorsOnly(ROEdge* edge,
150 const RODFDetectorCon& detectors) const {
151 assert(myDetectorsOnEdges.find(edge) != myDetectorsOnEdges.end());
152 const std::vector<std::string>& detIDs = myDetectorsOnEdges.find(edge)->second;
153 std::vector<std::string>::const_iterator i;
154 for (i = detIDs.begin(); i != detIDs.end(); ++i) {
155 const RODFDetector& det = detectors.getDetector(*i);
156 if (det.getType() != BETWEEN_DETECTOR) {
157 return false;
158 }
159 }
160 return true;
161 }
162
163
164 bool
hasSourceDetector(ROEdge * edge,const RODFDetectorCon & detectors) const165 RODFNet::hasSourceDetector(ROEdge* edge,
166 const RODFDetectorCon& detectors) const {
167 assert(myDetectorsOnEdges.find(edge) != myDetectorsOnEdges.end());
168 const std::vector<std::string>& detIDs = myDetectorsOnEdges.find(edge)->second;
169 std::vector<std::string>::const_iterator i;
170 for (i = detIDs.begin(); i != detIDs.end(); ++i) {
171 const RODFDetector& det = detectors.getDetector(*i);
172 if (det.getType() == SOURCE_DETECTOR) {
173 return true;
174 }
175 }
176 return false;
177 }
178
179
180
181 void
computeRoutesFor(ROEdge * edge,RODFRouteDesc & base,int,bool keepUnfoundEnds,bool keepShortestOnly,ROEdgeVector &,const RODFDetector & det,RODFRouteCont & into,const RODFDetectorCon & detectors,int maxFollowingLength,ROEdgeVector & seen) const182 RODFNet::computeRoutesFor(ROEdge* edge, RODFRouteDesc& base, int /*no*/,
183 bool keepUnfoundEnds,
184 bool keepShortestOnly,
185 ROEdgeVector& /*visited*/,
186 const RODFDetector& det, RODFRouteCont& into,
187 const RODFDetectorCon& detectors,
188 int maxFollowingLength,
189 ROEdgeVector& seen) const {
190 std::vector<RODFRouteDesc> unfoundEnds;
191 std::priority_queue<RODFRouteDesc, std::vector<RODFRouteDesc>, DFRouteDescByTimeComperator> toSolve;
192 std::map<ROEdge*, ROEdgeVector > dets2Follow;
193 dets2Follow[edge] = ROEdgeVector();
194 base.passedNo = 0;
195 double minDist = OptionsCont::getOptions().getFloat("min-route-length");
196 toSolve.push(base);
197 while (!toSolve.empty()) {
198 RODFRouteDesc current = toSolve.top();
199 toSolve.pop();
200 ROEdge* last = *(current.edges2Pass.end() - 1);
201 if (hasDetector(last)) {
202 if (dets2Follow.find(last) == dets2Follow.end()) {
203 dets2Follow[last] = ROEdgeVector();
204 }
205 for (ROEdgeVector::reverse_iterator i = current.edges2Pass.rbegin() + 1; i != current.edges2Pass.rend(); ++i) {
206 if (hasDetector(*i)) {
207 dets2Follow[*i].push_back(last);
208 break;
209 }
210 }
211 }
212
213 // do not process an edge twice
214 if (find(seen.begin(), seen.end(), last) != seen.end() && keepShortestOnly) {
215 continue;
216 }
217 seen.push_back(last);
218 // end if the edge has no further connections
219 if (!hasApproached(last)) {
220 // ok, no further connections to follow
221 current.factor = 1.;
222 double cdist = current.edges2Pass[0]->getFromJunction()->getPosition().distanceTo(current.edges2Pass.back()->getToJunction()->getPosition());
223 if (minDist < cdist) {
224 into.addRouteDesc(current);
225 }
226 continue;
227 }
228 // check for passing detectors:
229 // if the current last edge is not the one the detector is placed on ...
230 bool addNextNoFurther = false;
231 if (last != getDetectorEdge(det)) {
232 // ... if there is a detector ...
233 if (hasDetector(last)) {
234 if (!hasInBetweenDetectorsOnly(last, detectors)) {
235 // ... and it's not an in-between-detector
236 // -> let's add this edge and the following, but not any further
237 addNextNoFurther = true;
238 current.lastDetectorEdge = last;
239 current.duration2Last = (SUMOTime) current.duration_2;
240 current.distance2Last = current.distance;
241 current.endDetectorEdge = last;
242 if (hasSourceDetector(last, detectors)) {
243 ///!!! //toDiscard.push_back(current);
244 }
245 current.factor = 1.;
246 double cdist = current.edges2Pass[0]->getFromJunction()->getPosition().distanceTo(current.edges2Pass.back()->getToJunction()->getPosition());
247 if (minDist < cdist) {
248 into.addRouteDesc(current);
249 }
250 continue;
251 } else {
252 // ... if it's an in-between-detector
253 // -> mark the current route as to be continued
254 current.passedNo = 0;
255 current.duration2Last = (SUMOTime) current.duration_2;
256 current.distance2Last = current.distance;
257 current.lastDetectorEdge = last;
258 }
259 }
260 }
261 // check for highway off-ramps
262 if (myAmInHighwayMode) {
263 // if it's beside the highway...
264 if (last->getSpeedLimit() < 19.4 && last != getDetectorEdge(det)) {
265 // ... and has more than one following edge
266 if (myApproachedEdges.find(last)->second.size() > 1) {
267 // -> let's add this edge and the following, but not any further
268 addNextNoFurther = true;
269 }
270
271 }
272 }
273 // check for missing end connections
274 if (!addNextNoFurther) {
275 // ... if this one would be processed, but already too many edge
276 // without a detector occurred
277 if (current.passedNo > maxFollowingLength) {
278 // mark not to process any further
279 WRITE_WARNING("Could not close route for '" + det.getID() + "'");
280 unfoundEnds.push_back(current);
281 current.factor = 1.;
282 double cdist = current.edges2Pass[0]->getFromJunction()->getPosition().distanceTo(current.edges2Pass.back()->getToJunction()->getPosition());
283 if (minDist < cdist) {
284 into.addRouteDesc(current);
285 }
286 continue;
287 }
288 }
289 // ... else: loop over the next edges
290 const ROEdgeVector& appr = myApproachedEdges.find(last)->second;
291 bool hadOne = false;
292 for (int i = 0; i < (int)appr.size(); i++) {
293 if (find(current.edges2Pass.begin(), current.edges2Pass.end(), appr[i]) != current.edges2Pass.end()) {
294 // do not append an edge twice (do not build loops)
295 continue;
296 }
297 RODFRouteDesc t(current);
298 t.duration_2 += (appr[i]->getLength() / appr[i]->getSpeedLimit()); //!!!
299 t.distance += appr[i]->getLength();
300 t.edges2Pass.push_back(appr[i]);
301 if (!addNextNoFurther) {
302 t.passedNo = t.passedNo + 1;
303 toSolve.push(t);
304 } else {
305 if (!hadOne) {
306 t.factor = (double) 1. / (double) appr.size();
307 double cdist = current.edges2Pass[0]->getFromJunction()->getPosition().distanceTo(current.edges2Pass.back()->getToJunction()->getPosition());
308 if (minDist < cdist) {
309 into.addRouteDesc(t);
310 }
311 hadOne = true;
312 }
313 }
314 }
315 }
316 //
317 if (!keepUnfoundEnds) {
318 std::vector<RODFRouteDesc>::iterator i;
319 ConstROEdgeVector lastDetEdges;
320 for (i = unfoundEnds.begin(); i != unfoundEnds.end(); ++i) {
321 if (find(lastDetEdges.begin(), lastDetEdges.end(), (*i).lastDetectorEdge) == lastDetEdges.end()) {
322 lastDetEdges.push_back((*i).lastDetectorEdge);
323 } else {
324 bool ok = into.removeRouteDesc(*i);
325 assert(ok);
326 UNUSED_PARAMETER(ok); // ony used for assertion
327 }
328 }
329 } else {
330 // !!! patch the factors
331 }
332 while (!toSolve.empty()) {
333 // RODFRouteDesc d = toSolve.top();
334 toSolve.pop();
335 // delete d;
336 }
337 }
338
339
340 void
buildRoutes(RODFDetectorCon & detcont,bool keepUnfoundEnds,bool includeInBetween,bool keepShortestOnly,int maxFollowingLength) const341 RODFNet::buildRoutes(RODFDetectorCon& detcont, bool keepUnfoundEnds, bool includeInBetween,
342 bool keepShortestOnly, int maxFollowingLength) const {
343 // build needed information first
344 buildDetectorEdgeDependencies(detcont);
345 // then build the routes
346 std::map<ROEdge*, RODFRouteCont* > doneEdges;
347 const std::vector< RODFDetector*>& dets = detcont.getDetectors();
348 for (std::vector< RODFDetector*>::const_iterator i = dets.begin(); i != dets.end(); ++i) {
349 ROEdge* e = getDetectorEdge(**i);
350 if (doneEdges.find(e) != doneEdges.end()) {
351 // use previously build routes
352 (*i)->addRoutes(new RODFRouteCont(*doneEdges[e]));
353 continue;
354 }
355 ROEdgeVector seen;
356 RODFRouteCont* routes = new RODFRouteCont();
357 doneEdges[e] = routes;
358 RODFRouteDesc rd;
359 rd.edges2Pass.push_back(e);
360 rd.duration_2 = (e->getLength() / e->getSpeedLimit()); //!!!;
361 rd.endDetectorEdge = nullptr;
362 rd.lastDetectorEdge = nullptr;
363 rd.distance = e->getLength();
364 rd.distance2Last = 0;
365 rd.duration2Last = 0;
366
367 rd.overallProb = 0;
368
369 ROEdgeVector visited;
370 visited.push_back(e);
371 computeRoutesFor(e, rd, 0, keepUnfoundEnds, keepShortestOnly,
372 visited, **i, *routes, detcont, maxFollowingLength, seen);
373 //!!!routes->removeIllegal(illegals);
374 (*i)->addRoutes(routes);
375
376 // add routes to in-between detectors if wished
377 if (includeInBetween) {
378 // go through the routes
379 const std::vector<RODFRouteDesc>& r = routes->get();
380 for (std::vector<RODFRouteDesc>::const_iterator j = r.begin(); j != r.end(); ++j) {
381 const RODFRouteDesc& mrd = *j;
382 double duration = mrd.duration_2;
383 double distance = mrd.distance;
384 // go through each route's edges
385 ROEdgeVector::const_iterator routeend = mrd.edges2Pass.end();
386 for (ROEdgeVector::const_iterator k = mrd.edges2Pass.begin(); k != routeend; ++k) {
387 // check whether any detectors lies on the current edge
388 if (myDetectorsOnEdges.find(*k) == myDetectorsOnEdges.end()) {
389 duration -= (*k)->getLength() / (*k)->getSpeedLimit();
390 distance -= (*k)->getLength();
391 continue;
392 }
393 // get the detectors
394 const std::vector<std::string>& dets = myDetectorsOnEdges.find(*k)->second;
395 // go through the detectors
396 for (std::vector<std::string>::const_iterator l = dets.begin(); l != dets.end(); ++l) {
397 const RODFDetector& m = detcont.getDetector(*l);
398 if (m.getType() == BETWEEN_DETECTOR) {
399 RODFRouteDesc nrd;
400 copy(k, routeend, back_inserter(nrd.edges2Pass));
401 nrd.duration_2 = duration;//!!!;
402 nrd.endDetectorEdge = mrd.endDetectorEdge;
403 nrd.lastDetectorEdge = mrd.lastDetectorEdge;
404 nrd.distance = distance;
405 nrd.distance2Last = mrd.distance2Last;
406 nrd.duration2Last = mrd.duration2Last;
407 nrd.overallProb = mrd.overallProb;
408 nrd.factor = mrd.factor;
409 ((RODFDetector&) m).addRoute(nrd);
410 }
411 }
412 duration -= (*k)->getLength() / (*k)->getSpeedLimit();
413 distance -= (*k)->getLength();
414 }
415 }
416 }
417
418 }
419 }
420
421
422 void
revalidateFlows(const RODFDetector * detector,RODFDetectorFlows & flows,SUMOTime startTime,SUMOTime endTime,SUMOTime stepOffset)423 RODFNet::revalidateFlows(const RODFDetector* detector,
424 RODFDetectorFlows& flows,
425 SUMOTime startTime, SUMOTime endTime,
426 SUMOTime stepOffset) {
427 {
428 if (flows.knows(detector->getID())) {
429 const std::vector<FlowDef>& detFlows = flows.getFlowDefs(detector->getID());
430 for (std::vector<FlowDef>::const_iterator j = detFlows.begin(); j != detFlows.end(); ++j) {
431 if ((*j).qPKW > 0 || (*j).qLKW > 0) {
432 return;
433 }
434 }
435 }
436 }
437 // ok, there is no information for the whole time;
438 // lets find preceding detectors and rebuild the flows if possible
439 WRITE_WARNING("Detector '" + detector->getID() + "' has no flows.\n Trying to rebuild.");
440 // go back and collect flows
441 ROEdgeVector previous;
442 {
443 std::vector<IterationEdge> missing;
444 IterationEdge ie;
445 ie.depth = 0;
446 ie.edge = getDetectorEdge(*detector);
447 missing.push_back(ie);
448 bool maxDepthReached = false;
449 while (!missing.empty() && !maxDepthReached) {
450 IterationEdge last = missing.back();
451 missing.pop_back();
452 ROEdgeVector approaching = myApproachingEdges[last.edge];
453 for (ROEdgeVector::const_iterator j = approaching.begin(); j != approaching.end(); ++j) {
454 if (hasDetector(*j)) {
455 previous.push_back(*j);
456 } else {
457 ie.depth = last.depth + 1;
458 ie.edge = *j;
459 missing.push_back(ie);
460 if (ie.depth > 5) {
461 maxDepthReached = true;
462 }
463 }
464 }
465 }
466 if (maxDepthReached) {
467 WRITE_WARNING(" Could not build list of previous flows.");
468 }
469 }
470 // Edges with previous detectors are now in "previous";
471 // compute following
472 ROEdgeVector latter;
473 {
474 std::vector<IterationEdge> missing;
475 for (ROEdgeVector::const_iterator k = previous.begin(); k != previous.end(); ++k) {
476 IterationEdge ie;
477 ie.depth = 0;
478 ie.edge = *k;
479 missing.push_back(ie);
480 }
481 bool maxDepthReached = false;
482 while (!missing.empty() && !maxDepthReached) {
483 IterationEdge last = missing.back();
484 missing.pop_back();
485 ROEdgeVector approached = myApproachedEdges[last.edge];
486 for (ROEdgeVector::const_iterator j = approached.begin(); j != approached.end(); ++j) {
487 if (*j == getDetectorEdge(*detector)) {
488 continue;
489 }
490 if (hasDetector(*j)) {
491 latter.push_back(*j);
492 } else {
493 IterationEdge ie;
494 ie.depth = last.depth + 1;
495 ie.edge = *j;
496 missing.push_back(ie);
497 if (ie.depth > 5) {
498 maxDepthReached = true;
499 }
500 }
501 }
502 }
503 if (maxDepthReached) {
504 WRITE_WARNING(" Could not build list of latter flows.");
505 return;
506 }
507 }
508 // Edges with latter detectors are now in "latter";
509
510 // lets not validate them by now - surely this should be done
511 // for each time step: collect incoming flows; collect outgoing;
512 std::vector<FlowDef> mflows;
513 int index = 0;
514 for (SUMOTime t = startTime; t < endTime; t += stepOffset, index++) {
515 FlowDef inFlow;
516 inFlow.qLKW = 0;
517 inFlow.qPKW = 0;
518 inFlow.vLKW = 0;
519 inFlow.vPKW = 0;
520 // collect incoming
521 {
522 // !! time difference is missing
523 for (ROEdgeVector::iterator i = previous.begin(); i != previous.end(); ++i) {
524 const std::vector<FlowDef>& flows = static_cast<const RODFEdge*>(*i)->getFlows();
525 if (flows.size() != 0) {
526 const FlowDef& srcFD = flows[index];
527 inFlow.qLKW += srcFD.qLKW;
528 inFlow.qPKW += srcFD.qPKW;
529 inFlow.vLKW += srcFD.vLKW;
530 inFlow.vPKW += srcFD.vPKW;
531 }
532 }
533 }
534 inFlow.vLKW /= (double) previous.size();
535 inFlow.vPKW /= (double) previous.size();
536 // collect outgoing
537 FlowDef outFlow;
538 outFlow.qLKW = 0;
539 outFlow.qPKW = 0;
540 outFlow.vLKW = 0;
541 outFlow.vPKW = 0;
542 {
543 // !! time difference is missing
544 for (ROEdgeVector::iterator i = latter.begin(); i != latter.end(); ++i) {
545 const std::vector<FlowDef>& flows = static_cast<const RODFEdge*>(*i)->getFlows();
546 if (flows.size() != 0) {
547 const FlowDef& srcFD = flows[index];
548 outFlow.qLKW += srcFD.qLKW;
549 outFlow.qPKW += srcFD.qPKW;
550 outFlow.vLKW += srcFD.vLKW;
551 outFlow.vPKW += srcFD.vPKW;
552 }
553 }
554 }
555 outFlow.vLKW /= (double) latter.size();
556 outFlow.vPKW /= (double) latter.size();
557 //
558 FlowDef mFlow;
559 mFlow.qLKW = inFlow.qLKW - outFlow.qLKW;
560 mFlow.qPKW = inFlow.qPKW - outFlow.qPKW;
561 mFlow.vLKW = (inFlow.vLKW + outFlow.vLKW) / (double) 2.;
562 mFlow.vPKW = (inFlow.vPKW + outFlow.vPKW) / (double) 2.;
563 mflows.push_back(mFlow);
564 }
565 static_cast<RODFEdge*>(getDetectorEdge(*detector))->setFlows(mflows);
566 flows.setFlows(detector->getID(), mflows);
567 }
568
569
570 void
revalidateFlows(const RODFDetectorCon & detectors,RODFDetectorFlows & flows,SUMOTime startTime,SUMOTime endTime,SUMOTime stepOffset)571 RODFNet::revalidateFlows(const RODFDetectorCon& detectors,
572 RODFDetectorFlows& flows,
573 SUMOTime startTime, SUMOTime endTime,
574 SUMOTime stepOffset) {
575 const std::vector<RODFDetector*>& dets = detectors.getDetectors();
576 for (std::vector<RODFDetector*>::const_iterator i = dets.begin(); i != dets.end(); ++i) {
577 // check whether there is at least one entry with a flow larger than zero
578 revalidateFlows(*i, flows, startTime, endTime, stepOffset);
579 }
580 }
581
582
583
584 void
removeEmptyDetectors(RODFDetectorCon & detectors,RODFDetectorFlows & flows)585 RODFNet::removeEmptyDetectors(RODFDetectorCon& detectors,
586 RODFDetectorFlows& flows) {
587 const std::vector<RODFDetector*>& dets = detectors.getDetectors();
588 for (std::vector<RODFDetector*>::const_iterator i = dets.begin(); i != dets.end();) {
589 bool remove = true;
590 // check whether there is at least one entry with a flow larger than zero
591 if (flows.knows((*i)->getID())) {
592 remove = false;
593 }
594 if (remove) {
595 WRITE_MESSAGE("Removed detector '" + (*i)->getID() + "' because no flows for him exist.");
596 flows.removeFlow((*i)->getID());
597 detectors.removeDetector((*i)->getID());
598 i = dets.begin();
599 } else {
600 i++;
601 }
602 }
603 }
604
605
606
607 void
reportEmptyDetectors(RODFDetectorCon & detectors,RODFDetectorFlows & flows)608 RODFNet::reportEmptyDetectors(RODFDetectorCon& detectors,
609 RODFDetectorFlows& flows) {
610 const std::vector<RODFDetector*>& dets = detectors.getDetectors();
611 for (std::vector<RODFDetector*>::const_iterator i = dets.begin(); i != dets.end(); ++i) {
612 bool remove = true;
613 // check whether there is at least one entry with a flow larger than zero
614 if (flows.knows((*i)->getID())) {
615 remove = false;
616 }
617 if (remove) {
618 WRITE_MESSAGE("Detector '" + (*i)->getID() + "' has no flow.");
619 }
620 }
621 }
622
623
624
625 ROEdge*
getDetectorEdge(const RODFDetector & det) const626 RODFNet::getDetectorEdge(const RODFDetector& det) const {
627 std::string edgeName = det.getLaneID();
628 edgeName = edgeName.substr(0, edgeName.rfind('_'));
629 ROEdge* ret = getEdge(edgeName);
630 if (ret == nullptr) {
631 throw ProcessError("Edge '" + edgeName + "' used by detector '" + det.getID() + "' is not known.");
632 }
633 return ret;
634 }
635
636
637 bool
hasApproaching(ROEdge * edge) const638 RODFNet::hasApproaching(ROEdge* edge) const {
639 return
640 myApproachingEdges.find(edge) != myApproachingEdges.end()
641 &&
642 myApproachingEdges.find(edge)->second.size() != 0;
643 }
644
645
646 bool
hasApproached(ROEdge * edge) const647 RODFNet::hasApproached(ROEdge* edge) const {
648 return
649 myApproachedEdges.find(edge) != myApproachedEdges.end()
650 &&
651 myApproachedEdges.find(edge)->second.size() != 0;
652 }
653
654
655 bool
hasDetector(ROEdge * edge) const656 RODFNet::hasDetector(ROEdge* edge) const {
657 return
658 myDetectorsOnEdges.find(edge) != myDetectorsOnEdges.end()
659 &&
660 myDetectorsOnEdges.find(edge)->second.size() != 0;
661 }
662
663
664 const std::vector<std::string>&
getDetectorList(ROEdge * edge) const665 RODFNet::getDetectorList(ROEdge* edge) const {
666 return myDetectorsOnEdges.find(edge)->second;
667 }
668
669
670 double
getAbsPos(const RODFDetector & det) const671 RODFNet::getAbsPos(const RODFDetector& det) const {
672 if (det.getPos() >= 0) {
673 return det.getPos();
674 }
675 return getDetectorEdge(det)->getLength() + det.getPos();
676 }
677
678 bool
isSource(const RODFDetector & det,const RODFDetectorCon & detectors,bool strict) const679 RODFNet::isSource(const RODFDetector& det, const RODFDetectorCon& detectors,
680 bool strict) const {
681 ROEdgeVector seen;
682 return
683 isSource(det, getDetectorEdge(det), seen, detectors, strict);
684 }
685
686 bool
isFalseSource(const RODFDetector & det,const RODFDetectorCon & detectors) const687 RODFNet::isFalseSource(const RODFDetector& det, const RODFDetectorCon& detectors) const {
688 ROEdgeVector seen;
689 return
690 isFalseSource(det, getDetectorEdge(det), seen, detectors);
691 }
692
693 bool
isDestination(const RODFDetector & det,const RODFDetectorCon & detectors) const694 RODFNet::isDestination(const RODFDetector& det, const RODFDetectorCon& detectors) const {
695 ROEdgeVector seen;
696 return isDestination(det, getDetectorEdge(det), seen, detectors);
697 }
698
699
700 bool
isSource(const RODFDetector & det,ROEdge * edge,ROEdgeVector & seen,const RODFDetectorCon & detectors,bool strict) const701 RODFNet::isSource(const RODFDetector& det, ROEdge* edge,
702 ROEdgeVector& seen,
703 const RODFDetectorCon& detectors,
704 bool strict) const {
705 if (seen.size() == 1000) { // !!!
706 WRITE_WARNING("Quitting checking for being a source for detector '" + det.getID() + "' due to seen edge limit.");
707 return false;
708 }
709 if (edge == getDetectorEdge(det)) {
710 // maybe there is another detector at the same edge
711 // get the list of this/these detector(s)
712 const std::vector<std::string>& detsOnEdge = myDetectorsOnEdges.find(edge)->second;
713 for (std::vector<std::string>::const_iterator i = detsOnEdge.begin(); i != detsOnEdge.end(); ++i) {
714 if ((*i) == det.getID()) {
715 continue;
716 }
717 const RODFDetector& sec = detectors.getDetector(*i);
718 if (getAbsPos(sec) < getAbsPos(det)) {
719 // ok, there is another detector on the same edge and it is
720 // before this one -> no source
721 return false;
722 }
723 }
724 }
725 // it's a source if no edges are approaching the edge
726 if (!hasApproaching(edge)) {
727 if (edge != getDetectorEdge(det)) {
728 if (hasDetector(edge)) {
729 return false;
730 }
731 }
732 return true;
733 }
734 if (edge != getDetectorEdge(det)) {
735 // ok, we are at one of the edges in front
736 if (myAmInHighwayMode) {
737 if (edge->getSpeedLimit() >= 19.4) {
738 if (hasDetector(edge)) {
739 // we are still on the highway and there is another detector
740 return false;
741 }
742 // the next is a hack for the A100 scenario...
743 // We have to look into further edges herein edges
744 const ROEdgeVector& appr = myApproachingEdges.find(edge)->second;
745 int noOk = 0;
746 int noFalse = 0;
747 int noSkipped = 0;
748 for (int i = 0; i < (int)appr.size(); i++) {
749 if (!hasDetector(appr[i])) {
750 noOk++;
751 } else {
752 noFalse++;
753 }
754 }
755 if (noFalse + noSkipped == (int)appr.size()) {
756 return false;
757 }
758 }
759 }
760 }
761
762 if (myAmInHighwayMode) {
763 if (edge->getSpeedLimit() < 19.4 && edge != getDetectorEdge(det)) {
764 // we have left the highway already
765 // -> the detector will be a highway source
766 if (!hasDetector(edge)) {
767 return true;
768 }
769 }
770 }
771 if (myDetectorsOnEdges.find(edge) != myDetectorsOnEdges.end()
772 &&
773 myDetectorEdges.find(det.getID())->second != edge) {
774 return false;
775 }
776
777 // let's check the edges in front
778 const ROEdgeVector& appr = myApproachingEdges.find(edge)->second;
779 int numOk = 0;
780 int numFalse = 0;
781 int numSkipped = 0;
782 seen.push_back(edge);
783 for (int i = 0; i < (int)appr.size(); i++) {
784 bool had = std::find(seen.begin(), seen.end(), appr[i]) != seen.end();
785 if (!had) {
786 if (isSource(det, appr[i], seen, detectors, strict)) {
787 numOk++;
788 } else {
789 numFalse++;
790 }
791 } else {
792 numSkipped++;
793 }
794 }
795 if (strict) {
796 return numOk + numSkipped == (int)appr.size();
797 }
798 return numFalse + numSkipped != (int)appr.size();
799 }
800
801
802 bool
isDestination(const RODFDetector & det,ROEdge * edge,ROEdgeVector & seen,const RODFDetectorCon & detectors) const803 RODFNet::isDestination(const RODFDetector& det, ROEdge* edge, ROEdgeVector& seen,
804 const RODFDetectorCon& detectors) const {
805 if (seen.size() == 1000) { // !!!
806 WRITE_WARNING("Quitting checking for being a destination for detector '" + det.getID() + "' due to seen edge limit.");
807 return false;
808 }
809 if (edge == getDetectorEdge(det)) {
810 // maybe there is another detector at the same edge
811 // get the list of this/these detector(s)
812 const std::vector<std::string>& detsOnEdge = myDetectorsOnEdges.find(edge)->second;
813 for (std::vector<std::string>::const_iterator i = detsOnEdge.begin(); i != detsOnEdge.end(); ++i) {
814 if ((*i) == det.getID()) {
815 continue;
816 }
817 const RODFDetector& sec = detectors.getDetector(*i);
818 if (getAbsPos(sec) > getAbsPos(det)) {
819 // ok, there is another detector on the same edge and it is
820 // after this one -> no destination
821 return false;
822 }
823 }
824 }
825 if (!hasApproached(edge)) {
826 if (edge != getDetectorEdge(det)) {
827 if (hasDetector(edge)) {
828 return false;
829 }
830 }
831 return true;
832 }
833 if (edge != getDetectorEdge(det)) {
834 // ok, we are at one of the edges coming behind
835 if (myAmInHighwayMode) {
836 if (edge->getSpeedLimit() >= 19.4) {
837 if (hasDetector(edge)) {
838 // we are still on the highway and there is another detector
839 return false;
840 }
841 }
842 }
843 }
844
845 if (myAmInHighwayMode) {
846 if (edge->getSpeedLimit() < 19.4 && edge != getDetectorEdge(det)) {
847 if (hasDetector(edge)) {
848 return true;
849 }
850 if (myApproachedEdges.find(edge)->second.size() > 1) {
851 return true;
852 }
853
854 }
855 }
856
857 if (myDetectorsOnEdges.find(edge) != myDetectorsOnEdges.end()
858 &&
859 myDetectorEdges.find(det.getID())->second != edge) {
860 return false;
861 }
862 const ROEdgeVector& appr = myApproachedEdges.find(edge)->second;
863 bool isall = true;
864 int no = 0;
865 seen.push_back(edge);
866 for (int i = 0; i < (int)appr.size() && isall; i++) {
867 bool had = std::find(seen.begin(), seen.end(), appr[i]) != seen.end();
868 if (!had) {
869 if (!isDestination(det, appr[i], seen, detectors)) {
870 no++;
871 isall = false;
872 }
873 }
874 }
875 return isall;
876 }
877
878 bool
isFalseSource(const RODFDetector & det,ROEdge * edge,ROEdgeVector & seen,const RODFDetectorCon & detectors) const879 RODFNet::isFalseSource(const RODFDetector& det, ROEdge* edge, ROEdgeVector& seen,
880 const RODFDetectorCon& detectors) const {
881 if (seen.size() == 1000) { // !!!
882 WRITE_WARNING("Quitting checking for being a false source for detector '" + det.getID() + "' due to seen edge limit.");
883 return false;
884 }
885 seen.push_back(edge);
886 if (edge != getDetectorEdge(det)) {
887 // ok, we are at one of the edges coming behind
888 if (hasDetector(edge)) {
889 const std::vector<std::string>& dets = myDetectorsOnEdges.find(edge)->second;
890 for (std::vector<std::string>::const_iterator i = dets.begin(); i != dets.end(); ++i) {
891 if (detectors.getDetector(*i).getType() == SINK_DETECTOR) {
892 return false;
893 }
894 if (detectors.getDetector(*i).getType() == BETWEEN_DETECTOR) {
895 return false;
896 }
897 if (detectors.getDetector(*i).getType() == SOURCE_DETECTOR) {
898 return true;
899 }
900 }
901 } else {
902 if (myAmInHighwayMode && edge->getSpeedLimit() < 19.) {
903 return false;
904 }
905 }
906 }
907
908 if (myApproachedEdges.find(edge) == myApproachedEdges.end()) {
909 return false;
910 }
911
912 const ROEdgeVector& appr = myApproachedEdges.find(edge)->second;
913 bool isall = false;
914 for (int i = 0; i < (int)appr.size() && !isall; i++) {
915 //printf("checking %s->\n", appr[i].c_str());
916 bool had = std::find(seen.begin(), seen.end(), appr[i]) != seen.end();
917 if (!had) {
918 if (isFalseSource(det, appr[i], seen, detectors)) {
919 isall = true;
920 }
921 }
922 }
923 return isall;
924 }
925
926
927 void
buildEdgeFlowMap(const RODFDetectorFlows & flows,const RODFDetectorCon & detectors,SUMOTime startTime,SUMOTime endTime,SUMOTime stepOffset)928 RODFNet::buildEdgeFlowMap(const RODFDetectorFlows& flows,
929 const RODFDetectorCon& detectors,
930 SUMOTime startTime, SUMOTime endTime,
931 SUMOTime stepOffset) {
932 std::map<ROEdge*, std::vector<std::string>, idComp>::iterator i;
933 double speedFactorSumPKW = 0;
934 double speedFactorSumLKW = 0;
935 double speedFactorCountPKW = 0;
936 double speedFactorCountLKW = 0;
937 for (i = myDetectorsOnEdges.begin(); i != myDetectorsOnEdges.end(); ++i) {
938 ROEdge* into = (*i).first;
939 const double maxSpeedPKW = into->getVClassMaxSpeed(SVC_PASSENGER);
940 const double maxSpeedLKW = into->getVClassMaxSpeed(SVC_TRUCK);
941
942 const std::vector<std::string>& dets = (*i).second;
943 std::map<double, std::vector<std::string> > cliques;
944 std::vector<std::string>* maxClique = nullptr;
945 for (std::vector<std::string>::const_iterator j = dets.begin(); j != dets.end(); ++j) {
946 if (!flows.knows(*j)) {
947 continue;
948 }
949 const RODFDetector& det = detectors.getDetector(*j);
950 bool found = false;
951 for (std::map<double, std::vector<std::string> >::iterator k = cliques.begin(); !found && k != cliques.end(); ++k) {
952 if (fabs((*k).first - det.getPos()) < 1) {
953 (*k).second.push_back(*j);
954 if ((*k).second.size() > maxClique->size()) {
955 maxClique = &(*k).second;
956 }
957 found = true;
958 }
959 }
960 if (!found) {
961 cliques[det.getPos()].push_back(*j);
962 maxClique = &cliques[det.getPos()];
963 }
964 }
965 if (maxClique == nullptr) {
966 continue;
967 }
968 std::vector<FlowDef> mflows; // !!! reserve
969 for (SUMOTime t = startTime; t < endTime; t += stepOffset) {
970 FlowDef fd;
971 fd.qPKW = 0;
972 fd.qLKW = 0;
973 fd.vLKW = 0;
974 fd.vPKW = 0;
975 fd.fLKW = 0;
976 fd.isLKW = 0;
977 mflows.push_back(fd);
978 }
979 for (std::vector<std::string>::iterator l = maxClique->begin(); l != maxClique->end(); ++l) {
980 bool didWarn = false;
981 const std::vector<FlowDef>& dflows = flows.getFlowDefs(*l);
982 int index = 0;
983 for (SUMOTime t = startTime; t < endTime; t += stepOffset, index++) {
984 const FlowDef& srcFD = dflows[index];
985 FlowDef& fd = mflows[index];
986 fd.qPKW += srcFD.qPKW;
987 fd.qLKW += srcFD.qLKW;
988 fd.vLKW += srcFD.vLKW / (double) maxClique->size();
989 fd.vPKW += srcFD.vPKW / (double) maxClique->size();
990 fd.fLKW += srcFD.fLKW / (double) maxClique->size();
991 fd.isLKW += srcFD.isLKW / (double) maxClique->size();
992 const double speedFactorPKW = srcFD.vPKW / 3.6 / maxSpeedPKW;
993 const double speedFactorLKW = srcFD.vLKW / 3.6 / maxSpeedLKW;
994 myMaxSpeedFactorPKW = MAX2(myMaxSpeedFactorPKW, speedFactorPKW);
995 myMaxSpeedFactorLKW = MAX2(myMaxSpeedFactorLKW, speedFactorLKW);
996 speedFactorCountPKW += srcFD.qPKW;
997 speedFactorCountLKW += srcFD.qLKW;
998 speedFactorSumPKW += srcFD.qPKW * speedFactorPKW;
999 speedFactorSumLKW += srcFD.qLKW * speedFactorLKW;
1000 if (!didWarn && srcFD.vPKW > 0 && srcFD.vPKW < 255 && srcFD.vPKW / 3.6 > into->getSpeedLimit()) {
1001 WRITE_MESSAGE("Detected PKW speed (" + toString(srcFD.vPKW / 3.6, 3) + ") higher than allowed speed (" + toString(into->getSpeedLimit(), 3) + ") at '" + (*l) + "' on edge '" + into->getID() + "'.");
1002 didWarn = true;
1003 }
1004 if (!didWarn && srcFD.vLKW > 0 && srcFD.vLKW < 255 && srcFD.vLKW / 3.6 > into->getSpeedLimit()) {
1005 WRITE_MESSAGE("Detected LKW speed (" + toString(srcFD.vLKW / 3.6, 3) + ") higher than allowed speed (" + toString(into->getSpeedLimit(), 3) + ") at '" + (*l) + "' on edge '" + into->getID() + "'.");
1006 didWarn = true;
1007 }
1008 }
1009 }
1010 static_cast<RODFEdge*>(into)->setFlows(mflows);
1011 }
1012 // @note: this assumes that the speedFactors are independent of location and time
1013 if (speedFactorCountPKW > 0) {
1014 myAvgSpeedFactorPKW = speedFactorSumPKW / speedFactorCountPKW;
1015 WRITE_MESSAGE("Average speedFactor for PKW is " + toString(myAvgSpeedFactorPKW) + " maximum speedFactor is " + toString(myMaxSpeedFactorPKW) + ".");
1016 }
1017 if (speedFactorCountLKW > 0) {
1018 myAvgSpeedFactorLKW = speedFactorSumLKW / speedFactorCountLKW;
1019 WRITE_MESSAGE("Average speedFactor for LKW is " + toString(myAvgSpeedFactorLKW) + " maximum speedFactor is " + toString(myMaxSpeedFactorLKW) + ".");
1020 }
1021
1022 }
1023
1024
1025 void
buildDetectorDependencies(RODFDetectorCon & detectors)1026 RODFNet::buildDetectorDependencies(RODFDetectorCon& detectors) {
1027 // !!! this will not work when several detectors are lying on the same edge on different positions
1028
1029
1030 buildDetectorEdgeDependencies(detectors);
1031 // for each detector, compute the lists of predecessor and following detectors
1032 std::map<std::string, ROEdge*>::const_iterator i;
1033 for (i = myDetectorEdges.begin(); i != myDetectorEdges.end(); ++i) {
1034 const RODFDetector& det = detectors.getDetector((*i).first);
1035 if (!det.hasRoutes()) {
1036 continue;
1037 }
1038 // mark current detectors
1039 std::vector<RODFDetector*> last;
1040 {
1041 const std::vector<std::string>& detNames = myDetectorsOnEdges.find((*i).second)->second;
1042 for (std::vector<std::string>::const_iterator j = detNames.begin(); j != detNames.end(); ++j) {
1043 last.push_back(&detectors.getModifiableDetector(*j));
1044 }
1045 }
1046 // iterate over the current detector's routes
1047 const std::vector<RODFRouteDesc>& routes = det.getRouteVector();
1048 for (std::vector<RODFRouteDesc>::const_iterator j = routes.begin(); j != routes.end(); ++j) {
1049 const ROEdgeVector& edges2Pass = (*j).edges2Pass;
1050 for (ROEdgeVector::const_iterator k = edges2Pass.begin() + 1; k != edges2Pass.end(); ++k) {
1051 if (myDetectorsOnEdges.find(*k) != myDetectorsOnEdges.end()) {
1052 const std::vector<std::string>& detNames = myDetectorsOnEdges.find(*k)->second;
1053 // ok, consecutive detector found
1054 for (std::vector<RODFDetector*>::iterator l = last.begin(); l != last.end(); ++l) {
1055 // mark as follower of current
1056 for (std::vector<std::string>::const_iterator m = detNames.begin(); m != detNames.end(); ++m) {
1057 detectors.getModifiableDetector(*m).addPriorDetector(*l);
1058 (*l)->addFollowingDetector(&detectors.getDetector(*m));
1059 }
1060 }
1061 last.clear();
1062 for (std::vector<std::string>::const_iterator m = detNames.begin(); m != detNames.end(); ++m) {
1063 last.push_back(&detectors.getModifiableDetector(*m));
1064 }
1065 }
1066 }
1067 }
1068 }
1069 }
1070
1071
1072 void
mesoJoin(RODFDetectorCon & detectors,RODFDetectorFlows & flows)1073 RODFNet::mesoJoin(RODFDetectorCon& detectors, RODFDetectorFlows& flows) {
1074 buildDetectorEdgeDependencies(detectors);
1075 std::map<ROEdge*, std::vector<std::string>, idComp>::iterator i;
1076 for (i = myDetectorsOnEdges.begin(); i != myDetectorsOnEdges.end(); ++i) {
1077 const std::vector<std::string>& dets = (*i).second;
1078 std::map<double, std::vector<std::string> > cliques;
1079 // compute detector cliques
1080 for (std::vector<std::string>::const_iterator j = dets.begin(); j != dets.end(); ++j) {
1081 const RODFDetector& det = detectors.getDetector(*j);
1082 bool found = false;
1083 for (std::map<double, std::vector<std::string> >::iterator k = cliques.begin(); !found && k != cliques.end(); ++k) {
1084 if (fabs((*k).first - det.getPos()) < 10.) {
1085 (*k).second.push_back(*j);
1086 found = true;
1087 }
1088 }
1089 if (!found) {
1090 cliques[det.getPos()] = std::vector<std::string>();
1091 cliques[det.getPos()].push_back(*j);
1092 }
1093 }
1094 // join detector cliques
1095 for (std::map<double, std::vector<std::string> >::iterator m = cliques.begin(); m != cliques.end(); ++m) {
1096 std::vector<std::string> clique = (*m).second;
1097 // do not join if only one
1098 if (clique.size() == 1) {
1099 continue;
1100 }
1101 std::string nid;
1102 for (std::vector<std::string>::iterator n = clique.begin(); n != clique.end(); ++n) {
1103 std::cout << *n << " ";
1104 if (n != clique.begin()) {
1105 nid = nid + "_";
1106 }
1107 nid = nid + *n;
1108 }
1109 std::cout << ":" << nid << std::endl;
1110 flows.mesoJoin(nid, (*m).second);
1111 detectors.mesoJoin(nid, (*m).second);
1112 }
1113 }
1114 }
1115
1116
1117
1118 /****************************************************************************/
1119
1120