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