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