Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2024 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file ROHelper.cpp
15 : /// @author Daniel Krajzewicz
16 : /// @author Michael Behrisch
17 : /// @date Sept 2002
18 : ///
19 : // Some helping methods for router
20 : /****************************************************************************/
21 : #include <config.h>
22 :
23 : #include <functional>
24 : #include <vector>
25 : #include "ROEdge.h"
26 : #include "ROVehicle.h"
27 : #include "ROHelper.h"
28 :
29 :
30 : // ===========================================================================
31 : // class definitions
32 : // ===========================================================================
33 :
34 :
35 : namespace ROHelper {
36 : void
37 4588 : recheckForLoops(ConstROEdgeVector& edges, const ConstROEdgeVector& mandatory) {
38 : // for simplicities sake, prevent removal of any mandatory edges
39 : // in theory these edges could occur multiple times so it might be possible
40 : // to delete some of them anyway.
41 : // XXX check for departLane, departPos, departSpeed, ....
42 :
43 : // removal of edge loops within the route (edge occurs twice)
44 : // call repeatedly until no more loops have been found
45 : bool findLoop = true;
46 9188 : while (findLoop) {
47 : findLoop = false;
48 : std::map<const ROEdge*, int> lastOccurrence; // index of the last occurrence of this edge
49 61364 : for (int ii = 0; ii < (int)edges.size(); ++ii) {
50 56776 : std::map<const ROEdge*, int>::iterator it_pre = lastOccurrence.find(edges[ii]);
51 56792 : if (it_pre != lastOccurrence.end() &&
52 56792 : noMandatory(mandatory, edges.begin() + it_pre->second, edges.begin() + ii)) {
53 12 : edges.erase(edges.begin() + it_pre->second, edges.begin() + ii);
54 : ii = it_pre->second;
55 : findLoop = true;
56 : break;
57 : } else {
58 56764 : lastOccurrence[edges[ii]] = ii;
59 : }
60 : }
61 : }
62 :
63 : // remove loops at the route's begin
64 : // (vehicle makes a turnaround to get into the right direction at an already passed node)
65 4588 : const RONode* start = edges[0]->getFromJunction();
66 4588 : if (start == nullptr && edges.size() > 1) {
67 : // taz edge has no fromJunction
68 4 : start = edges[1]->getFromJunction();
69 : }
70 4588 : if (start != nullptr) {
71 : int lastStart = 0;
72 56716 : for (int i = 1; i < (int)edges.size(); i++) {
73 52128 : if (edges[i]->getFromJunction() == start) {
74 : lastStart = i;
75 : }
76 : }
77 4588 : if (lastStart > 0 && noMandatory(mandatory, edges.begin(), edges.begin() + lastStart - 1)) {
78 : edges.erase(edges.begin(), edges.begin() + lastStart - 1);
79 : }
80 : }
81 : // remove loops at the route's end
82 : // (vehicle makes a turnaround to get into the right direction at an already passed node)
83 4588 : const RONode* end = edges.back()->getToJunction();
84 4588 : if (end == nullptr && edges.size() > 1) {
85 : // taz edge has no toJunction
86 4 : end = edges[edges.size() - 2]->getToJunction();
87 : }
88 4588 : if (end != nullptr) {
89 55824 : for (int i = 0; i < (int)edges.size() - 1; i++) {
90 51354 : if (edges[i]->getToJunction() == end && noMandatory(mandatory, edges.begin() + i + 2, edges.end())) {
91 : edges.erase(edges.begin() + i + 2, edges.end());
92 118 : break;
93 : }
94 : }
95 : }
96 :
97 : // removal of node loops (node occurs twice) is not done because these may occur legitimately
98 : /*
99 : std::vector<RONode*> nodes;
100 : for (ConstROEdgeVector::iterator i = edges.begin(); i != edges.end(); ++i) {
101 : nodes.push_back((*i)->getFromJunction());
102 : }
103 : nodes.push_back(edges.back()->getToJunction());
104 : bool changed = false;
105 : do {
106 : changed = false;
107 : for (int b = 0; b < nodes.size() && !changed; ++b) {
108 : RONode* bn = nodes[b];
109 : for (int e = b + 1; e < nodes.size() && !changed; ++e) {
110 : if (bn == nodes[e]) {
111 : changed = true;
112 : nodes.erase(nodes.begin() + b, nodes.begin() + e);
113 : edges.erase(edges.begin() + b, edges.begin() + e);
114 : }
115 : }
116 : }
117 : } while (changed);
118 : */
119 4588 : }
120 :
121 : bool
122 264 : noMandatory(const ConstROEdgeVector& mandatory,
123 : ConstROEdgeVector::const_iterator start,
124 : ConstROEdgeVector::const_iterator end) {
125 264 : for (const ROEdge* m : mandatory) {
126 32 : for (auto it = start; it != end; it++) {
127 32 : if (*it == m) {
128 : return false;
129 : }
130 : }
131 : }
132 : return true;
133 : }
134 :
135 :
136 : }
137 :
138 :
139 : /****************************************************************************/
|
