sumolib.net

   1# Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
   2# Copyright (C) 2008-2026 German Aerospace Center (DLR) and others.
   3# This program and the accompanying materials are made available under the
   4# terms of the Eclipse Public License 2.0 which is available at
   5# https://www.eclipse.org/legal/epl-2.0/
   6# This Source Code may also be made available under the following Secondary
   7# Licenses when the conditions for such availability set forth in the Eclipse
   8# Public License 2.0 are satisfied: GNU General Public License, version 2
   9# or later which is available at
  10# https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
  11# SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
  12
  13# @file    __init__.py
  14# @author  Daniel Krajzewicz
  15# @author  Laura Bieker
  16# @author  Karol Stosiek
  17# @author  Michael Behrisch
  18# @author  Jakob Erdmann
  19# @author  Robert Hilbrich
  20# @author  Mirko Barthauer
  21# @date    2008-03-27
  22
  23"""
  24This file contains a content handler for parsing sumo network xml files.
  25It uses other classes from this module to represent the road network.
  26"""
  27
  28from __future__ import print_function
  29from __future__ import absolute_import
  30import sys
  31import math
  32import heapq
  33import gzip
  34import warnings
  35import io
  36from xml.sax import handler, parse
  37from copy import copy
  38from collections import defaultdict
  39from itertools import chain
  40try:
  41    from functools import lru_cache
  42    HAVE_LRU_CACHE = True
  43except ImportError:
  44    HAVE_LRU_CACHE = False
  45
  46try:
  47    import lxml.etree
  48    import pathlib
  49    HAVE_LXML = True
  50except ImportError:
  51    HAVE_LXML = False
  52
  53try:
  54    import pyproj  # noqa
  55    HAVE_PYPROJ = True
  56except ImportError:
  57    HAVE_PYPROJ = False
  58
  59import sumolib
  60from . import lane, edge, netshiftadaptor, node, connection, roundabout  # noqa
  61from .connection import Connection
  62from sumolib.miscutils import intIfPossible
  63
  64
  65class TLS:
  66
  67    """Traffic Light Signal for a sumo network"""
  68
  69    def __init__(self, id):
  70        self._id = id
  71        self._connections = []
  72        self._maxConnectionNo = -1
  73        self._programs = {}
  74
  75    def addConnection(self, inLane, outLane, linkNo):
  76        self._connections.append([inLane, outLane, linkNo])
  77        if linkNo > self._maxConnectionNo:
  78            self._maxConnectionNo = linkNo
  79
  80    def getConnections(self):
  81        return self._connections
  82
  83    def getID(self):
  84        return self._id
  85
  86    def getLinks(self):
  87        links = {}
  88        for the_connection in self._connections:
  89            if the_connection[2] not in links:
  90                links[the_connection[2]] = []
  91            links[the_connection[2]].append(the_connection)
  92        return links
  93
  94    def getEdges(self):
  95        edges = set()
  96        for c in self._connections:
  97            edges.add(c[0].getEdge())
  98        return edges
  99
 100    def addProgram(self, program):
 101        self._programs[program._id] = program
 102
 103    def removePrograms(self):
 104        self._programs.clear()
 105
 106    def toXML(self):
 107        ret = ""
 108        for p in self._programs:
 109            ret = ret + self._programs[p].toXML(self._id)
 110        return ret
 111
 112    def getPrograms(self):
 113        return self._programs
 114
 115
 116class Phase:
 117
 118    def __init__(self, duration, state, minDur=None, maxDur=None, next=tuple(), name="", earlyTarget=""):
 119        """
 120        Constructs a traffic light phase
 121        duration (float): the duration of the phase in seconds
 122        state (string): the state codes for each controlled link
 123        minDur (float): the minimum duration (ignored by static tls)
 124        maxDur (float): the maximum duration (ignored by static tls)
 125        next (intList): possible succesor phase (optional)
 126        name (string): the name of the phase
 127        earlyTarget (string): early switching to phase with the given index(es)
 128        """
 129        self.duration = duration
 130        self.state = state
 131        # minimum and maximum duration (only for actuated tls)
 132        self.minDur = minDur if minDur is not None else duration
 133        self.maxDur = maxDur if maxDur is not None else duration
 134        self.next = next
 135        self.name = name
 136        self.earlyTarget = earlyTarget
 137
 138    def __repr__(self):
 139        name = (", name='%s'" % self.name) if self.name else ""
 140        next = (", next='%s'" % str(self.next)) if self.next else ""
 141        earlyTarget = (", earlyTarget='%s'" % self.earlyTarget) if self.earlyTarget else ""
 142        return ("Phase(duration=%s, state='%s', minDur=%s, maxDur=%s%s%s%s)"
 143                % (self.duration, self.state, self.minDur, self.maxDur, name, next, earlyTarget))
 144
 145
 146class TLSProgram:
 147
 148    def __init__(self, id, offset, type):
 149        self._id = id
 150        self._type = type
 151        self._offset = offset
 152        self._phases = []
 153        self._params = {}
 154        self._conditions = {}
 155
 156    def addPhase(self, state, duration, minDur=-1, maxDur=-1, next=None, name="", earlyTarget=""):
 157        self._phases.append(Phase(duration, state, minDur, maxDur, next, name, earlyTarget))
 158
 159    def addCondition(self, id, value):
 160        self._conditions[id] = value
 161
 162    def toXML(self, tlsID):
 163        ret = '  <tlLogic id="%s" type="%s" programID="%s" offset="%s">\n' % (
 164            tlsID, self._type, self._id, self._offset)
 165        for p in self._phases:
 166            minDur = '' if p.minDur < 0 else ' minDur="%s"' % p.minDur
 167            maxDur = '' if p.maxDur < 0 else ' maxDur="%s"' % p.maxDur
 168            name = '' if p.name == '' else ' name="%s"' % p.name
 169            next = '' if len(p.next) == 0 else ' next="%s"' % ' '.join(map(str, p.next))
 170            earlyTarget = '' if p.earlyTarget == '' else ' earlyTarget="%s"' % p.earlyTarget
 171            ret += '    <phase duration="%s" state="%s"%s%s%s%s%s/>\n' % (
 172                p.duration, p.state, minDur, maxDur, name, next, earlyTarget)
 173        for k, v in self._params.items():
 174            ret += '    <param key="%s" value="%s"/>\n' % (k, v)
 175        for i, v in self._conditions.items():
 176            ret += '    <condition id="%s" value="%s"/>\n' % (i, v)
 177        ret += '  </tlLogic>\n'
 178        return ret
 179
 180    def getPhases(self):
 181        return self._phases
 182
 183    def getType(self):
 184        return self._type
 185
 186    def setParam(self, key, value):
 187        self._params[key] = value
 188
 189    def getParam(self, key, default=None):
 190        return self._params.get(key, default)
 191
 192    def getParams(self):
 193        return self._params
 194
 195    def getStages(self):
 196        stages = dict()
 197        for idx, phase in enumerate(self.getPhases()):
 198            if phase not in stages.values():
 199                if 'G' in phase.state and 'y' not in phase.state and phase.name:
 200                    stages[idx] = phase
 201        return stages
 202
 203    def getOffset(self):
 204        return self._offset
 205
 206
 207class EdgeType:
 208    def __init__(self, id, allow, disallow):
 209        self.id = id
 210        self.allow = allow
 211        self.disallow = disallow
 212
 213
 214class Net:
 215
 216    """The whole sumo network."""
 217
 218    def __init__(self):
 219        self._location = {}
 220        self._id2node = {}
 221        self._id2edge = {}
 222        self._crossings_and_walkingAreas = set()
 223        self._macroConnectors = set()
 224        self._id2tls = {}
 225        self._nodes = []
 226        self._edges = []
 227        self._tlss = []
 228        self._ranges = [[sys.float_info.max, -sys.float_info.max], [sys.float_info.max, -sys.float_info.max]]
 229        self._roundabouts = []
 230        self._rtreeEdges = None
 231        self._rtreeLanes = None
 232        self._allLanes = []
 233        self._origIdx = None
 234        self._proj = None
 235        self.hasInternal = False
 236        self.hasWalkingArea = False
 237        # store dijsktra heap for reuse if the same origin is used repeatedly
 238        self._shortestPathCache = None
 239        self._version = None
 240        self._edgeTypes = defaultdict(lambda: EdgeType("DEFAULT_EDGETYPE", "", ""))
 241        self._routingCache = None
 242
 243    def initRoutingCache(self, maxsize=1000):
 244        self._routingCache = lru_cache(maxsize=maxsize)(lambda fromEdge, fromPos, fastest, vClass, ignoreDirection, reversalPenalty, preferences: {})  # noqa
 245
 246    def getVersion(self):
 247        return self._version
 248
 249    def getEdgeType(self, typeID):
 250        return self._edgeTypes[typeID]
 251
 252    def setLocation(self, netOffset, convBoundary, origBoundary, projParameter):
 253        self._location["netOffset"] = netOffset
 254        self._location["convBoundary"] = convBoundary
 255        self._location["origBoundary"] = origBoundary
 256        self._location["projParameter"] = projParameter
 257
 258    def loadSelection(self, selectionFile):
 259        self.resetSelection()
 260        with io.open(selectionFile, "r", encoding="utf-8") as f:
 261            for line in f:
 262                line = line.strip()
 263                if line.startswith("edge:"):
 264                    edgeID = line[5:]
 265                    if edgeID in self._id2edge:
 266                        self.getEdge(edgeID).select()
 267                elif line.startswith("junction:"):
 268                    nodeID = line[9:]
 269                    if nodeID in self._id2node:
 270                        self.getNode(nodeID).select()
 271
 272    def resetSelection(self):
 273        for n in self._nodes:
 274            n.select(False)
 275        for e in self._edges:
 276            e.select(False)
 277
 278    def addNode(self, id, type=None, coord=None, incLanes=None, intLanes=None):
 279        if id is None:
 280            return None
 281        if id not in self._id2node:
 282            n = node.Node(id, type, coord, incLanes, intLanes)
 283            self._nodes.append(n)
 284            self._id2node[id] = n
 285        self.setAdditionalNodeInfo(
 286            self._id2node[id], type, coord, incLanes, intLanes)
 287        return self._id2node[id]
 288
 289    def setAdditionalNodeInfo(self, node, type, coord, incLanes, intLanes=None):
 290        if coord is not None and node._coord is None:
 291            node._coord = coord
 292            self._ranges[0][0] = min(self._ranges[0][0], coord[0])
 293            self._ranges[0][1] = max(self._ranges[0][1], coord[0])
 294            self._ranges[1][0] = min(self._ranges[1][0], coord[1])
 295            self._ranges[1][1] = max(self._ranges[1][1], coord[1])
 296        if incLanes is not None and node._incLanes is None:
 297            node._incLanes = incLanes
 298        if intLanes is not None and node._intLanes is None:
 299            node._intLanes = intLanes
 300        if type is not None and node._type is None:
 301            node._type = type
 302
 303    def addEdge(self, id, fromID, toID, prio, function, name, edgeType='', routingType=''):
 304        if id not in self._id2edge:
 305            fromN = self.addNode(fromID)
 306            toN = self.addNode(toID)
 307            e = edge.Edge(id, fromN, toN, prio, function, name, edgeType, routingType)
 308            self._edges.append(e)
 309            self._id2edge[id] = e
 310            if function:
 311                self.hasInternal = True
 312                if function == "walkingarea":
 313                    self.hasWalkingArea = True
 314        return self._id2edge[id]
 315
 316    def addLane(self, edge, speed, length, width, allow=None, disallow=None, acceleration=False):
 317        return lane.Lane(edge, speed, length, width, allow, disallow, acceleration)
 318
 319    def addRoundabout(self, nodes, edges=None):
 320        r = roundabout.Roundabout(nodes, edges)
 321        self._roundabouts.append(r)
 322        return r
 323
 324    def addConnection(self, fromEdge, toEdge, fromlane, tolane, direction,
 325                      tls, tllink, tllink2, allow, disallow, state, viaLaneID=None):
 326        conn = connection.Connection(
 327            fromEdge, toEdge, fromlane, tolane, direction,
 328            tls, tllink, tllink2, allow, disallow, state, viaLaneID)
 329        fromEdge.addOutgoing(conn)
 330        fromlane.addOutgoing(conn)
 331        toEdge._addIncoming(conn)
 332        if viaLaneID:
 333            try:
 334                # internal lanes are only available when building with option withInternal=True
 335                viaLane = self.getLane(viaLaneID)
 336                viaEdge = viaLane.getEdge()
 337                viaEdge._addIncoming(connection.Connection(
 338                    fromEdge, viaEdge, fromlane, viaLane, direction, tls,
 339                    tllink, tllink2, allow, disallow, state, ''))
 340            except Exception:
 341                pass
 342        return conn
 343
 344    def getEdges(self, withInternal=True):
 345        if not withInternal:
 346            return [e for e in self._edges if e.getFunction() == '']
 347        else:
 348            return self._edges
 349
 350    def getRoundabouts(self):
 351        return self._roundabouts
 352
 353    def hasEdge(self, id):
 354        return id in self._id2edge
 355
 356    def getEdge(self, id):
 357        return self._id2edge[id]
 358
 359    def getLane(self, laneID):
 360        edge_id, lane_index = laneID.rsplit("_", 1)
 361        return self.getEdge(edge_id).getLane(int(lane_index))
 362
 363    def _initRTree(self, shapeList, includeJunctions=True):
 364        import rtree  # noqa
 365        result = rtree.index.Index()
 366        result.interleaved = True
 367        for ri, shape in enumerate(shapeList):
 368            result.add(ri, shape.getBoundingBox(includeJunctions))
 369        return result
 370
 371    # Please be aware that the resulting list of edges is NOT sorted
 372    def getNeighboringEdges(self, x, y, r=0.1, includeJunctions=True, allowFallback=True):
 373        edges = []
 374        try:
 375            if self._rtreeEdges is None:
 376                self._rtreeEdges = self._initRTree(self._edges, includeJunctions)
 377            for i in self._rtreeEdges.intersection((x - r, y - r, x + r, y + r)):
 378                e = self._edges[i]
 379                d = sumolib.geomhelper.distancePointToPolygon(
 380                    (x, y), e.getShape(includeJunctions))
 381                if d < r:
 382                    edges.append((e, d))
 383        except ImportError:
 384            if not allowFallback:
 385                raise
 386            warnings.warn("Module 'rtree' not available. Using brute-force fallback.")
 387            for the_edge in self._edges:
 388                d = sumolib.geomhelper.distancePointToPolygon((x, y), the_edge.getShape(includeJunctions))
 389                if d < r:
 390                    edges.append((the_edge, d))
 391        return edges
 392
 393    def getNeighboringLanes(self, x, y, r=0.1, includeJunctions=True, allowFallback=True):
 394        lanes = []
 395        try:
 396            if self._rtreeLanes is None:
 397                for the_edge in self._edges:
 398                    self._allLanes += the_edge.getLanes()
 399                self._rtreeLanes = self._initRTree(self._allLanes, includeJunctions)
 400            for i in self._rtreeLanes.intersection((x - r, y - r, x + r, y + r)):
 401                the_lane = self._allLanes[i]
 402                d = sumolib.geomhelper.distancePointToPolygon((x, y), the_lane.getShape(includeJunctions))
 403                if d < r:
 404                    lanes.append((the_lane, d))
 405        except ImportError:
 406            if not allowFallback:
 407                raise
 408            warnings.warn("Module 'rtree' not available. Using brute-force fallback.")
 409            for the_edge in self._edges:
 410                for the_lane in the_edge.getLanes():
 411                    d = sumolib.geomhelper.distancePointToPolygon((x, y), the_lane.getShape(includeJunctions))
 412                    if d < r:
 413                        lanes.append((the_lane, d))
 414        return lanes
 415
 416    def hasNode(self, id):
 417        return id in self._id2node
 418
 419    def getNode(self, id):
 420        return self._id2node[id]
 421
 422    def getNodes(self):
 423        return self._nodes
 424
 425    def getTLS(self, tlid):
 426        return self._id2tls[tlid]
 427
 428    def getTLSSecure(self, tlid):
 429        if tlid in self._id2tls:
 430            tls = self._id2tls[tlid]
 431        else:
 432            tls = TLS(tlid)
 433            self._id2tls[tlid] = tls
 434            self._tlss.append(tls)
 435        return tls
 436
 437    def getTrafficLights(self):
 438        return self._tlss
 439
 440    def addTLS(self, tlid, inLane, outLane, linkNo):
 441        tls = self.getTLSSecure(tlid)
 442        tls.addConnection(inLane, outLane, linkNo)
 443        return tls
 444
 445    def addTLSProgram(self, tlid, programID, offset, type, removeOthers):
 446        tls = self.getTLSSecure(tlid)
 447        program = TLSProgram(programID, offset, type)
 448        if removeOthers:
 449            tls.removePrograms()
 450        tls.addProgram(program)
 451        return program
 452
 453    def setFoes(self, junctionID, index, foes, prohibits):
 454        self._id2node[junctionID].setFoes(index, foes, prohibits)
 455
 456    def forbids(self, possProhibitor, possProhibited):
 457        return possProhibitor.getFrom().getToNode().forbids(possProhibitor, possProhibited)
 458
 459    def getUpstreamEdges(self, edge, distance, stopOnTLS, stopOnTurnaround):
 460        """return a list of lists of the form
 461           [[firstEdge, pos, [edge_0, edge_1, ..., edge_k], aborted], ...]
 462           where
 463             firstEdge: is the upstream edge furthest away from the intersection,
 464             [edge_0, ..., edge_k]: is the list of edges from the intersection upstream to firstEdge
 465             pos: is the position on firstEdge with distance to the end of the input edge
 466             aborted: a flag indicating whether the downstream
 467                 search stopped at a TLS or a node without incoming edges before reaching the distance threshold
 468        """
 469        ret = []
 470        seen = set()
 471        toProc = []
 472        toProc.append([edge, 0, []])
 473        while not len(toProc) == 0:
 474            ie = toProc.pop()
 475            if ie[0] in seen:
 476                continue
 477            seen.add(ie[0])
 478            if ie[1] + ie[0].getLength() >= distance:
 479                ret.append(
 480                    [ie[0], ie[0].getLength() + ie[1] - distance, ie[2], False])
 481                continue
 482            if len(ie[0]._incoming) == 0:
 483                ret.append([ie[0], ie[0].getLength() + ie[1], ie[2], True])
 484                continue
 485            mn = []
 486            stop = False
 487            for ci in ie[0]._incoming:
 488                if ci not in seen:
 489                    prev = copy(ie[2])
 490                    if stopOnTLS and ci._tls and ci != edge and not stop:
 491                        ret.append([ie[0], ie[1], prev, True])
 492                        stop = True
 493                    elif (stopOnTurnaround and ie[0]._incoming[ci][0].getDirection() == Connection.LINKDIR_TURN and
 494                          not stop):
 495                        ret.append([ie[0], ie[1], prev, True])
 496                        stop = True
 497                    else:
 498                        prev.append(ie[0])
 499                        mn.append([ci, ie[0].getLength() + ie[1], prev])
 500            if not stop:
 501                toProc.extend(mn)
 502        return ret
 503
 504    def getEdgesByOrigID(self, origID):
 505        if self._origIdx is None:
 506            self._origIdx = defaultdict(set)
 507            for the_edge in self._edges:
 508                for the_lane in the_edge.getLanes():
 509                    for oID in the_lane.getParam("origId", "").split():
 510                        self._origIdx[oID].add(the_edge)
 511        return self._origIdx[origID]
 512
 513    def getGeometries(self, useLanes, includeJunctions=False):
 514        for e in self._edges:
 515            if useLanes:
 516                for the_lane in e.getLanes():
 517                    yield the_lane.getID(), the_lane.getShape(), the_lane.getWidth()
 518            else:
 519                yield e.getID(), e.getShape(includeJunctions), sum([the_lane.getWidth() for the_lane in e.getLanes()])
 520
 521    def getBBoxXY(self):
 522        """
 523        Get the bounding box (bottom left and top right coordinates) for a net;
 524        Coordinates are in X and Y (not Lat and Lon)
 525
 526        :return [(bottom_left_X, bottom_left_Y), (top_right_X, top_right_Y)]
 527        """
 528        return [(self._ranges[0][0], self._ranges[1][0]),
 529                (self._ranges[0][1], self._ranges[1][1])]
 530
 531    # the diagonal of the bounding box of all nodes
 532    def getBBoxDiameter(self):
 533        return math.sqrt(
 534            (self._ranges[0][0] - self._ranges[0][1]) ** 2 +
 535            (self._ranges[1][0] - self._ranges[1][1]) ** 2)
 536
 537    def hasGeoProj(self):
 538        projString = self._location["projParameter"]
 539        return projString != "!"
 540
 541    def getGeoProj(self):
 542        if not self.hasGeoProj() or not HAVE_PYPROJ:
 543            raise RuntimeError("Network does not provide geo-projection or pyproj not installed.")
 544        if self._proj is None:
 545            try:
 546                self._proj = pyproj.Proj(projparams=self._location["projParameter"])
 547            except RuntimeError:
 548                if hasattr(pyproj.datadir, 'set_data_dir'):
 549                    pyproj.datadir.set_data_dir('/usr/share/proj')
 550                    self._proj = pyproj.Proj(projparams=self._location["projParameter"])
 551                raise
 552        return self._proj
 553
 554    def getLocationOffset(self):
 555        """ offset to be added after converting from geo-coordinates to UTM"""
 556        return list(map(float, self._location["netOffset"].split(",")))
 557
 558    def getBoundary(self):
 559        """ return xmin,ymin,xmax,ymax network coordinates"""
 560        return list(map(float, self._location["convBoundary"].split(",")))
 561
 562    def convertLonLat2XY(self, lon, lat, rawUTM=False):
 563        x, y = self.getGeoProj()(lon, lat)
 564        if rawUTM:
 565            return x, y
 566        else:
 567            x_off, y_off = self.getLocationOffset()
 568            return x + x_off, y + y_off
 569
 570    def convertXY2LonLat(self, x, y, rawUTM=False):
 571        if not rawUTM:
 572            x_off, y_off = self.getLocationOffset()
 573            x -= x_off
 574            y -= y_off
 575        return self.getGeoProj()(x, y, inverse=True)
 576
 577    def move(self, dx, dy, dz=0):
 578        for n in self._nodes:
 579            n._coord = (n._coord[0] + dx, n._coord[1] + dy, n._coord[2] + dz)
 580        for e in self._edges:
 581            for _lane in e.getLanes():
 582                _lane.setShape([(p[0] + dx, p[1] + dy, p[2] + dz) for p in _lane.getShape3D()])
 583            e.rebuildShape()
 584
 585    def getInternalPath(self, conn, fastest=False):
 586        minInternalCost = 1e400
 587        minPath = None
 588        for c in conn:
 589            if c.getViaLaneID() != "":
 590                viaCost = 0
 591                viaID = c.getViaLaneID()
 592                viaPath = []
 593                while viaID != "":
 594                    viaLane = self.getLane(viaID)
 595                    viaCost += viaLane.getLength() if not fastest else viaLane.getLength() / viaLane.getSpeed()
 596                    viaID = viaLane.getOutgoing()[0].getViaLaneID()
 597                    viaPath.append(viaLane.getEdge())
 598                if viaCost < minInternalCost:
 599                    minInternalCost = viaCost
 600                    minPath = viaPath
 601        return minPath, minInternalCost
 602
 603    def getOptimalPath(self, fromEdge, toEdge, fastest=False, maxCost=1e400, vClass=None, reversalPenalty=0,
 604                       includeFromToCost=True, withInternal=False, ignoreDirection=False,
 605                       fromPos=None, toPos=None, preferences={}):
 606        """
 607        Finds the optimal (shortest or fastest) path for vClass from fromEdge to toEdge
 608        by using using Dijkstra's algorithm.
 609        It returns a pair of a tuple of edges and the cost.
 610        If no path is found the first element is None.
 611        The cost for the returned path is equal to the sum of all edge costs in the path,
 612        including the internal connectors, if they are present in the network.
 613        The path itself does not include internal edges except for the case
 614        when the start or end edge are internal edges.
 615        The search may be limited using the given threshold.
 616        The preferences declare a mapping from the 'routingType' of each edge to divisor
 617        that is applied to the computed cost of that edge (i.e. a preference of 2 reduces cost by a factor of 0.5).
 618        """
 619
 620        if preferences:
 621            if fastest:
 622                def speedFunc(edge):
 623                    return preferences.get(edge.getRoutingType(), 1.0) * edge.getSpeed()
 624            else:
 625                def speedFunc(edge):
 626                    return preferences.get(edge.getRoutingType(), 1.0)
 627        elif fastest:
 628            def speedFunc(edge):
 629                return edge.getSpeed()
 630        else:
 631            def speedFunc(edge):
 632                return 1.0
 633
 634        def remainder(edge, pos):
 635            if pos < 0:
 636                return min(-pos, edge.getLength())
 637            return max(0., edge.getLength() - pos)
 638
 639        def getToNormalIncoming(edge):
 640            if edge.getFunction() == '':
 641                return [(e, None) for e in edge.getToNode().getIncoming() if e.getFunction() == '']
 642            else:
 643                return []
 644
 645        if self.hasInternal:
 646            appendix = []
 647            appendixCost = 0.
 648            while toEdge.getFunction() == "internal":
 649                appendix = [toEdge] + appendix
 650                appendixCost += toEdge.getLength() / speedFunc(toEdge)
 651                toEdge = list(toEdge.getIncoming().keys())[0]
 652
 653        def finalizeCost(cost, path):
 654            if includeFromToCost:
 655                # add costs for (part of) the first edge, still needs to be fixed for wrong direction travel
 656                remainFrom = fromEdge.getLength() if fromPos is None else remainder(fromEdge, fromPos)
 657                cost += remainFrom / speedFunc(fromEdge)
 658                # remove costs for (part of) the last edge, still needs to be fixed for wrong direction travel
 659                removeTo = 0. if toPos is None else remainder(toEdge, toPos)
 660            else:
 661                removeTo = toEdge.getLength() if len(path) > 1 else 0.
 662            cost -= removeTo / speedFunc(toEdge)
 663            return cost
 664
 665        def constructPath(dist):
 666            # destination was already reached in a previous query
 667            cost, pred = dist[toEdge]
 668            path = [toEdge]
 669            while pred is not None:
 670                if self.hasInternal and withInternal:
 671                    viaPath, minInternalCost = self.getInternalPath(pred.getAllowedOutgoing(vClass).get(path[-1], []),
 672                                                                    fastest=fastest)
 673                    if viaPath is not None:
 674                        path += reversed(viaPath)
 675                path.append(pred)
 676                _, pred = dist[pred]
 677
 678            path.reverse()
 679            cost = finalizeCost(cost, path)
 680            assert cost >= 0
 681            if self.hasInternal:
 682                if appendix:
 683                    return tuple(path + appendix), cost + appendixCost
 684                elif ignoreDirection and self.hasWalkingArea and not withInternal:
 685                    return [e for e in path if e.getFunction() == ''], cost
 686            return tuple(path), cost
 687
 688        needLoop = (fromEdge == toEdge
 689                    and fromPos is not None
 690                    and toPos is not None
 691                    and fromPos > toPos
 692                    and not ignoreDirection)
 693
 694        seen = set()
 695        dist = {}
 696        q = []
 697        if self._routingCache is not None:
 698            if needLoop:
 699                # use cached results from all follower edges:
 700                bestCost = maxCost
 701                bestPath = None
 702                for e2, conn in fromEdge.getAllowedOutgoing(vClass).items():
 703                    path, cost = self.getOptimalPath(e2, toEdge, fastest=fastest, maxCost=maxCost, vClass=vClass,
 704                                                     reversalPenalty=reversalPenalty,
 705                                                     includeFromToCost=includeFromToCost,
 706                                                     withInternal=withInternal, fromPos=0, toPos=toPos,
 707                                                     preferences=preferences)
 708                    if path is not None and cost < bestCost:
 709                        bestPath = path
 710                        bestCost = cost
 711                if bestPath is not None:
 712                    path = [fromEdge]
 713                    if self.hasInternal and withInternal:
 714                        viaPath, minInternalCost = self.getInternalPath(
 715                            fromEdge.getAllowedOutgoing(vClass).get(path[0], []), fastest=fastest)
 716                        if viaPath is not None:
 717                            path += viaPath
 718                            bestCost += minInternalCost
 719                    path += list(bestPath)
 720                    if includeFromToCost:
 721                        bestCost += remainder(fromEdge, fromPos) / speedFunc(fromEdge)
 722                    return tuple(path), bestCost
 723                else:
 724                    return None, 1e400
 725
 726            dist = self._routingCache(fromEdge, fromPos, fastest, vClass, ignoreDirection, reversalPenalty,
 727                                      tuple(preferences.items()))
 728            if toEdge in dist:
 729                return constructPath(dist)
 730            else:
 731                # initialize heap from previous query
 732                q = []
 733                frontier = set(dist.keys())
 734                for cost, prev in dist.values():
 735                    frontier.discard(prev)
 736                for e in frontier:
 737                    cost, prev = dist[e]
 738                    heapq.heappush(q, (cost, e, prev))
 739        elif needLoop:
 740            # start search on successors of fromEdge
 741            for e2, conn in fromEdge.getAllowedOutgoing(vClass).items():
 742                q.append((e2.getLength() / speedFunc(e2), e2, fromEdge))
 743
 744        if len(dist) == 0:
 745            dist[fromEdge] = (0., None)
 746            if not needLoop:
 747                q.append((0., fromEdge, None))
 748
 749        while q:
 750            cost, e1, prev = heapq.heappop(q)
 751            if e1 in seen:
 752                continue
 753            seen.add(e1)
 754            if e1 == toEdge:
 755                return constructPath(dist)
 756            if cost > maxCost:
 757                return None, cost
 758
 759            for e2, conn in chain(e1.getAllowedOutgoing(vClass).items(),
 760                                  e1.getIncoming().items() if ignoreDirection else [],
 761                                  getToNormalIncoming(e1) if ignoreDirection and not self.hasWalkingArea else []):
 762                if e2 not in seen:
 763                    newCost = cost + e2.getLength() / speedFunc(e2)
 764                    #  print(cost, newCost, e2.getID(), speedFunc(e2))
 765                    if e2 == e1.getBidi():
 766                        newCost += reversalPenalty
 767                    if self.hasInternal and conn is not None:
 768                        viaPath, minInternalCost = self.getInternalPath(conn, fastest=fastest)
 769                        if viaPath is not None:
 770                            newCost += minInternalCost
 771                    if e2 not in dist or newCost < dist[e2][0]:
 772                        dist[e2] = (newCost, e1)
 773                        heapq.heappush(q, (newCost, e2, e1))
 774        return None, 1e400
 775
 776    def getShortestPath(self, fromEdge, toEdge, maxCost=1e400, vClass=None, reversalPenalty=0,
 777                        includeFromToCost=True, withInternal=False, ignoreDirection=False,
 778                        fromPos=None, toPos=None, preferences={}):
 779        """
 780        Finds the shortest path from fromEdge to toEdge respecting vClass, using Dijkstra's algorithm.
 781        It returns a pair of a tuple of edges and the cost. If no path is found the first element is None.
 782        The cost for the returned path is equal to the sum of all edge lengths in the path,
 783        including the internal connectors, if they are present in the network.
 784        The path itself does not include internal edges except for the case
 785        when the start or end edge are internal edges.
 786        The search may be limited using the given threshold.
 787        The preferences declare a mapping from the 'routingType' of each edge to divisor
 788        that is applied to the lenght of that edge
 789        (i.e. a preference of 2 reduces reduces effective length by a factor of 0.5).
 790        """
 791
 792        return self.getOptimalPath(fromEdge, toEdge, False, maxCost, vClass, reversalPenalty,
 793                                   includeFromToCost, withInternal, ignoreDirection, fromPos, toPos,
 794                                   preferences)
 795
 796    def getFastestPath(self, fromEdge, toEdge, maxCost=1e400, vClass=None, reversalPenalty=0,
 797                       includeFromToCost=True, withInternal=False, ignoreDirection=False,
 798                       fromPos=None, toPos=None, preferences={}):
 799        """
 800        Finds the fastest path from fromEdge to toEdge respecting vClass, using Dijkstra's algorithm.
 801        It returns a pair of a tuple of edges and the cost. If no path is found the first element is None.
 802        The cost for the returned path is equal to the sum of all edge costs in the path,
 803        including the internal connectors, if they are present in the network.
 804        The path itself does not include internal edges except for the case
 805        when the start or end edge are internal edges.
 806        The search may be limited using the given threshold.
 807        The preferences declare a mapping from the 'routingType' of each edge to divisor
 808        that is applied to the computed traveltime of that edge
 809        (i.e. a preference of 2 reduces effective traveltime by a factor of 0.5).
 810        """
 811
 812        return self.getOptimalPath(fromEdge, toEdge, True, maxCost, vClass, reversalPenalty,
 813                                   includeFromToCost, withInternal, ignoreDirection, fromPos, toPos,
 814                                   preferences)
 815
 816    def getReachable(self, source, vclass=None, useIncoming=False, cache=None):
 817        if vclass is not None and not source.allows(vclass):
 818            raise RuntimeError("'{}' does not allow {}".format(source.getID(), vclass))
 819        fringe = [source]
 820        found = set()
 821        found.add(source)
 822        while len(fringe) > 0:
 823            new_fringe = []
 824            for e in fringe:
 825                if vclass == "pedestrian":
 826                    cands = chain(chain(*e.getIncoming().values()), chain(*e.getOutgoing().values()))
 827                else:
 828                    cands = chain(*(e.getIncoming().values() if useIncoming else e.getOutgoing().values()))
 829                # print("\n".join(map(str, list(cands))))
 830                for conn in cands:
 831                    if vclass is None or (
 832                            conn.getFromLane().allows(vclass)
 833                            and conn.getToLane().allows(vclass)):
 834                        for reachable in [conn.getTo(), conn.getFrom()]:
 835                            if reachable not in found:
 836                                # print("added %s via %s" % (reachable, conn))
 837                                if cache and reachable in cache:
 838                                    found.update(cache[reachable])
 839                                else:
 840                                    found.add(reachable)
 841                                    new_fringe.append(reachable)
 842            fringe = new_fringe
 843        if cache is not None:
 844            cache[source] = tuple(found)
 845        return found
 846
 847
 848class NetReader(handler.ContentHandler):
 849
 850    """Reads a network, storing the edge geometries, lane numbers and max. speeds"""
 851
 852    def __init__(self, **others):
 853        self._net = others.get('net', Net())
 854        self._currentEdge = None
 855        self._currentNode = None
 856        self._currentConnection = None
 857        self._currentLane = None
 858        self._crossingID2edgeIDs = {}
 859        self._withPhases = others.get('withPrograms', False)
 860        self._latestProgram = others.get('withLatestPrograms', False)
 861        if self._latestProgram:
 862            self._withPhases = True
 863        self._withConnections = others.get('withConnections', True)
 864        self._withFoes = others.get('withFoes', True)
 865        self._withPedestrianConnections = others.get('withPedestrianConnections', False)
 866        self._withMacroConnectors = others.get('withMacroConnectors', False)
 867        self._withInternal = others.get('withInternal', self._withPedestrianConnections)
 868        if self._withPedestrianConnections and not self._withInternal:
 869            sys.stderr.write("Warning: Option withPedestrianConnections requires withInternal\n")
 870            self._withInternal = True
 871        self._bidiEdgeIDs = {}
 872
 873    def startElement(self, name, attrs):
 874        if name == 'net':
 875            parts = attrs["version"].split('.', 1)
 876            self._net._version = (int(parts[0]), float(parts[1]))
 877        elif name == 'location':
 878            self._net.setLocation(attrs["netOffset"], attrs["convBoundary"], attrs[
 879                                  "origBoundary"], attrs["projParameter"])
 880        elif name == 'type':
 881            self._net._edgeTypes[attrs['id']] = EdgeType(attrs['id'], attrs.get('allow'), attrs.get('disallow'))
 882        elif name == 'edge':
 883            function = attrs.get('function', '')
 884            if (function == ''
 885                    or (self._withInternal and function in ['internal', 'crossing', 'walkingarea'])
 886                    or (self._withMacroConnectors and function == 'connector')):
 887                prio = -1
 888                if 'priority' in attrs:
 889                    prio = int(attrs['priority'])
 890
 891                # get the  ids
 892                edgeID = attrs['id']
 893                fromNodeID = attrs.get('from', None)
 894                toNodeID = attrs.get('to', None)
 895
 896                # for internal junctions use the junction's id for from and to node
 897                if function == 'internal' or function == 'crossing' or function == 'walkingarea':
 898                    fromNodeID = toNodeID = edgeID[1:edgeID.rfind('_')]
 899
 900                # remember edges crossed by pedestrians to link them later to the crossing objects
 901                if function == 'crossing':
 902                    self._crossingID2edgeIDs[edgeID] = attrs.get('crossingEdges').split(' ')
 903
 904                self._currentEdge = self._net.addEdge(edgeID, fromNodeID, toNodeID, prio, function,
 905                                                      attrs.get('name', ''), attrs.get('type', ''),
 906                                                      attrs.get('routingType', ''))
 907
 908                self._currentEdge.setRawShape(convertShape(attrs.get('shape', '')))
 909
 910                bidi = attrs.get('bidi', '')
 911                if bidi:
 912                    self._bidiEdgeIDs[edgeID] = bidi
 913            else:
 914                if function in ['crossing', 'walkingarea']:
 915                    self._net._crossings_and_walkingAreas.add(attrs['id'])
 916                elif function == 'connector':
 917                    self._net._macroConnectors.add(attrs['id'])
 918                self._currentEdge = None
 919        elif name == 'lane' and self._currentEdge is not None:
 920            self._currentLane = self._net.addLane(
 921                self._currentEdge,
 922                float(attrs['speed']),
 923                float(attrs['length']),
 924                float(attrs.get('width', 3.2)),
 925                attrs.get('allow'),
 926                attrs.get('disallow'),
 927                attrs.get('acceleration') == "1")
 928            self._currentLane.setShape(convertShape(attrs.get('shape', '')))
 929        elif name == 'neigh' and self._currentLane is not None:
 930            self._currentLane.setNeigh(attrs['lane'])
 931        elif name == 'junction':
 932            if attrs['id'][0] != ':':
 933                intLanes = None
 934                if self._withInternal:
 935                    intLanes = attrs["intLanes"].split(" ")
 936                self._currentNode = self._net.addNode(attrs['id'], attrs['type'],
 937                                                      tuple(
 938                                                          map(float, [attrs['x'], attrs['y'],
 939                                                                      attrs['z'] if 'z' in attrs else '0'])),
 940                                                      attrs['incLanes'].split(" "), intLanes)
 941                self._currentNode.setShape(
 942                    convertShape(attrs.get('shape', '')))
 943                if 'fringe' in attrs:
 944                    self._currentNode._fringe = attrs['fringe']
 945
 946        elif name == 'succ' and self._withConnections:  # deprecated
 947            if attrs['edge'][0] != ':':
 948                self._currentEdge = self._net.getEdge(attrs['edge'])
 949                self._currentLane = attrs['lane']
 950                self._currentLane = int(
 951                    self._currentLane[self._currentLane.rfind('_') + 1:])
 952            else:
 953                self._currentEdge = None
 954        elif name == 'succlane' and self._withConnections:  # deprecated
 955            lid = attrs['lane']
 956            if lid[0] != ':' and lid != "SUMO_NO_DESTINATION" and self._currentEdge:
 957                connected = self._net.getEdge(lid[:lid.rfind('_')])
 958                tolane = int(lid[lid.rfind('_') + 1:])
 959                if 'tl' in attrs and attrs['tl'] != "":
 960                    tl = attrs['tl']
 961                    tllink = int(attrs['linkIdx'])
 962                    tlid = attrs['tl']
 963                    toEdge = self._net.getEdge(lid[:lid.rfind('_')])
 964                    tolane2 = toEdge._lanes[tolane]
 965                    tls = self._net.addTLS(
 966                        tlid, self._currentEdge._lanes[self._currentLane], tolane2, tllink)
 967                    self._currentEdge.setTLS(tls)
 968                else:
 969                    tl = ""
 970                    tllink = -1
 971                toEdge = self._net.getEdge(lid[:lid.rfind('_')])
 972                tolane = toEdge._lanes[tolane]
 973                viaLaneID = attrs['via']
 974                self._net.addConnection(self._currentEdge, connected, self._currentEdge._lanes[
 975                                        self._currentLane], tolane,
 976                                        attrs['dir'], tl, tllink, -1,
 977                                        attrs.get('allow'), attrs.get('disallow'), attrs['state'], viaLaneID)
 978        elif name == 'connection' and self._withConnections and (attrs['from'][0] != ":" or self._withInternal):
 979            fromEdgeID = attrs['from']
 980            toEdgeID = attrs['to']
 981            if ((self._withPedestrianConnections or not (fromEdgeID in self._net._crossings_and_walkingAreas or
 982                                                         toEdgeID in self._net._crossings_and_walkingAreas))
 983                and (self._withMacroConnectors or not (fromEdgeID in self._net._macroConnectors or toEdgeID in
 984                                                       self._net._macroConnectors))):
 985                fromEdge = self._net.getEdge(fromEdgeID)
 986                toEdge = self._net.getEdge(toEdgeID)
 987                fromLane = fromEdge.getLane(int(attrs['fromLane']))
 988                toLane = toEdge.getLane(int(attrs['toLane']))
 989                if 'tl' in attrs and attrs['tl'] != "":
 990                    tl = attrs['tl']
 991                    tllink = int(attrs['linkIndex'])
 992                    tllink2 = int(attrs.get('linkIndex2', -1))
 993                    tls = self._net.addTLS(tl, fromLane, toLane, tllink)
 994                    fromEdge.setTLS(tls)
 995                else:
 996                    tl = ""
 997                    tllink = -1
 998                    tllink2 = -1
 999                try:
