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, openz, PRACTICAL_INFINITY
  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 = {True: None, False: None}  # different rTrees depending on includeJunctions
 231        self._rtreeLanes = {True: None, False: None}  # different rTrees depending on includeJunctions
 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        self._edgeSuccessorCache = None
 243        self._edgeCostCache = None
 244
 245    def initRoutingCache(self, maxsize=1000):
 246        self._routingCache = lru_cache(maxsize=maxsize)(lambda fromEdge, fastest, vClass, ignoreDirection, reversalPenalty, preferences: {})  # noqa
 247
 248    def getVersion(self):
 249        return self._version
 250
 251    def getEdgeType(self, typeID):
 252        return self._edgeTypes[typeID]
 253
 254    def setLocation(self, netOffset, convBoundary, origBoundary, projParameter):
 255        self._location["netOffset"] = netOffset
 256        self._location["convBoundary"] = convBoundary
 257        self._location["origBoundary"] = origBoundary
 258        self._location["projParameter"] = projParameter
 259
 260    def loadSelection(self, selectionFile):
 261        self.resetSelection()
 262        with io.open(selectionFile, "r", encoding="utf-8") as f:
 263            for line in f:
 264                line = line.strip()
 265                if line.startswith("edge:"):
 266                    edgeID = line[5:]
 267                    if edgeID in self._id2edge:
 268                        self.getEdge(edgeID).select()
 269                elif line.startswith("junction:"):
 270                    nodeID = line[9:]
 271                    if nodeID in self._id2node:
 272                        self.getNode(nodeID).select()
 273
 274    def resetSelection(self):
 275        for n in self._nodes:
 276            n.select(False)
 277        for e in self._edges:
 278            e.select(False)
 279
 280    def addNode(self, id, type=None, coord=None, incLanes=None, intLanes=None):
 281        if id is None:
 282            return None
 283        if id not in self._id2node:
 284            n = node.Node(id, type, coord, incLanes, intLanes)
 285            self._nodes.append(n)
 286            self._id2node[id] = n
 287        self.setAdditionalNodeInfo(
 288            self._id2node[id], type, coord, incLanes, intLanes)
 289        return self._id2node[id]
 290
 291    def setAdditionalNodeInfo(self, node, type, coord, incLanes, intLanes=None):
 292        if coord is not None and node._coord is None:
 293            node._coord = coord
 294            self._ranges[0][0] = min(self._ranges[0][0], coord[0])
 295            self._ranges[0][1] = max(self._ranges[0][1], coord[0])
 296            self._ranges[1][0] = min(self._ranges[1][0], coord[1])
 297            self._ranges[1][1] = max(self._ranges[1][1], coord[1])
 298        if incLanes is not None and node._incLanes is None:
 299            node._incLanes = incLanes
 300        if intLanes is not None and node._intLanes is None:
 301            node._intLanes = intLanes
 302        if type is not None and node._type is None:
 303            node._type = type
 304
 305    def addEdge(self, id, fromID, toID, prio, function, name, edgeType='', routingType=''):
 306        if id not in self._id2edge:
 307            fromN = self.addNode(fromID)
 308            toN = self.addNode(toID)
 309            e = edge.Edge(id, fromN, toN, prio, function, name, edgeType, routingType)
 310            self._edges.append(e)
 311            self._id2edge[id] = e
 312            if function:
 313                self.hasInternal = True
 314                if function == "walkingarea":
 315                    self.hasWalkingArea = True
 316        return self._id2edge[id]
 317
 318    def addLane(self, edge, speed, length, width, allow=None, disallow=None, acceleration=False):
 319        return lane.Lane(edge, speed, length, width, allow, disallow, acceleration)
 320
 321    def addRoundabout(self, nodes, edges=None):
 322        r = roundabout.Roundabout(nodes, edges)
 323        self._roundabouts.append(r)
 324        return r
 325
 326    def addConnection(self, fromEdge, toEdge, fromlane, tolane, direction,
 327                      tls, tllink, tllink2, allow, disallow, state, viaLaneID=None):
 328        conn = connection.Connection(
 329            fromEdge, toEdge, fromlane, tolane, direction,
 330            tls, tllink, tllink2, allow, disallow, state, viaLaneID)
 331        fromEdge.addOutgoing(conn)
 332        fromlane.addOutgoing(conn)
 333        toEdge._addIncoming(conn)
 334        if viaLaneID:
 335            try:
 336                # internal lanes are only available when building with option withInternal=True
 337                viaLane = self.getLane(viaLaneID)
 338                viaEdge = viaLane.getEdge()
 339                viaEdge._addIncoming(connection.Connection(
 340                    fromEdge, viaEdge, fromlane, viaLane, direction, tls,
 341                    tllink, tllink2, allow, disallow, state, ''))
 342            except Exception:
 343                pass
 344        return conn
 345
 346    def getEdges(self, withInternal=True):
 347        if not withInternal:
 348            return [e for e in self._edges if e.getFunction() == '']
 349        else:
 350            return self._edges
 351
 352    def getRoundabouts(self):
 353        return self._roundabouts
 354
 355    def hasEdge(self, id):
 356        return id in self._id2edge
 357
 358    def getEdge(self, id):
 359        return self._id2edge[id]
 360
 361    def getLane(self, laneID):
 362        edge_id, lane_index = laneID.rsplit("_", 1)
 363        return self.getEdge(edge_id).getLane(int(lane_index))
 364
 365    def _initRTree(self, shapeList, includeJunctions=True):
 366        import rtree  # noqa
 367        result = rtree.index.Index()
 368        result.interleaved = True
 369        for ri, shape in enumerate(shapeList):
 370            result.add(ri, shape.getBoundingBox(includeJunctions))
 371        return result
 372
 373    # Please be aware that the resulting list of edges is NOT sorted
 374    def getNeighboringEdges(self, x, y, r=0.1, includeJunctions=True, allowFallback=True):
 375        edges = []
 376        rtree = self._rtreeEdges[includeJunctions]
 377        try:
 378            if rtree is None:
 379                rtree = self._initRTree(self._edges, includeJunctions)
 380                self._rtreeEdges[includeJunctions] = rtree
 381            for i in rtree.intersection((x - r, y - r, x + r, y + r)):
 382                e = self._edges[i]
 383                d = sumolib.geomhelper.distancePointToPolygon(
 384                    (x, y), e.getShape(includeJunctions))
 385                if d < r:
 386                    edges.append((e, d))
 387        except ImportError:
 388            if not allowFallback:
 389                raise
 390            warnings.warn("Module 'rtree' not available. Using brute-force fallback.")
 391            for the_edge in self._edges:
 392                d = sumolib.geomhelper.distancePointToPolygon((x, y), the_edge.getShape(includeJunctions))
 393                if d < r:
 394                    edges.append((the_edge, d))
 395        return edges
 396
 397    def getNeighboringLanes(self, x, y, r=0.1, includeJunctions=True, allowFallback=True):
 398        lanes = []
 399        rtree = self._rtreeLanes[includeJunctions]
 400        try:
 401            if rtree is None:
 402                for the_edge in self._edges:
 403                    self._allLanes += the_edge.getLanes()
 404                rtree = self._initRTree(self._allLanes, includeJunctions)
 405                self._rtreeLanes[includeJunctions] = rtree
 406            for i in rtree.intersection((x - r, y - r, x + r, y + r)):
 407                the_lane = self._allLanes[i]
 408                d = sumolib.geomhelper.distancePointToPolygon((x, y), the_lane.getShape(includeJunctions))
 409                if d < r:
 410                    lanes.append((the_lane, d))
 411        except ImportError:
 412            if not allowFallback:
 413                raise
 414            warnings.warn("Module 'rtree' not available. Using brute-force fallback.")
 415            for the_edge in self._edges:
 416                for the_lane in the_edge.getLanes():
 417                    d = sumolib.geomhelper.distancePointToPolygon((x, y), the_lane.getShape(includeJunctions))
 418                    if d < r:
 419                        lanes.append((the_lane, d))
 420        return lanes
 421
 422    def hasNode(self, id):
 423        return id in self._id2node
 424
 425    def getNode(self, id):
 426        return self._id2node[id]
 427
 428    def getNodes(self):
 429        return self._nodes
 430
 431    def getTLS(self, tlid):
 432        return self._id2tls[tlid]
 433
 434    def getTLSSecure(self, tlid):
 435        if tlid in self._id2tls:
 436            tls = self._id2tls[tlid]
 437        else:
 438            tls = TLS(tlid)
 439            self._id2tls[tlid] = tls
 440            self._tlss.append(tls)
 441        return tls
 442
 443    def getTrafficLights(self):
 444        return self._tlss
 445
 446    def addTLS(self, tlid, inLane, outLane, linkNo):
 447        tls = self.getTLSSecure(tlid)
 448        tls.addConnection(inLane, outLane, linkNo)
 449        return tls
 450
 451    def addTLSProgram(self, tlid, programID, offset, type, removeOthers):
 452        tls = self.getTLSSecure(tlid)
 453        program = TLSProgram(programID, offset, type)
 454        if removeOthers:
 455            tls.removePrograms()
 456        tls.addProgram(program)
 457        return program
 458
 459    def setFoes(self, junctionID, index, foes, prohibits):
 460        self._id2node[junctionID].setFoes(index, foes, prohibits)
 461
 462    def forbids(self, possProhibitor, possProhibited):
 463        return possProhibitor.getFrom().getToNode().forbids(possProhibitor, possProhibited)
 464
 465    def getUpstreamEdges(self, edge, distance, stopOnTLS, stopOnTurnaround):
 466        """return a list of lists of the form
 467           [[firstEdge, pos, [edge_0, edge_1, ..., edge_k], aborted], ...]
 468           where
 469             firstEdge: is the upstream edge furthest away from the intersection,
 470             [edge_0, ..., edge_k]: is the list of edges from the intersection upstream to firstEdge
 471             pos: is the position on firstEdge with distance to the end of the input edge
 472             aborted: a flag indicating whether the downstream
 473                 search stopped at a TLS or a node without incoming edges before reaching the distance threshold
 474        """
 475        ret = []
 476        seen = set()
 477        toProc = []
 478        toProc.append([edge, 0, []])
 479        while not len(toProc) == 0:
 480            ie = toProc.pop()
 481            if ie[0] in seen:
 482                continue
 483            seen.add(ie[0])
 484            if ie[1] + ie[0].getLength() >= distance:
 485                ret.append(
 486                    [ie[0], ie[0].getLength() + ie[1] - distance, ie[2], False])
 487                continue
 488            if len(ie[0]._incoming) == 0:
 489                ret.append([ie[0], ie[0].getLength() + ie[1], ie[2], True])
 490                continue
 491            mn = []
 492            stop = False
 493            for ci in ie[0]._incoming:
 494                if ci not in seen:
 495                    prev = copy(ie[2])
 496                    if stopOnTLS and ci._tls and ci != edge and not stop:
 497                        ret.append([ie[0], ie[1], prev, True])
 498                        stop = True
 499                    elif (stopOnTurnaround and ie[0]._incoming[ci][0].getDirection() == Connection.LINKDIR_TURN and
 500                          not stop):
 501                        ret.append([ie[0], ie[1], prev, True])
 502                        stop = True
 503                    else:
 504                        prev.append(ie[0])
 505                        mn.append([ci, ie[0].getLength() + ie[1], prev])
 506            if not stop:
 507                toProc.extend(mn)
 508        return ret
 509
 510    def getEdgesByOrigID(self, origID):
 511        if self._origIdx is None:
 512            self._origIdx = defaultdict(set)
 513            for the_edge in self._edges:
 514                for the_lane in the_edge.getLanes():
 515                    for oID in the_lane.getParam("origId", "").split():
 516                        self._origIdx[oID].add(the_edge)
 517        return self._origIdx[origID]
 518
 519    def getGeometries(self, useLanes, includeJunctions=False):
 520        for e in self._edges:
 521            if useLanes:
 522                for the_lane in e.getLanes():
 523                    yield the_lane.getID(), the_lane.getShape(), the_lane.getWidth()
 524            else:
 525                yield e.getID(), e.getShape(includeJunctions), sum([the_lane.getWidth() for the_lane in e.getLanes()])
 526
 527    def getBBoxXY(self):
 528        """
 529        Get the bounding box (bottom left and top right coordinates) for a net;
 530        Coordinates are in X and Y (not Lat and Lon)
 531
 532        :return [(bottom_left_X, bottom_left_Y), (top_right_X, top_right_Y)]
 533        """
 534        return [(self._ranges[0][0], self._ranges[1][0]),
 535                (self._ranges[0][1], self._ranges[1][1])]
 536
 537    # the diagonal of the bounding box of all nodes
 538    def getBBoxDiameter(self):
 539        return math.sqrt(
 540            (self._ranges[0][0] - self._ranges[0][1]) ** 2 +
 541            (self._ranges[1][0] - self._ranges[1][1]) ** 2)
 542
 543    def hasGeoProj(self):
 544        projString = self._location["projParameter"]
 545        return projString != "!"
 546
 547    def getGeoProj(self):
 548        if not self.hasGeoProj() or not HAVE_PYPROJ:
 549            raise RuntimeError("Network does not provide geo-projection or pyproj not installed.")
 550        if self._proj is None:
 551            try:
 552                self._proj = pyproj.Proj(projparams=self._location["projParameter"])
 553            except RuntimeError:
 554                if hasattr(pyproj.datadir, 'set_data_dir'):
 555                    pyproj.datadir.set_data_dir('/usr/share/proj')
 556                    self._proj = pyproj.Proj(projparams=self._location["projParameter"])
 557                raise
 558        return self._proj
 559
 560    def getLocationOffset(self):
 561        """ offset to be added after converting from geo-coordinates to UTM"""
 562        return list(map(float, self._location["netOffset"].split(",")))
 563
 564    def getBoundary(self):
 565        """ return xmin,ymin,xmax,ymax network coordinates"""
 566        return list(map(float, self._location["convBoundary"].split(",")))
 567
 568    def convertLonLat2XY(self, lon, lat, rawUTM=False):
 569        x, y = self.getGeoProj()(lon, lat)
 570        if rawUTM:
 571            return x, y
 572        else:
 573            x_off, y_off = self.getLocationOffset()
 574            return x + x_off, y + y_off
 575
 576    def convertXY2LonLat(self, x, y, rawUTM=False):
 577        if not rawUTM:
 578            x_off, y_off = self.getLocationOffset()
 579            x -= x_off
 580            y -= y_off
 581        return self.getGeoProj()(x, y, inverse=True)
 582
 583    def move(self, dx, dy, dz=0):
 584        for n in self._nodes:
 585            n._coord = (n._coord[0] + dx, n._coord[1] + dy, n._coord[2] + dz)
 586        for e in self._edges:
 587            for _lane in e.getLanes():
 588                _lane.setShape([(p[0] + dx, p[1] + dy, p[2] + dz) for p in _lane.getShape3D()])
 589            e.rebuildShape()
 590
 591    def getInternalPath(self, conn, fastest=False):
 592        minInternalCost = PRACTICAL_INFINITY
 593        minPath = None
 594        for c in conn:
 595            if c.getViaLaneID() != "":
 596                viaCost = 0
 597                viaID = c.getViaLaneID()
 598                viaPath = []
 599                while viaID != "":
 600                    viaLane = self.getLane(viaID)
 601                    viaCost += viaLane.getLength() if not fastest else viaLane.getLength() / viaLane.getSpeed()
 602                    viaID = viaLane.getOutgoing()[0].getViaLaneID()
 603                    viaPath.append(viaLane.getEdge())
 604                if viaCost < minInternalCost:
 605                    minInternalCost = viaCost
 606                    minPath = viaPath
 607        return minPath, minInternalCost
 608
 609    def getOptimalPath(self, fromEdge, toEdge, fastest=False, maxCost=PRACTICAL_INFINITY, vClass=None,
 610                       reversalPenalty=0, includeFromToCost=True, withInternal=False, ignoreDirection=False,
 611                       fromPos=None, toPos=None, preferences={}):
 612        """
 613        Finds the optimal (shortest or fastest) path for vClass from fromEdge to toEdge
 614        by using using Dijkstra's algorithm.
 615        It returns a pair of a tuple of edges and the cost.
 616        If no path is found the first element is None.
 617        The cost for the returned path is equal to the sum of all edge costs in the path,
 618        including the internal connectors, if they are present in the network.
 619        The path itself does not include internal edges except for the case
 620        when the start or end edge are internal edges.
 621        The search may be limited using the given threshold.
 622        The preferences declare a mapping from the 'routingType' of each edge to divisor
 623        that is applied to the computed cost of that edge (i.e. a preference of 2 reduces cost by a factor of 0.5).
 624        """
 625
 626        if preferences:
 627            if fastest:
 628                def speedFunc(edge):
 629                    return preferences.get(edge.getRoutingType(), 1.0) * edge.getSpeed()
 630            else:
 631                def speedFunc(edge):
 632                    return preferences.get(edge.getRoutingType(), 1.0)
 633        elif fastest:
 634            def speedFunc(edge):
 635                return edge.getSpeed()
 636        else:
 637            def speedFunc(edge):
 638                return 1.0
 639
 640        def remainder(edge, pos):
 641            if pos < 0:
 642                return min(-pos, edge.getLength())
 643            return max(0., edge.getLength() - pos)
 644
 645        def getToNormalIncoming(edge):
 646            if edge.getFunction() == '':
 647                return [(e, None) for e in edge.getToNode().getIncoming() if e.getFunction() == '']
 648            else:
 649                return []
 650
 651        if self._edgeSuccessorCache != (vClass, ignoreDirection):
 652            self._edgeSuccessorCache = (vClass, ignoreDirection)
 653            for e1 in self.getEdges():
 654                e1._succCacche = tuple(chain(e1.getAllowedOutgoing(vClass).items(),
 655                                       e1.getIncoming().items() if ignoreDirection else [],
 656                                       getToNormalIncoming(e1) if ignoreDirection and not self.hasWalkingArea else []))
 657
 658        if self._edgeCostCache != (fastest, preferences):
 659            self._edgeCostCache = (fastest, preferences)
 660            for e1 in self.getEdges():
 661                e1._costCache = e1.getLength() / speedFunc(e1)
 662
 663        if self.hasInternal:
 664            appendix = []
 665            appendixCost = 0.
 666            while toEdge.getFunction() == "internal":
 667                appendix = [toEdge] + appendix
 668                appendixCost += toEdge._costCache
 669                toEdge = list(toEdge.getIncoming().keys())[0]
 670
 671        def finalizeCost(cost, path):
 672            if includeFromToCost:
 673                # add costs for (part of) the first edge, still needs to be fixed for wrong direction travel
 674                remainFrom = fromEdge.getLength() if fromPos is None else remainder(fromEdge, fromPos)
 675                cost += remainFrom / speedFunc(fromEdge)
 676                # remove costs for (part of) the last edge, still needs to be fixed for wrong direction travel
 677                removeTo = 0. if toPos is None else remainder(toEdge, toPos)
 678            else:
 679                removeTo = toEdge.getLength() if len(path) > 1 else 0.
 680            cost -= removeTo / speedFunc(toEdge)
 681            return cost
 682
 683        def constructPath(dist):
 684            # destination was already reached in a previous query
 685            cost, pred = dist[toEdge]
 686            path = [toEdge]
 687            while pred is not None:
 688                if self.hasInternal and withInternal:
 689                    viaPath, minInternalCost = self.getInternalPath(pred.getAllowedOutgoing(vClass).get(path[-1], []),
 690                                                                    fastest=fastest)
 691                    if viaPath is not None:
 692                        path += reversed(viaPath)
 693                path.append(pred)
 694                _, pred = dist[pred]
 695
 696            path.reverse()
 697            cost = finalizeCost(cost, path)
 698            assert cost >= 0
 699            if self.hasInternal:
 700                if appendix:
 701                    return tuple(path + appendix), cost + appendixCost
 702                elif ignoreDirection and self.hasWalkingArea and not withInternal:
 703                    return [e for e in path if e.getFunction() == ''], cost
 704            return tuple(path), cost
 705
 706        needLoop = (fromEdge == toEdge
 707                    and fromPos is not None
 708                    and toPos is not None
 709                    and fromPos > toPos
 710                    and not ignoreDirection)
 711
 712        seen = set()
 713        dist = {}
 714        q = []
 715        if self._routingCache is not None:
 716            if needLoop:
 717                # use cached results from all follower edges:
 718                bestCost = maxCost
 719                bestPath = None
 720                for e2, conn in fromEdge.getAllowedOutgoing(vClass).items():
 721                    path, cost = self.getOptimalPath(e2, toEdge, fastest=fastest, maxCost=maxCost, vClass=vClass,
 722                                                     reversalPenalty=reversalPenalty,
 723                                                     includeFromToCost=includeFromToCost,
 724                                                     withInternal=withInternal, fromPos=0, toPos=toPos,
 725                                                     preferences=preferences)
 726                    if path is not None and cost < bestCost:
 727                        bestPath = path
 728                        bestCost = cost
 729                if bestPath is not None:
 730                    path = [fromEdge]
 731                    if self.hasInternal and withInternal:
 732                        viaPath, minInternalCost = self.getInternalPath(
 733                            fromEdge.getAllowedOutgoing(vClass).get(path[0], []), fastest=fastest)
 734                        if viaPath is not None:
 735                            path += viaPath
 736                            bestCost += minInternalCost
 737                    path += list(bestPath)
 738                    if includeFromToCost:
 739                        bestCost += remainder(fromEdge, fromPos) / speedFunc(fromEdge)
 740                    return tuple(path), bestCost
 741                else:
 742                    return None, PRACTICAL_INFINITY
 743
 744            dist = self._routingCache(fromEdge, fastest, vClass, ignoreDirection, reversalPenalty,
 745                                      tuple(preferences.items()))
 746            if toEdge in dist:
 747                return constructPath(dist)
 748            else:
 749                # initialize heap from previous query
 750                q = []
 751                frontier = set(dist.keys())
 752                for cost, prev in dist.values():
 753                    frontier.discard(prev)
 754                for e in frontier:
 755                    cost, prev = dist[e]
 756                    heapq.heappush(q, (cost, e, prev))
 757        elif needLoop:
 758            # start search on successors of fromEdge
 759            for e2, conn in fromEdge.getAllowedOutgoing(vClass).items():
 760                q.append((e2._costCache, e2, fromEdge))
 761
 762        if len(dist) == 0:
 763            dist[fromEdge] = (0., None)
 764            if not needLoop:
 765                q.append((0., fromEdge, None))
 766
 767        while q:
 768            cost, e1, prev = heapq.heappop(q)
 769            if e1 in seen:
 770                continue
 771            seen.add(e1)
 772            if e1 == toEdge:
 773                return constructPath(dist)
 774            if cost > maxCost:
 775                return None, cost
 776
 777            for e2, conn in e1._succCacche:
 778                if e2 not in seen:
 779                    newCost = cost + e2._costCache
 780                    #  print(cost, newCost, e2.getID(), speedFunc(e2))
 781                    if e2 == e1.getBidi():
 782                        newCost += reversalPenalty
 783                    if self.hasInternal and conn is not None:
 784                        viaPath, minInternalCost = self.getInternalPath(conn, fastest=fastest)
 785                        if viaPath is not None:
 786                            newCost += minInternalCost
 787                    if e2 not in dist or newCost < dist[e2][0]:
 788                        dist[e2] = (newCost, e1)
 789                        heapq.heappush(q, (newCost, e2, e1))
 790        return None, PRACTICAL_INFINITY
 791
 792    def getShortestPath(self, fromEdge, toEdge, maxCost=PRACTICAL_INFINITY, vClass=None, reversalPenalty=0,
 793                        includeFromToCost=True, withInternal=False, ignoreDirection=False,
 794                        fromPos=None, toPos=None, preferences={}):
 795        """
 796        Finds the shortest path from fromEdge to toEdge respecting vClass, using Dijkstra's algorithm.
 797        It returns a pair of a tuple of edges and the cost. If no path is found the first element is None.
 798        The cost for the returned path is equal to the sum of all edge lengths in the path,
 799        including the internal connectors, if they are present in the network.
 800        The path itself does not include internal edges except for the case
 801        when the start or end edge are internal edges.
 802        The search may be limited using the given threshold.
 803        The preferences declare a mapping from the 'routingType' of each edge to divisor
 804        that is applied to the lenght of that edge
 805        (i.e. a preference of 2 reduces reduces effective length by a factor of 0.5).
 806        """
 807
 808        return self.getOptimalPath(fromEdge, toEdge, False, maxCost, vClass, reversalPenalty,
 809                                   includeFromToCost, withInternal, ignoreDirection, fromPos, toPos,
 810                                   preferences)
 811
 812    def getFastestPath(self, fromEdge, toEdge, maxCost=PRACTICAL_INFINITY, vClass=None, reversalPenalty=0,
 813                       includeFromToCost=True, withInternal=False, ignoreDirection=False,
 814                       fromPos=None, toPos=None, preferences={}):
 815        """
 816        Finds the fastest path from fromEdge to toEdge respecting vClass, using Dijkstra's algorithm.
 817        It returns a pair of a tuple of edges and the cost. If no path is found the first element is None.
 818        The cost for the returned path is equal to the sum of all edge costs in the path,
 819        including the internal connectors, if they are present in the network.
 820        The path itself does not include internal edges except for the case
 821        when the start or end edge are internal edges.
 822        The search may be limited using the given threshold.
 823        The preferences declare a mapping from the 'routingType' of each edge to divisor
 824        that is applied to the computed traveltime of that edge
 825        (i.e. a preference of 2 reduces effective traveltime by a factor of 0.5).
 826        """
 827
 828        return self.getOptimalPath(fromEdge, toEdge, True, maxCost, vClass, reversalPenalty,
 829                                   includeFromToCost, withInternal, ignoreDirection, fromPos, toPos,
 830                                   preferences)
 831
 832    def getReachable(self, source, vclass=None, useIncoming=False, cache=None):
 833        if vclass is not None and not source.allows(vclass):
 834            raise RuntimeError("'{}' does not allow {}".format(source.getID(), vclass))
 835        fringe = [source]
 836        found = set()
 837        found.add(source)
 838        while len(fringe) > 0:
 839            new_fringe = []
 840            for e in fringe:
 841                if vclass == "pedestrian":
 842                    cands = chain(chain(*e.getIncoming().values()), chain(*e.getOutgoing().values()))
 843                else:
 844                    cands = chain(*(e.getIncoming().values() if useIncoming else e.getOutgoing().values()))
 845                # print("\n".join(map(str, list(cands))))
 846                for conn in cands:
 847                    if vclass is None or (
 848                            conn.getFromLane().allows(vclass)
 849                            and conn.getToLane().allows(vclass)):
 850                        for reachable in [conn.getTo(), conn.getFrom()]:
 851                            if reachable not in found:
 852                                # print("added %s via %s" % (reachable, conn))
 853                                if cache and reachable in cache:
 854                                    found.update(cache[reachable])
 855                                else:
 856                                    found.add(reachable)
 857                                    new_fringe.append(reachable)
 858            fringe = new_fringe
 859        if cache is not None:
 860            cache[source] = tuple(found)
 861        return found
 862
 863
 864class NetReader(handler.ContentHandler):
 865
 866    """Reads a network, storing the edge geometries, lane numbers and max. speeds"""
 867
 868    def __init__(self, **others):
 869        self._net = others.get('net', Net())
 870        self._currentEdge = None
 871        self._currentNode = None
 872        self._currentConnection = None
 873        self._currentLane = None
 874        self._crossingID2edgeIDs = {}
 875        self._withPhases = others.get('withPrograms', False)
 876        self._latestProgram = others.get('withLatestPrograms', False)
 877        if self._latestProgram:
 878            self._withPhases = True
 879        self._withConnections = others.get('withConnections', True)
 880        self._withFoes = others.get('withFoes', True)
 881        self._withPedestrianConnections = others.get('withPedestrianConnections', False)
 882        self._withMacroConnectors = others.get('withMacroConnectors', False)
 883        self._withInternal = others.get('withInternal', self._withPedestrianConnections)
 884        if self._withPedestrianConnections and not self._withInternal:
 885            sys.stderr.write("Warning: Option withPedestrianConnections requires withInternal\n")
 886            self._withInternal = True
 887        self._bidiEdgeIDs = {}
 888
 889    def startElement(self, name, attrs):
 890        if name == 'net':
 891            parts = attrs["version"].split('.', 1)
 892            self._net._version = (int(parts[0]), float(parts[1]))
 893        elif name == 'location':
 894            self._net.setLocation(attrs["netOffset"], attrs["convBoundary"], attrs[
 895                                  "origBoundary"], attrs["projParameter"])
 896        elif name == 'type':
 897            self._net._edgeTypes[attrs['id']] = EdgeType(attrs['id'], attrs.get('allow'), attrs.get('disallow'))
 898        elif name == 'edge':
 899            function = attrs.get('function', '')
 900            if (function == ''
 901                    or (self._withInternal and function in ['internal', 'crossing', 'walkingarea'])
 902                    or (self._withMacroConnectors and function == 'connector')):
 903                prio = -1
 904                if 'priority' in attrs:
 905                    prio = int(attrs['priority'])
 906
 907                # get the  ids
 908                edgeID = attrs['id']
 909                fromNodeID = attrs.get('from', None)
 910                toNodeID = attrs.get('to', None)
 911
 912                # for internal junctions use the junction's id for from and to node
 913                if function == 'internal' or function == 'crossing' or function == 'walkingarea':
 914                    fromNodeID = toNodeID = edgeID[1:edgeID.rfind('_')]
 915
 916                # remember edges crossed by pedestrians to link them later to the crossing objects
 917                if function == 'crossing':
 918                    self._crossingID2edgeIDs[edgeID] = attrs.get('crossingEdges').split(' ')
 919
 920                self._currentEdge = self._net.addEdge(edgeID, fromNodeID, toNodeID, prio, function,
 921                                                      attrs.get('name', ''), attrs.get('type', ''),
 922                                                      attrs.get('routingType', ''))
 923
 924                self._currentEdge.setRawShape(convertShape(attrs.get('shape', '')))
 925
 926                bidi = attrs.get('bidi', '')
 927                if bidi:
 928                    self._bidiEdgeIDs[edgeID] = bidi
 929            else:
 930                if function in ['crossing', 'walkingarea']:
 931                    self._net._crossings_and_walkingAreas.add(attrs['id'])
 932                elif function == 'connector':
 933                    self._net._macroConnectors.add(attrs['id'])
 934                self._currentEdge = None
 935        elif name == 'lane' and self._currentEdge is not None:
 936            self._currentLane = self._net.addLane(
 937                self._currentEdge,
 938                float(attrs['speed']),
 939                float(attrs['length']),
 940                float(attrs.get('width', 3.2)),
 941                attrs.get('allow'),
 942                attrs.get('disallow'),
 943                attrs.get('acceleration') == "1")
 944            self._currentLane.setShape(convertShape(attrs.get('shape', '')))
 945        elif name == 'neigh' and self._currentLane is not None:
 946            self._currentLane.setNeigh(attrs['lane'])
 947        elif name == 'junction':
 948            if attrs['id'][0] != ':':
 949                intLanes = None
 950                if self._withInternal:
 951                    intLanes = attrs["intLanes"].split(" ")
 952                self._currentNode = self._net.addNode(attrs['id'], attrs['type'],
 953                                                      tuple(
 954                                                          map(float, [attrs['x'], attrs['y'],
 955                                                                      attrs['z'] if 'z' in attrs else '0'])),
 956                                                      attrs['incLanes'].split(" "), intLanes)
 957                self._currentNode.setShape(
 958                    convertShape(attrs.get('shape', '')))
 959                if 'fringe' in attrs:
 960                    self._currentNode._fringe = attrs['fringe']
 961
 962        elif name == 'succ' and self._withConnections:  # deprecated
 963            if attrs['edge'][0] != ':':
 964                self._currentEdge = self._net.getEdge(attrs['edge'])
 965                self._currentLane = attrs['lane']
 966                self._currentLane = int(
 967                    self._currentLane[self._currentLane.rfind('_') + 1:])
 968            else:
 969                self._currentEdge = None
 970        elif name == 'succlane' and self._withConnections:  # deprecated
 971            lid = attrs['lane']
 972            if lid[0] != ':' and lid != "SUMO_NO_DESTINATION" and self._currentEdge:
 973                connected = self._net.getEdge(lid[:lid.rfind('_')])
 974                tolane = int(lid[lid.rfind('_') + 1:])
 975                if 'tl' in attrs and attrs['tl'] != "":
 976                    tl = attrs['tl']
 977                    tllink = int(attrs['linkIdx'])
 978                    tlid = attrs['tl']
 979                    toEdge = self._net.getEdge(lid[:lid.rfind('_')])
 980                    tolane2 = toEdge._lanes[tolane]
 981                    tls = self._net.addTLS(
 982                        tlid, self._currentEdge._lanes[self._currentLane], tolane2, tllink)
 983                    self._currentEdge.setTLS(tls)
 984                else:
 985                    tl = ""
 986                    tllink = -1
 987                toEdge = self._net.getEdge(lid[:lid.rfind('_')])
 988                tolane = toEdge._lanes[tolane]
 989                viaLaneID = attrs['via']
 990                self._net.addConnection(self._currentEdge, connected, self._currentEdge._lanes[
 991                                        self._currentLane], tolane,
 992                                        attrs['dir'], tl, tllink, -1,
 993                                        attrs.get('allow'), attrs.get('disallow'), attrs['state'], viaLaneID)
 994        elif name == 'connection' and self._withConnections and (attrs['from'][0] != ":" or self._withInternal):
 995            fromEdgeID = attrs['from']
 996            toEdgeID = attrs['to']
 997            if ((self._withPedestrianConnections or not (fromEdgeID in self._net._crossings_and_walkingAreas or
 998                                                         toEdgeID in self._net._crossings_and_walkingAreas))
 999                and (self._withMacroConnectors or not (fromEdgeID in self._net._macroConnectors or toEdgeID in
1000                                                       self._net._macroConnectors))):
1001                fromEdge = self._net.getEdge(fromEdgeID)
1002                toEdge = self._net.getEdge(toEdgeID)
1003                fromLane = fromEdge.getLane(int(attrs['fromLane']))
1004                toLane = toEdge.getLane(int(attrs['toLane']))
1005                if 'tl' in attrs and attrs['tl'] != "":
1006                    tl = attrs['tl']
1007                    tllink = int(attrs['linkIndex'])
1008                    tllink2 = int(attrs.get('linkIndex2', -1))
1009                    tls = self._net.addTLS(tl, fromLane, toLane, tllink)
1010                    fromEdge.setTLS(tls)
1011                else:
1012                    tl = ""
1013                    tllink = -1
1014                    tllink2 = -1
1015                try:
1016                    viaLaneID = attrs['via']
1017                except KeyError:
1018                    viaLaneID = ''
1019
1020                self._currentConnection = self._net.addConnection(
1021                    fromEdge, toEdge, fromLane, toLane, attrs['dir'], tl,
1022                    tllink, tllink2, attrs.get('allow'), attrs.get('disallow'), attrs['state'], viaLaneID)
1023
1024        # 'row-logic' is deprecated!!!
1025        elif self._withFoes and name == 'ROWLogic':
1026            self._currentNode = attrs['id']
1027        elif name == 'logicitem' and self._withFoes:  # deprecated
1028            self._net.setFoes(
1029                self._currentNode, int(attrs['request']), attrs["foes"], attrs["response"])
1030        elif name == 'request' and self._withFoes:
1031            self._currentNode.setFoes(
1032                int(attrs['index']), attrs["foes"], attrs["response"])
1033        # tl-logic is deprecated!!! NOTE: nevertheless, this is still used by
1034        # netconvert... (Leo)
1035        elif self._withPhases and name == 'tlLogic':
1036            self._currentProgram = self._net.addTLSProgram(
1037                attrs['id'], attrs['programID'],
1038                intIfPossible(float(attrs['offset'])), attrs['type'], self._latestProgram)
1039        elif self._withPhases and name == 'phase':
1040            self._currentProgram.addPhase(
1041                attrs['state'],
1042                intIfPossible(float(attrs['duration'])),
1043                intIfPossible(float(attrs['minDur'])) if 'minDur' in attrs else -1,
1044                intIfPossible(float(attrs['maxDur'])) if 'maxDur' in attrs else -1,
1045                list(map(int, attrs['next'].split())) if 'next' in attrs else [],
1046                attrs['name'] if 'name' in attrs else ""
1047            )
1048        elif name == 'roundabout':
1049            self._net.addRoundabout(
1050                attrs['nodes'].split(), attrs['edges'].split())
1051        elif name == 'param':
1052            if self._currentLane is not None:
1053                self._currentLane.setParam(attrs['key'], attrs['value'])
1054            elif self._currentEdge is not None:
1055                self._currentEdge.setParam(attrs['key'], attrs['value'])
1056            elif self._currentNode is not None:
1057                self._currentNode.setParam(attrs['key'], attrs['value'])
1058            elif self._currentConnection is not None:
1059                self._currentConnection.setParam(attrs['key'], attrs['value'])
1060            elif self._withPhases and self._currentProgram is not None:
1061                self._currentProgram.setParam(attrs['key'], attrs['value'])
1062
1063    def endElement(self, name):
1064        if name == 'lane':
1065            self._currentLane = None
1066        elif name == 'edge':
1067            self._currentEdge = None
1068        elif name == 'junction':
1069            self._currentNode = None
1070        elif name == 'connection':
1071            self._currentConnection = None
1072        # 'row-logic' is deprecated!!!
1073        elif name == 'ROWLogic' or name == 'row-logic':
1074            self._haveROWLogic = False
1075        # tl-logic is deprecated!!!
1076        elif self._withPhases and (name == 'tlLogic' or name == 'tl-logic'):
1077            self._currentProgram = None
1078        elif name == 'net':
1079            for edgeID, bidiID in self._bidiEdgeIDs.items():
1080                self._net.getEdge(edgeID)._bidi = self._net.getEdge(bidiID)
1081
1082    def endDocument(self):
1083        # set crossed edges of pedestrian crossings
1084        for crossingID, crossedEdgeIDs in self._crossingID2edgeIDs.items():
1085            pedCrossing = self._net.getEdge(crossingID)
1086            for crossedEdgeID in crossedEdgeIDs:
1087                pedCrossing._addCrossingEdge(self._net.getEdge(crossedEdgeID))
1088
1089    def getNet(self):
1090        return self._net
1091
1092
1093def convertShape(shapeString):
1094    """ Convert xml shape string into float tuples.
1095
1096    This method converts the 2d or 3d shape string from SUMO's xml file
1097    into a list containing 3d float-tuples. Non existent z coordinates default
1098    to zero. If shapeString is empty, an empty list will be returned.
1099    """
1100
1101    cshape = []
1102    for pointString in shapeString.split():
1103        p = [float(e) for e in pointString.split(",")]
1104        if len(p) == 2:
1105            cshape.append((p[0], p[1], 0.))
1106        elif len(p) == 3:
1107            cshape.append(tuple(p))
1108        else:
1109            raise ValueError(
1110                'Invalid shape point "%s", should be either 2d or 3d' % pointString)
1111    return cshape
1112
1113
1114def lane2edge(laneID):
1115    return laneID[:laneID.rfind("_")]
1116
1117
1118def lane2index(laneID):
1119    return int(laneID[laneID.rfind("_") + 1:])
1120
1121
1122def hasInternal(filename):
1123    with openz(filename) as f:
1124        for line in f:
1125            if '<edge id="' in line:
1126                if '<edge id=":' in line:
1127                    return True
1128                else:
1129                    return False
1130    return False
1131
1132
1133def readNet(filename, **others):
1134    """ load a .net.xml file
1135    The following named options are supported:
1136
1137        'net' : initialize data structures with an existing net object (default Net())
1138        'withPrograms' : import all traffic light programs (default False)
1139        'withLatestPrograms' : import only the last program for each traffic light.
1140                               This is the program that would be active in sumo by default.
1141                               (default False)
1142        'withConnections' : import all connections (default True)
1143        'withFoes' : import right-of-way information (default True)
1144        'withInternal' : import internal edges and lanes (default False)
1145        'withPedestrianConnections' : import connections between sidewalks, crossings (default False)
1146        'lxml' : set to False to use the xml.sax parser instead of the lxml parser
1147        'maxcache' : set maximum cache size (default 1000) or 0 to disable optimal route caching
1148    """
1149    netreader = NetReader(**others)
1150    try:
1151        source = gzip.open(filename)
1152        source.read(10)
1153        source.seek(0)
1154    except IOError:
1155        source = filename
1156    if HAVE_LXML and others.get("lxml", True):
1157        if isinstance(source, pathlib.Path):
1158            source = str(source)
1159        for event, v in lxml.etree.iterparse(source, events=("start", "end")):
1160            if event == "start":
1161                netreader.startElement(v.tag, v.attrib)
1162            elif event == "end":
1163                netreader.endElement(v.tag)
1164            v.clear()  # reduce memory footprint
1165    else:
1166        parse(source, netreader)
1167    net = netreader.getNet()
1168    maxcache = others.get('maxcache', 1000)
1169    if HAVE_LRU_CACHE and maxcache is not None and maxcache > 0:
1170        net.initRoutingCache(maxcache)
1171    return net