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