1000                    viaLaneID = attrs['via']
1001                except KeyError:
1002                    viaLaneID = ''
1003
1004                self._currentConnection = self._net.addConnection(
1005                    fromEdge, toEdge, fromLane, toLane, attrs['dir'], tl,
1006                    tllink, tllink2, attrs.get('allow'), attrs.get('disallow'), attrs['state'], viaLaneID)
1007
1008        # 'row-logic' is deprecated!!!
1009        elif self._withFoes and name == 'ROWLogic':
1010            self._currentNode = attrs['id']
1011        elif name == 'logicitem' and self._withFoes:  # deprecated
1012            self._net.setFoes(
1013                self._currentNode, int(attrs['request']), attrs["foes"], attrs["response"])
1014        elif name == 'request' and self._withFoes:
1015            self._currentNode.setFoes(
1016                int(attrs['index']), attrs["foes"], attrs["response"])
1017        # tl-logic is deprecated!!! NOTE: nevertheless, this is still used by
1018        # netconvert... (Leo)
1019        elif self._withPhases and name == 'tlLogic':
1020            self._currentProgram = self._net.addTLSProgram(
1021                attrs['id'], attrs['programID'],
1022                intIfPossible(float(attrs['offset'])), attrs['type'], self._latestProgram)
1023        elif self._withPhases and name == 'phase':
1024            self._currentProgram.addPhase(
1025                attrs['state'],
1026                intIfPossible(float(attrs['duration'])),
1027                intIfPossible(float(attrs['minDur'])) if 'minDur' in attrs else -1,
1028                intIfPossible(float(attrs['maxDur'])) if 'maxDur' in attrs else -1,
1029                list(map(int, attrs['next'].split())) if 'next' in attrs else [],
1030                attrs['name'] if 'name' in attrs else ""
1031            )
1032        elif name == 'roundabout':
1033            self._net.addRoundabout(
1034                attrs['nodes'].split(), attrs['edges'].split())
1035        elif name == 'param':
1036            if self._currentLane is not None:
1037                self._currentLane.setParam(attrs['key'], attrs['value'])
1038            elif self._currentEdge is not None:
1039                self._currentEdge.setParam(attrs['key'], attrs['value'])
1040            elif self._currentNode is not None:
1041                self._currentNode.setParam(attrs['key'], attrs['value'])
1042            elif self._currentConnection is not None:
1043                self._currentConnection.setParam(attrs['key'], attrs['value'])
1044            elif self._withPhases and self._currentProgram is not None:
1045                self._currentProgram.setParam(attrs['key'], attrs['value'])
1046
1047    def endElement(self, name):
1048        if name == 'lane':
1049            self._currentLane = None
1050        elif name == 'edge':
1051            self._currentEdge = None
1052        elif name == 'junction':
1053            self._currentNode = None
1054        elif name == 'connection':
1055            self._currentConnection = None
1056        # 'row-logic' is deprecated!!!
1057        elif name == 'ROWLogic' or name == 'row-logic':
1058            self._haveROWLogic = False
1059        # tl-logic is deprecated!!!
1060        elif self._withPhases and (name == 'tlLogic' or name == 'tl-logic'):
1061            self._currentProgram = None
1062        elif name == 'net':
1063            for edgeID, bidiID in self._bidiEdgeIDs.items():
1064                self._net.getEdge(edgeID)._bidi = self._net.getEdge(bidiID)
1065
1066    def endDocument(self):
1067        # set crossed edges of pedestrian crossings
1068        for crossingID, crossedEdgeIDs in self._crossingID2edgeIDs.items():
1069            pedCrossing = self._net.getEdge(crossingID)
1070            for crossedEdgeID in crossedEdgeIDs:
1071                pedCrossing._addCrossingEdge(self._net.getEdge(crossedEdgeID))
1072
1073    def getNet(self):
1074        return self._net
1075
1076
1077def convertShape(shapeString):
1078    """ Convert xml shape string into float tuples.
1079
1080    This method converts the 2d or 3d shape string from SUMO's xml file
1081    into a list containing 3d float-tuples. Non existent z coordinates default
1082    to zero. If shapeString is empty, an empty list will be returned.
1083    """
1084
1085    cshape = []
1086    for pointString in shapeString.split():
1087        p = [float(e) for e in pointString.split(",")]
1088        if len(p) == 2:
1089            cshape.append((p[0], p[1], 0.))
1090        elif len(p) == 3:
1091            cshape.append(tuple(p))
1092        else:
1093            raise ValueError(
1094                'Invalid shape point "%s", should be either 2d or 3d' % pointString)
1095    return cshape
1096
1097
1098def lane2edge(laneID):
1099    return laneID[:laneID.rfind("_")]
1100
1101
1102def lane2index(laneID):
1103    return int(laneID[laneID.rfind("_") + 1:])
1104
1105
1106def readNet(filename, **others):
1107    """ load a .net.xml file
1108    The following named options are supported:
1109
1110        'net' : initialize data structures with an existing net object (default Net())
1111        'withPrograms' : import all traffic light programs (default False)
1112        'withLatestPrograms' : import only the last program for each traffic light.
1113                               This is the program that would be active in sumo by default.
1114                               (default False)
1115        'withConnections' : import all connections (default True)
1116        'withFoes' : import right-of-way information (default True)
1117        'withInternal' : import internal edges and lanes (default False)
1118        'withPedestrianConnections' : import connections between sidewalks, crossings (default False)
1119        'lxml' : set to False to use the xml.sax parser instead of the lxml parser
1120        'maxcache' : set maximum cache size (default 1000) or 0 to disable optimal route caching
1121    """
1122    netreader = NetReader(**others)
1123    try:
1124        source = gzip.open(filename)
1125        source.read(10)
1126        source.seek(0)
1127    except IOError:
1128        source = filename
1129    if HAVE_LXML and others.get("lxml", True):
1130        if isinstance(source, pathlib.Path):
1131            source = str(source)
1132        for event, v in lxml.etree.iterparse(source, events=("start", "end")):
1133            if event == "start":
1134                netreader.startElement(v.tag, v.attrib)
1135            elif event == "end":
1136                netreader.endElement(v.tag)
1137            v.clear()  # reduce memory footprint
1138    else:
1139        parse(source, netreader)
1140    net = netreader.getNet()
1141    maxcache = others.get('maxcache', 1000)
1142    if HAVE_LRU_CACHE and maxcache is not None and maxcache > 0:
1143        net.initRoutingCache(maxcache)
1144    return net