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