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        5112 : 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       10236 :     while (findLoop) {
      47             :         findLoop = false;
      48             :         std::map<const ROEdge*, int> lastOccurrence; // index of the last occurrence of this edge
      49       78280 :         for (int ii = 0; ii < (int)edges.size(); ++ii) {
      50       73168 :             std::map<const ROEdge*, int>::iterator it_pre = lastOccurrence.find(edges[ii]);
      51       73184 :             if (it_pre != lastOccurrence.end() &&
      52       73184 :                     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       73156 :                 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        5112 :     const RONode* start = edges[0]->getFromJunction();
      66        5112 :     if (start == nullptr && edges.size() > 1) {
      67             :         // taz edge has no fromJunction
      68           4 :         start = edges[1]->getFromJunction();
      69             :     }
      70        5112 :     if (start != nullptr) {
      71             :         int lastStart = 0;
      72       73108 :         for (int i = 1; i < (int)edges.size(); i++) {
      73       67996 :             if (edges[i]->getFromJunction() == start) {
      74             :                 lastStart = i;
      75             :             }
      76             :         }
      77        5112 :         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        5112 :     const RONode* end = edges.back()->getToJunction();
      84        5112 :     if (end == nullptr && edges.size() > 1) {
      85             :         // taz edge has no toJunction
      86           4 :         end = edges[edges.size() - 2]->getToJunction();
      87             :     }
      88        5112 :     if (end != nullptr) {
      89       71284 :         for (int i = 0; i < (int)edges.size() - 1; i++) {
      90       66400 :             if (edges[i]->getToJunction() == end && noMandatory(mandatory, edges.begin() + i + 2, edges.end())) {
      91             :                 edges.erase(edges.begin() + i + 2, edges.end());
      92         228 :                 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        5112 : }
     120             : 
     121             : bool
     122         488 : noMandatory(const ConstROEdgeVector& mandatory,
     123             :             ConstROEdgeVector::const_iterator start,
     124             :             ConstROEdgeVector::const_iterator end) {
     125         488 :     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             : /****************************************************************************/