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