1#!/usr/local/bin/python3.8 2# Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo 3# Copyright (C) 2007-2019 German Aerospace Center (DLR) and others. 4# This program and the accompanying materials 5# are made available under the terms of the Eclipse Public License v2.0 6# which accompanies this distribution, and is available at 7# http://www.eclipse.org/legal/epl-v20.html 8# SPDX-License-Identifier: EPL-2.0 9 10# @file flowrouter.py 11# @author Michael Behrisch 12# @author Daniel Krajzewicz 13# @date 2007-06-28 14# @version $Id$ 15 16""" 17This script does flow routing similar to the dfrouter. 18It has three mandatory parameters, the SUMO net (.net.xml), a file 19specifying detectors and one for the flows. It may detect the type 20of the detectors (source, sink, inbetween) itself or read it from 21the detectors file. 22""" 23from __future__ import absolute_import 24from __future__ import division 25from __future__ import print_function 26import os 27import random 28import sys 29import heapq 30from xml.sax import make_parser, handler 31from optparse import OptionParser 32from collections import defaultdict 33sys.path.append(os.path.dirname(os.path.dirname(os.path.abspath(__file__)))) 34import sumolib # noqa 35from sumolib.net.lane import get_allowed # noqa 36import detector # noqa 37 38# Vertex class which stores incoming and outgoing edges as well as 39# auxiliary data for the flow computation. The members are accessed 40# directly. 41 42DEBUG = False 43PULL_FLOW = True 44 45 46class Vertex: 47 48 def __init__(self): 49 self.inEdges = [] 50 self.outEdges = [] 51 self.reset() 52 53 def reset(self): 54 self.inPathEdge = None 55 self.flowDelta = sys.maxsize 56 self.gain = 0 57 self.value = 0 58 if self.outEdges: 59 for e in self.outEdges: 60 self.value += (e.flow / e.numLanes if e.flow > 0 else -e.numLanes) 61 self.value /= len(self.outEdges) 62 63 def update(self, edge, flow, isForward): 64 self.inPathEdge = edge 65 self.flowDelta = flow 66 if isForward: 67 numSatEdges = edge.source.gain // edge.source.flowDelta 68 self.gain = numSatEdges * flow 69 if edge.startCapacity < sys.maxsize: 70 self.gain += flow 71 else: 72 numSatEdges = edge.target.gain // edge.target.flowDelta 73 self.gain = numSatEdges * flow 74 if edge.startCapacity < sys.maxsize: 75 self.gain -= flow 76 77 def __repr__(self): 78 return "<%s,%s,%s>" % (self.inPathEdge, self.flowDelta, self.gain) 79 80 def __lt__(self, other): 81 return self.value < other.value 82 83 84# Edge class which stores start and end vertex, type amd label of the edge 85# as well as flow and capacity for the flow computation and some parameters 86# read from the net. The members are accessed directly. 87class Edge: 88 89 def __init__(self, label, source, target, kind, linkDir=None): 90 self.label = label 91 self.source = source 92 self.target = target 93 self.kind = kind 94 self.maxSpeed = 0.0 95 self.linkDir = linkDir 96 self.length = 0.0 97 self.numLanes = 0 98 self.isOnSourcePath = False 99 self.isOnSinkPath = False 100 self.detGroup = [] 101 self.reset() 102 103 def reset(self): 104 self.capacity = sys.maxsize 105 self.startCapacity = sys.maxsize 106 self.flow = 0 107 self.routes = [] 108 self.newRoutes = [] 109 110 def getDetFlow(self): 111 result = 0 112 for group in self.detGroup: 113 if int(group.totalFlow) > result: 114 result = int(group.totalFlow) 115 return result 116 117 def __repr__(self): 118 cap = str(self.capacity) 119 if self.capacity == sys.maxsize: 120 cap = "inf" 121 return self.kind + "_" + self.label + "<" + str(self.flow) + "|" + cap + ">" 122 123 def __lt__(self, other): 124 return self.label < other.label 125 126 127# Route class storing the list of edges and the frequency of a route. 128class Route: 129 130 def __init__(self, freq, edges): 131 self.frequency = freq 132 self.edges = edges 133 self.newFrequency = None 134 135 def __repr__(self): 136 result = str(self.frequency) + " * [" 137 lastLabel = "" 138 for edge in self.edges: 139 if edge.kind == "real": 140 if lastLabel: 141 result += lastLabel + ", " 142 lastLabel = edge.label 143 return result + lastLabel + "]" 144 145 def __lt__(self, other): 146 return self.edges < other.edges 147 148 149# Net class which stores the network (vertex and edge collection) and the 150# routes. All the algorithmic stuff and the output generation are also 151# inside this class. The members are either "private" or have get/add/remove 152# methods. 153class Net: 154 155 def __init__(self): 156 self._vertices = [] 157 self._edges = {} 158 self._internalEdges = [] 159 self._possibleSources = set() 160 self._possibleSinks = set() 161 self._source = self.newVertex() 162 self._sink = self.newVertex() 163 self._edgeRestriction = {} 164 self._routeRestriction = {} 165 if options.restrictionfile: 166 for f in options.restrictionfile.split(","): 167 for line in open(f): 168 ls = line.split() 169 if len(ls) == 2: 170 self._edgeRestriction[ls[1]] = int(ls[0]) 171 else: 172 self._routeRestriction[tuple(ls[1:])] = int(ls[0]) 173 if options.verbose: 174 print("Loaded %s edge restrictions and %s route restrictions" % 175 (len(self._edgeRestriction), len(self._routeRestriction))) 176 177 def newVertex(self): 178 v = Vertex() 179 self._vertices.append(v) 180 return v 181 182 def getEdge(self, edgeLabel): 183 if edgeLabel in self._edges: 184 return self._edges[edgeLabel] 185 else: 186 raise RuntimeError("edge '%s' not found" % edgeLabel) 187 188 def addEdge(self, edgeObj): 189 edgeObj.source.outEdges.append(edgeObj) 190 edgeObj.target.inEdges.append(edgeObj) 191 if edgeObj.kind == "real": 192 self._edges[edgeObj.label] = edgeObj 193 else: 194 assert edgeObj.target == self._sink or len(edgeObj.target.outEdges) == 1 195 if len(edgeObj.target.outEdges) == 1: 196 edgeObj.numLanes = edgeObj.target.outEdges[0].numLanes 197 else: 198 edgeObj.numLanes = 1 199 self._internalEdges.append(edgeObj) 200 201 def removeEdge(self, edgeObj): 202 edgeObj.source.outEdges.remove(edgeObj) 203 edgeObj.target.inEdges.remove(edgeObj) 204 if edgeObj.kind == "real": 205 del self._edges[edgeObj.label] 206 checkEdges = set(edgeObj.source.inEdges).union(edgeObj.target.outEdges) 207 for edge in checkEdges: 208 if edge.kind != "real": 209 self.removeEdge(edge) 210 211 def addIsolatedRealEdge(self, edgeLabel): 212 self.addEdge(Edge(edgeLabel, self.newVertex(), self.newVertex(), 213 "real")) 214 215 def addSourceEdge(self, edgeObj): 216 newEdge = Edge("s_" + edgeObj.label, self._source, edgeObj.source, 217 "source") 218 self.addEdge(newEdge) 219 220 def addSinkEdge(self, edgeObj): 221 newEdge = Edge("t_" + edgeObj.label, edgeObj.target, self._sink, 222 "sink") 223 self.addEdge(newEdge) 224 225 def trimNet(self): 226 if options.minspeed > 0.0: 227 if options.verbose: 228 print("Removing edges with maxspeed < %s," % 229 options.minspeed, end=' ') 230 # The code in the following loop assumes there are still all 231 # auxiliary junction edges present. 232 for edgeObj in self._edges.values(): 233 if edgeObj.maxSpeed < options.minspeed: 234 if len(edgeObj.detGroup) == 0 or not options.keepdet: 235 for auxpred in edgeObj.source.inEdges: 236 for realpred in auxpred.source.inEdges: 237 if realpred.maxSpeed >= options.minspeed: 238 self._possibleSinks.add(realpred) 239 for auxsucc in edgeObj.target.outEdges: 240 for realsucc in auxsucc.target.outEdges: 241 if realsucc.maxSpeed >= options.minspeed: 242 self._possibleSources.add(realsucc) 243 self.removeEdge(edgeObj) 244 if options.verbose: 245 print(len(self._edges), "left") 246 if options.trimfile: 247 trimOut = open(options.trimfile, 'w') 248 for edge in self._edges.values(): 249 print("edge:" + edge.label, file=trimOut) 250 trimOut.close() 251 252 def detectSourceSink(self, sources, sinks): 253 self.trimNet() 254 for id in sorted(sources): 255 self.addSourceEdge(self.getEdge(id)) 256 for id in sorted(sinks): 257 self.addSinkEdge(self.getEdge(id)) 258 foundSources = [] 259 foundSinks = [] 260 for edgeObj in sorted(self._edges.values()): 261 if len(sources) == 0 and (len(edgeObj.source.inEdges) == 0 or edgeObj in self._possibleSources): 262 if edgeObj.numLanes > 0: 263 self.addSourceEdge(edgeObj) 264 foundSources.append(edgeObj.label) 265 if len(sinks) == 0 and (len(edgeObj.target.outEdges) == 0 or edgeObj in self._possibleSinks): 266 if edgeObj.numLanes > 0: 267 if edgeObj.label in foundSources: 268 print("Error! Edge '%s' is simultaneously source and sink." % edgeObj.label) 269 return False 270 self.addSinkEdge(edgeObj) 271 foundSinks.append(edgeObj.label) 272 if options.verbose: 273 print(("Loaded %s sources and %s sinks from detector file. Added %s sources and %s sinks " + 274 "from the network") % ( 275 len(sources), len(sinks), len(foundSources), len(foundSinks))) 276 if options.source_sink_output: 277 with open(options.source_sink_output, 'w') as outf: 278 outf.write('<detectors>\n') 279 freq = options.interval * 60 if options.interval else 24 * 3600 280 for source in foundSources: 281 outf.write((' <e1Detector id="%s_0" lane="%s_0" pos="1" type="source" friendlyPos="true" ' + 282 'file="NUL" freq="%s"/>\n') % 283 (source, source, freq)) 284 for sink in foundSinks: 285 outf.write((' <e1Detector id="%s_0" lane="%s_0" pos="-1" type="sink" friendlyPos="true" ' + 286 'file="NUL" freq="%s"/>\n') % 287 (sink, sink, freq)) 288 outf.write('</detectors>\n') 289 290 if len(self._sink.inEdges) == 0: 291 print("Error! No sinks found.") 292 return False 293 if len(self._source.outEdges) == 0: 294 print("Error! No sources found.") 295 return False 296 return True 297 298 def initNet(self): 299 for edge in self._internalEdges: 300 edge.reset() 301 flowRestriction = sys.maxsize 302 if options.maxturnflow and edge.linkDir == 't': 303 flowRestriction = int(options.maxturnflow * options.interval / 60) 304 if edge.label in self._edgeRestriction: 305 flowRestriction = int(self._edgeRestriction[edge.label] * options.interval / 60) 306 edge.capacity = min(edge.capacity, flowRestriction) 307 for edge in self._edges.values(): 308 edge.reset() 309 if len(edge.detGroup) > 0: 310 edge.capacity = 0 311 for group in edge.detGroup: 312 if int(group.totalFlow) > edge.capacity: 313 edge.capacity = int(group.totalFlow) 314 if not options.respectzero and edge.capacity == 0: 315 edge.capacity = sys.maxsize 316 edge.startCapacity = edge.capacity 317 flowRestriction = sys.maxsize if edge.numLanes > 0 else 0 318 if options.maxflow: 319 flowRestriction = int(options.maxflow * edge.numLanes * options.interval / 60) 320 if options.maxturnflow and edge.linkDir == 't': 321 flowRestriction = int(options.maxturnflow * options.interval / 60) 322 if edge.label in self._edgeRestriction: 323 flowRestriction = int(self._edgeRestriction[edge.label] * options.interval / 60) 324 edge.capacity = min(edge.capacity, flowRestriction) 325 # collect limited source edges 326 for s in self._source.outEdges: 327 queue = [s] 328 s.isOnSourcePath = True 329 while queue: 330 edgeObj = queue.pop(0) 331 if edgeObj.startCapacity == sys.maxsize: 332 if len(edgeObj.target.inEdges) > 1: 333 s.isOnSourcePath = False 334 break 335 else: 336 queue += edgeObj.target.outEdges 337 # collect limited sink edges 338 for s in self._sink.inEdges: 339 queue = [s] 340 s.isOnSinkPath = True 341 while queue: 342 edgeObj = queue.pop(0) 343 if edgeObj.startCapacity == sys.maxsize: 344 if len(edgeObj.source.outEdges) > 1: 345 s.isOnSinkPath = False 346 break 347 else: 348 queue += edgeObj.source.inEdges 349 350 if options.verbose: 351 unlimitedSource = 0 352 for edgeObj in self._source.outEdges: 353 for src in edgeObj.target.outEdges: 354 if src.capacity == sys.maxsize: 355 unlimitedSource += 1 356 unlimitedSink = 0 357 for edgeObj in self._sink.inEdges: 358 for sink in edgeObj.source.inEdges: 359 if sink.capacity == sys.maxsize: 360 unlimitedSink += 1 361 print(len(self._source.outEdges), "sources,", end=' ') 362 print(unlimitedSource, "unlimited") 363 print(len(self._sink.inEdges), "sinks,", 364 unlimitedSink, "unlimited") 365 366 def splitRoutes(self, stubs, currEdge, upstreamBackEdges, newRoutes, alteredRoutes): 367 newStubs = [] 368 backSet = set(upstreamBackEdges) 369 while len(stubs) > 0: 370 routeStub = stubs.pop() 371 if len(routeStub.edges) > 0 and currEdge == routeStub.edges[0]: 372 routeStub.edges.pop(0) 373 newStubs.append(routeStub) 374 else: 375 if DEBUG: 376 print(" trying to split", routeStub) 377 assert(len(currEdge.routes) > 0) 378 for route in currEdge.routes + currEdge.newRoutes: 379 if route.newFrequency == 0: 380 continue 381 edgePos = route.edges.index(currEdge) 382 backPath = False 383 hadForward = False 384 for edge in route.edges[edgePos + 1:]: 385 if edge in backSet: 386 if hadForward: 387 if DEBUG: 388 print(" skipping", route, "because", edge, "is in", backSet) 389 backPath = True 390 break 391 else: 392 hadForward = True 393 if backPath: 394 continue 395 routeFreq = route.frequency if route.newFrequency is None else route.newFrequency 396 newRoute = Route(min(routeStub.frequency, routeFreq), 397 route.edges[:edgePos] + routeStub.edges) 398 newRoutes.append(newRoute) 399 for edge in newRoute.edges: 400 edge.newRoutes.append(route) 401 newStubs.append(Route(newRoute.frequency, 402 route.edges[edgePos + 1:])) 403 if route.newFrequency is None: 404 route.newFrequency = route.frequency 405 route.newFrequency -= newRoute.frequency 406 alteredRoutes.append(route) 407 routeStub.frequency -= newRoute.frequency 408 if routeStub.frequency == 0: 409 break 410 if routeStub.frequency > 0: 411 if DEBUG: 412 print(" Could not split", routeStub) 413 return False 414 stubs.extend(newStubs) 415 return True 416 417 def updateFlow(self, startVertex, endVertex): 418 assert endVertex.flowDelta < sys.maxsize 419 if options.limit and endVertex.flowDelta > options.limit: 420 endVertex.flowDelta = options.limit 421 stubs = [Route(endVertex.flowDelta, [])] 422 if DEBUG: 423 print(" updateFlow start=%s end=%s flowDelta=%s" % (startVertex, 424 endVertex, endVertex.flowDelta)) 425 upstreamBackEdges = list(self.getBackEdges(startVertex, endVertex)) 426 newRoutes = [] 427 alteredRoutes = [] 428 flowDeltas = [] 429 cycleStartStep = (startVertex == endVertex) 430 currVertex = endVertex 431 while currVertex != startVertex or cycleStartStep: 432 cycleStartStep = False 433 currEdge = currVertex.inPathEdge 434 if currEdge.target == currVertex: 435 if DEBUG: # and not currEdge.kind == 'junction': 436 print(" incFlow edge=%s delta=%s" % (currEdge, endVertex.flowDelta)) 437 flowDeltas.append((currEdge, endVertex.flowDelta)) 438 currVertex = currEdge.source 439 for routeStub in stubs: 440 routeStub.edges.insert(0, currEdge) 441 else: 442 if DEBUG: 443 print(" decFlow edge=%s delta=%s" % (currEdge, endVertex.flowDelta)) 444 flowDeltas.append((currEdge, -endVertex.flowDelta)) 445 currVertex = currEdge.target 446 upstreamBackEdges.pop(0) 447 if not self.splitRoutes(stubs, currEdge, upstreamBackEdges, newRoutes, alteredRoutes): 448 # resetting to previous state 449 for route in alteredRoutes: 450 route.newFrequency = None 451 for route in newRoutes: 452 for edge in route.edges: 453 del edge.newRoutes[:] 454 if DEBUG: 455 self.testFlowInvariants() 456 return False 457 if DEBUG: 458 self.testFlowInvariants() 459 # up to here no modification of existing edges or routes in case splitting fails 460 for edge, delta in flowDeltas: 461 edge.flow += delta 462 for route in alteredRoutes: 463 if route.newFrequency is not None: # otherwise it has been handled before 464 if route.newFrequency == 0: 465 for edge in route.edges: 466 edge.routes.remove(route) 467 else: 468 route.frequency = route.newFrequency 469 route.newFrequency = None 470 for route in stubs + newRoutes: 471 for edge in route.edges: 472 edge.routes.append(route) 473 del edge.newRoutes[:] 474 if DEBUG: 475 self.testFlowInvariants() 476 return True 477 478 def endsRestrictedRoute(self, edge): 479 if not self._routeRestriction: 480 return False 481 currVertex = edge.source 482 routeEdgeObj = [edge] 483 route = [] 484 count = currVertex.flowDelta 485 if options.limit and count > options.limit: 486 count = options.limit 487 while currVertex != self._source: 488 edge = currVertex.inPathEdge 489 if edge.target == currVertex: 490 if edge.kind == "real": 491 route.insert(0, edge.label) 492 routeEdgeObj.insert(0, edge) 493 currVertex = edge.source 494 else: 495 return False 496 for r in edge.routes: 497 if r.edges == routeEdgeObj: 498 count += r.frequency 499 if DEBUG: 500 print(" checking limit for route %s count %s" % (route, count)) 501 return count > self._routeRestriction.get(tuple(route), 502 # check origin-destination restriction 503 self._routeRestriction.get((route[0], route[-1]), count)) 504 505 def getBackEdges(self, pathStart, currVertex): 506 cycleStartStep = (pathStart == currVertex) 507 while currVertex != pathStart or cycleStartStep: 508 cycleStartStep = False 509 edge = currVertex.inPathEdge 510 if edge.source == currVertex: 511 yield edge 512 currVertex = edge.target 513 else: 514 currVertex = edge.source 515 516 def findPath(self, startVertex, pathStart, limitedSource=True, limitedSink=True, allowBackward=True): 517 queue = [startVertex] 518 if DEBUG: 519 print(" findPath start=%s pathStart=%s limits(%s, %s)" % 520 (startVertex, pathStart, limitedSource, limitedSink)) 521 while len(queue) > 0: 522 currVertex = heapq.heappop(queue) 523 if currVertex == self._sink or (currVertex == self._source and currVertex.inPathEdge): 524 if self.updateFlow(pathStart, currVertex): 525 return True 526 continue 527 for edge in currVertex.outEdges: 528 if limitedSource and currVertex == self._source and not edge.isOnSourcePath: 529 continue 530 if limitedSink and edge.target == self._sink and not edge.isOnSinkPath: 531 continue 532 if edge.target == self._sink and self.endsRestrictedRoute(edge): 533 continue 534 if not edge.target.inPathEdge and edge.flow < edge.capacity: 535 if edge.target != self._sink or currVertex.gain > 0: 536 heapq.heappush(queue, edge.target) 537 edge.target.update(edge, min(currVertex.flowDelta, 538 edge.capacity - edge.flow), 539 True) 540 if allowBackward: 541 for edge in currVertex.inEdges: 542 if not edge.source.inPathEdge and edge.flow > 0: 543 if edge.source != self._source or currVertex.gain > 0: 544 heapq.heappush(queue, edge.source) 545 edge.source.update(edge, min(currVertex.flowDelta, 546 edge.flow), False) 547 return False 548 549 def savePulledPath(self, startVertex, unsatEdge, pred): 550 numSatEdges = 1 551 currVertex = startVertex 552 while currVertex != unsatEdge.source: 553 currEdge = pred[currVertex] 554 if currEdge.target == currVertex: 555 currEdge.source.inPathEdge = currEdge 556 currVertex = currEdge.source 557 if currEdge.capacity < sys.maxsize: 558 numSatEdges -= 1 559 else: 560 currEdge.target.inPathEdge = currEdge 561 currVertex = currEdge.target 562 if currEdge.capacity < sys.maxsize: 563 numSatEdges += 1 564 startVertex.inPathEdge = None 565 unsatEdge.target.flowDelta = startVertex.flowDelta 566 unsatEdge.target.gain = startVertex.flowDelta * numSatEdges 567 568 def pullFlow(self, unsatEdge, limitSource, limitSink, allowBackward): 569 if DEBUG: 570 print("Trying to increase flow on", unsatEdge) 571 for vertex in self._vertices: 572 vertex.reset() 573 pred = {unsatEdge.target: unsatEdge, unsatEdge.source: unsatEdge} 574 unsatEdge.target.inPathEdge = unsatEdge 575 unsatEdge.source.flowDelta = unsatEdge.capacity - unsatEdge.flow 576 queue = [unsatEdge.source] 577 while len(queue) > 0: 578 currVertex = queue.pop(0) 579 if ((currVertex == self._source and (not limitSource or pred[currVertex].isOnSourcePath)) or 580 currVertex == self._sink): 581 self.savePulledPath(currVertex, unsatEdge, pred) 582 return self.findPath(unsatEdge.target, currVertex, limitSource, limitSink, allowBackward) 583 for edge in currVertex.inEdges: 584 if edge.source not in pred and edge.flow < edge.capacity: 585 queue.append(edge.source) 586 pred[edge.source] = edge 587 edge.source.flowDelta = min( 588 currVertex.flowDelta, edge.capacity - edge.flow) 589 if allowBackward: 590 # inverse find path semantics 591 for edge in currVertex.outEdges: 592 if edge.target not in pred and edge.flow > 0: 593 queue.append(edge.target) 594 pred[edge.target] = edge 595 edge.target.flowDelta = min( 596 currVertex.flowDelta, edge.flow) 597 return False 598 599 def testFlowInvariants(self): 600 # the following code only tests assertions 601 for vertex in self._vertices: 602 flowSum = 0 603 for preEdge in vertex.inEdges: 604 flowSum += preEdge.flow 605 for succEdge in vertex.outEdges: 606 flowSum -= succEdge.flow 607 totalEdgeFlow = 0 608 for route in succEdge.routes: 609 assert route.frequency > 0 610 totalEdgeFlow += route.frequency 611 if DEBUG and totalEdgeFlow != succEdge.flow: 612 print("total edge flow failed", totalEdgeFlow, succEdge) 613 for r in succEdge.routes: 614 print(r) 615 assert totalEdgeFlow == succEdge.flow 616 assert vertex == self._source or vertex == self._sink or flowSum == 0 617 618 def calcRoutes(self, allowBackward=True): 619 for limitSource, limitSink in ((True, True), (True, False), (False, True), (False, False)): 620 pathFound = True 621 while pathFound: 622 for vertex in self._vertices: 623 vertex.reset() 624 pathFound = self.findPath(self._source, self._source, limitSource, limitSink, allowBackward) 625 if not pathFound and PULL_FLOW and not limitSource and not limitSink: 626 for i, edge in enumerate(sorted(self._edges.values())): 627 if DEBUG and options.verbose and i > 0 and i % 100 == 0: 628 print("pullFlow %.2f%%" % (100 * i / len(self._edges))) 629 if edge.startCapacity < sys.maxsize: 630 while (edge.flow < edge.capacity and 631 self.pullFlow(edge, limitSource, limitSink, allowBackward)): 632 pathFound = True 633 if DEBUG: 634 totalDetFlow = 0 635 for edge in self._edges.values(): 636 if edge.startCapacity < sys.maxsize: 637 totalDetFlow += edge.flow 638 print("detFlow", totalDetFlow) 639 if DEBUG: 640 self.testFlowInvariants() 641 self.consolidateRoutes() 642 self.testFlowInvariants() 643 644 def consolidateRoutes(self): 645 for edge in self._source.outEdges: 646 routeByEdges = {} 647 for route in edge.routes: 648 key = tuple([e.label for e in route.edges if e.kind == "real"]) 649 if key in routeByEdges: 650 routeByEdges[key].frequency += route.frequency 651 for e in route.edges[1:]: 652 e.routes.remove(route) 653 elif route.frequency > 0: 654 routeByEdges[key] = route 655 edge.routes = sorted(routeByEdges.values()) 656 657 def applyRouteRestrictions(self): 658 removed = False 659 deleteRoute = [] 660 for edge in self._source.outEdges: 661 for route in edge.routes: 662 key = tuple([e.label for e in route.edges if e.kind == "real"]) 663 restriction = self._routeRestriction.get(key, 664 self._routeRestriction.get((key[0], key[-1]), sys.maxsize)) 665 surplus = route.frequency - restriction 666 if surplus > 0: 667 if DEBUG: 668 print("route '%s' surplus=%s" % (" ".join(key), surplus)) 669 removed = True 670 for e in route.edges: 671 e.flow -= surplus 672 for e in route.edges[1:]: 673 if restriction == 0: 674 e.routes.remove(route) 675 if restriction == 0: 676 deleteRoute.append(route) 677 else: 678 route.frequency = restriction 679 if deleteRoute: 680 edge.routes = [r for r in edge.routes if r not in deleteRoute] 681 if DEBUG: 682 self.testFlowInvariants() 683 return removed 684 685 def writeRoutes(self, routeOut, suffix=""): 686 totalFlow = 0 687 for edge in self._source.outEdges: 688 totalFlow += edge.flow 689 targetCount = defaultdict(lambda: 0) 690 for route in edge.routes: 691 if routeOut is None: 692 print(route) 693 continue 694 firstReal = '' 695 lastReal = None 696 routeString = '' 697 for redge in route.edges: 698 if redge.kind == "real": 699 if options.lanebased: 700 routeString += redge.label[:redge.label.rfind("_")] + " " 701 else: 702 routeString += redge.label + " " 703 if firstReal == '': 704 firstReal = redge.label 705 lastReal = redge 706 assert firstReal != '' and lastReal is not None 707 index = "" if targetCount[lastReal] == 0 else ".%s" % targetCount[lastReal] 708 targetCount[lastReal] += 1 709 route.routeID = "%s_%s%s%s" % (firstReal, lastReal.label, index, suffix) 710 print(' <route id="%s" edges="%s"/>' % ( 711 route.routeID, routeString.strip()), file=routeOut) 712 if routeOut is None: 713 print("total flow:", totalFlow) 714 715 def writeEmitters(self, emitOut, begin=0, end=3600, suffix=""): 716 if not emitOut: 717 return 718 totalFlow = 0 719 numSources = 0 720 unusedSources = [] 721 for srcEdge in self._source.outEdges: 722 if len(srcEdge.routes) == 0: 723 unusedSources.append(srcEdge.target.outEdges[0].label) 724 continue 725 assert len(srcEdge.target.outEdges) == 1 726 totalFlow += srcEdge.flow 727 numSources += 1 728 edge = srcEdge.target.outEdges[0] 729 if options.random: 730 ids = " ".join(r.routeID for r in srcEdge.routes) 731 probs = " ".join([str(route.frequency) 732 for route in srcEdge.routes]) 733 print(' <flow id="%s%s" %s number="%s" begin="%s" end="%s">' % 734 (edge.label, suffix, options.params, int(srcEdge.flow), begin, end), file=emitOut) 735 print(' <routeDistribution routes="%s" probabilities="%s"/>' % (ids, probs), file=emitOut) 736 print(' </flow>', file=emitOut) 737 else: 738 for route in srcEdge.routes: 739 via = "" 740 if options.viadetectors: 741 realEdges = [e for e in route.edges if e.kind == "real"] 742 # exclude detectors on 'from' and 'to' edge 743 detEdges = [e.label for e in realEdges[1:-1] if e.getDetFlow() > 0] 744 # avoid duplicate via-edges 745 viaEdges = [] 746 for e in detEdges: 747 if not viaEdges or viaEdges[-1] != e: 748 viaEdges.append(e) 749 if viaEdges: 750 via = ' via="%s"' % " ".join(viaEdges) 751 print(' <flow id="%s" %s route="%s" number="%s" begin="%s" end="%s"%s/>' % 752 (route.routeID, options.params, route.routeID, 753 int(route.frequency), begin, end, via), file=emitOut) 754 755 if options.verbose: 756 print("Writing %s vehicles from %s sources between time %s and %s (minutes)" % ( 757 totalFlow, numSources, int(begin / 60), int(end / 60))) 758 if len(unusedSources) > 0: 759 print(" unused sources:", " ".join(unusedSources)) 760 761 for s in self._sink.inEdges: 762 queue = [s] 763 s.isOnSinkPath = True 764 while queue: 765 queue.pop(0) 766 767 def writeFlowPOIs(self, poiOut, suffix=""): 768 if not poiOut: 769 return 770 for edge in self._edges.values(): 771 color = "0,0,1" 772 for src in edge.source.inEdges: 773 if src.source == self._source: 774 color = "0,1,0" 775 break 776 for sink in edge.target.outEdges: 777 if sink.target == self._sink: 778 color = "1," + color[2] + ",0" 779 break 780 if edge.flow == edge.startCapacity: 781 color = ".5,.5,.5" 782 cap = ":c" + str(edge.startCapacity) 783 if edge.startCapacity == sys.maxsize: 784 cap = "" 785 if edge.isOnSourcePath: 786 cap += "-source" 787 if edge.isOnSinkPath: 788 cap += "-sink" 789 lane = edge.label if options.lanebased else edge.label + "_0" 790 print(' <poi id="%s_f%s%s%s" color="%s" lane="%s" pos="%s"/>' % ( 791 edge.label, edge.flow, cap, suffix, color, lane, random.random() * edge.length), file=poiOut) 792 793 794# The class for parsing the XML and CSV input files. The data parsed is 795# written into the net. All members are "private". 796class NetDetectorFlowReader(handler.ContentHandler): 797 798 def __init__(self, net): 799 self._net = net 800 self._edge = '' 801 self._lane2edge = {} 802 self._detReader = None 803 804 def startElement(self, name, attrs): 805 if name == 'edge' and ('function' not in attrs or attrs['function'] != 'internal'): 806 self._edge = attrs['id'] 807 if not options.lanebased: 808 self._net.addIsolatedRealEdge(attrs['id']) 809 elif name == 'connection': 810 fromEdgeID = attrs['from'] 811 if fromEdgeID[0] != ":": 812 toEdgeID = attrs['to'] 813 if options.lanebased: 814 fromEdgeID += "_" + attrs["fromLane"] 815 toEdgeID += "_" + attrs["toLane"] 816 v = self._net.getEdge(fromEdgeID).target 817 eID = fromEdgeID + "->" + toEdgeID 818 for e in v.outEdges: 819 if e.label == eID: 820 return 821 newEdge = Edge(eID, v, self._net.getEdge(toEdgeID).source, "junction", attrs['dir']) 822 self._net.addEdge(newEdge) 823 elif name == 'lane' and self._edge != '': 824 if options.lanebased: 825 self._net.addIsolatedRealEdge(attrs['id']) 826 self._edge = attrs['id'] 827 self._lane2edge[attrs['id']] = self._edge 828 edgeObj = self._net.getEdge(self._edge) 829 edgeObj.maxSpeed = max(edgeObj.maxSpeed, float(attrs['speed'])) 830 edgeObj.length = float(attrs['length']) 831 if (options.vclass is None or 832 options.vclass in get_allowed(attrs.get('allow'), attrs.get('disallow'))): 833 edgeObj.numLanes += 1 834 835 def endElement(self, name): 836 if name == 'edge': 837 self._edge = '' 838 839 def readDetectors(self, detFile): 840 self._detReader = detector.DetectorReader(detFile, self._lane2edge) 841 for edge, detGroups in self._detReader._edge2DetData.items(): 842 for group in detGroups: 843 if group.isValid: 844 self._net.getEdge(edge).detGroup.append(group) 845 sources = set() 846 sinks = set() 847 for det in sumolib.xml.parse(detFile, ["detectorDefinition", "e1Detector"]): 848 if hasattr(det, "type"): 849 if det.type == "source": 850 if options.lanebased: 851 sources.add(det.lane) 852 else: 853 sources.add(det.lane[:det.lane.rfind("_")]) 854 if det.type == "sink": 855 if options.lanebased: 856 sinks.add(det.lane) 857 else: 858 sinks.add(det.lane[:det.lane.rfind("_")]) 859 return sources, sinks 860 861 def readFlows(self, flowFile, t=None, tMax=None): 862 if t is None: 863 return self._detReader.readFlows(flowFile, flow=options.flowcol) 864 else: 865 return self._detReader.readFlows(flowFile, flow=options.flowcol, time="Time", timeVal=t, timeMax=tMax) 866 867 def clearFlows(self): 868 self._detReader.clearFlows() 869 870 def readSyntheticFlows(self, start=None, end=None): 871 if options.syntheticflowfile is None: 872 return 873 if start is not None: 874 times = [float(t) / 100. for t in options.timeline.split(",")] 875 factor = sum([times[t] for t in range(start // 60, end // 60)]) 876 else: 877 factor = 1. 878 for f in options.syntheticflowfile.split(","): 879 for line in open(f): 880 flow, edge = line.split() 881 edgeObj = self._net.getEdge(edge) 882 groups = self._detReader.getEdgeDetGroups(edge) 883 if len(groups) == 0: 884 self._detReader.addDetector(edge, edgeObj.length / 2, edge) 885 self._net.getEdge(edge).detGroup.append(self._detReader.getEdgeDetGroups(edge)[0]) 886 self._detReader.addFlow(edge, int(float(flow) * factor)) 887 888 889def addFlowFile(option, opt_str, value, parser): 890 if not getattr(parser.values, option.dest, None): 891 setattr(parser.values, option.dest, []) 892 fileList = getattr(parser.values, option.dest) 893 fileList.append(value) 894 index = 0 895 while index < len(parser.rargs) and not parser.rargs[index].startswith("-"): 896 index += 1 897 fileList.extend(parser.rargs[0:index]) 898 parser.rargs = parser.rargs[index:] 899 900 901optParser = OptionParser() 902optParser.add_option("-n", "--net-file", dest="netfile", 903 help="read SUMO network from FILE (mandatory)", metavar="FILE") 904optParser.add_option("-d", "--detector-file", dest="detfile", 905 help="read detectors from FILE (mandatory)", metavar="FILE") 906optParser.add_option("--revalidate-detectors", action="store_true", dest="revalidate", 907 default=False, help="ignore source and sink information in detector file") 908optParser.add_option("-f", "--detector-flow-files", dest="flowfiles", 909 action="callback", callback=addFlowFile, type="string", 910 help="read detector flows from FILE(s) (mandatory)", metavar="FILE") 911optParser.add_option("-c", "--flow-column", dest="flowcol", default="qPKW", 912 help="which column contains flows", metavar="STRING") 913optParser.add_option("-o", "--routes-output", dest="routefile", 914 help="write routes to FILE", metavar="FILE") 915optParser.add_option("-e", "--emitters-output", dest="emitfile", 916 help="write emitters to FILE and create files per emitter (needs -o)", metavar="FILE") 917optParser.add_option("-y", "--params", help="vehicle / flow params to use (vType, departPos etc.)", 918 default='departSpeed="max" departPos="last" departLane="best"', metavar="STRING") 919optParser.add_option("-t", "--trimmed-output", dest="trimfile", 920 help="write edges of trimmed network to FILE", metavar="FILE") 921optParser.add_option("-p", "--flow-poi-output", dest="flowpoifile", 922 help="write resulting flows as SUMO POIs to FILE", metavar="FILE") 923optParser.add_option("--source-sink-output", dest="source_sink_output", 924 help="write sources and sinks in detector format to FILE", metavar="FILE") 925optParser.add_option("-m", "--min-speed", type="float", dest="minspeed", 926 default=0.0, help="only consider edges where the fastest lane allows at least this " + 927 "maxspeed (m/s)") 928optParser.add_option("-M", "--max-flow", type="int", dest="maxflow", 929 help="limit the number of vehicles per lane and hour to this value") 930optParser.add_option("--max-turn-flow", type="int", dest="maxturnflow", 931 help="limit the number of vehicles per turn-around connection and hour to this value") 932optParser.add_option("-r", "--flow-restrictions", dest="restrictionfile", 933 help="read edge and route restrictions from FILEs (each line starts with '<maxHourlyFlow> ' " + 934 "followed by <edgeID> or '<originEdgeID> <destEdgeID>' or '<e1> <e2> ... <en>')", 935 metavar="FILE+") 936optParser.add_option("-s", "--synthetic-flows", dest="syntheticflowfile", 937 help="read artificial detector values from FILE (lines of the form '<dailyFlow> <edgeID>')", 938 metavar="FILE") 939optParser.add_option("--timeline", default=("0.9,0.5,0.2,0.2,0.5,1.3,7.0,9.3,6.7,4.2,4.0,3.8," + 940 "4.1,4.6,5.0,6.7,9.6,9.2,7.1,4.8,3.5,2.7,2.2,1.9"), 941 help="use time line for artificial detector values") 942optParser.add_option("-D", "--keep-det", action="store_true", dest="keepdet", 943 default=False, help='keep edges with detectors when deleting "slow" edges') 944optParser.add_option("-z", "--respect-zero", action="store_true", dest="respectzero", 945 default=False, help="respect detectors without data (or with permanent zero) with zero flow") 946optParser.add_option("-l", "--lane-based", action="store_true", dest="lanebased", 947 default=False, help="do not aggregate detector data and connections to edges") 948optParser.add_option("-i", "--interval", type="int", help="aggregation interval in minutes") 949optParser.add_option("-b", "--begin", type="int", help="begin time in minutes") 950optParser.add_option("--limit", type="int", help="limit the amount of flow assigned in a single step") 951optParser.add_option("--vclass", help="only consider lanes that allow the given vehicle class") 952optParser.add_option("-q", "--quiet", action="store_true", dest="quiet", 953 default=False, help="suppress warnings") 954optParser.add_option("--random", action="store_true", dest="random", 955 default=False, help="write route distributions instead of separate flows") 956optParser.add_option("--via-detectors", action="store_true", dest="viadetectors", 957 default=False, help="set used detectors as via-edges for generated flows") 958optParser.add_option("-v", "--verbose", action="store_true", dest="verbose", 959 default=False, help="tell me what you are doing") 960optParser.add_option("--debug", action="store_true", default=False, help="tell me what you are doing in high detail") 961(options, args) = optParser.parse_args() 962if not options.netfile or not options.detfile or not options.flowfiles: 963 optParser.print_help() 964 sys.exit() 965if options.emitfile and not options.routefile: 966 optParser.print_help() 967 sys.exit() 968if (options.restrictionfile is not None or options.maxflow is not None) and options.interval is None: 969 print("Restrictions need interval length") 970 optParser.print_help() 971 sys.exit() 972 973DEBUG = options.debug 974parser = make_parser() 975if options.verbose: 976 print("Reading net") 977net = Net() 978reader = NetDetectorFlowReader(net) 979parser.setContentHandler(reader) 980parser.parse(options.netfile) 981if options.verbose: 982 print(len(net._edges), "edges read") 983 print("Reading detectors") 984sources, sinks = reader.readDetectors(options.detfile) 985if options.revalidate: 986 sources = sinks = [] 987if net.detectSourceSink(sources, sinks): 988 routeOut = None 989 if options.routefile: 990 routeOut = open(options.routefile, 'w') 991 print("<routes>", file=routeOut) 992 emitOut = None 993 if options.emitfile: 994 emitOut = open(options.emitfile, 'w') 995 print("<additional>", file=emitOut) 996 poiOut = None 997 if options.flowpoifile: 998 poiOut = open(options.flowpoifile, 'w') 999 print("<pois>", file=poiOut) 1000 if options.interval: 1001 tMin = None 1002 tMax = None 1003 for flow in options.flowfiles: 1004 tMin, tMax = reader._detReader.findTimes(flow, tMin, tMax) 1005 if tMin is None: 1006 print("No flows in '%s'" % flow) 1007 sys.exit(1) 1008 if options.begin is not None and options.begin > tMin: 1009 tMin = options.begin 1010 if options.verbose: 1011 print("Reading flows between %s and %s" % (tMin, tMax)) 1012 start = int(tMin - (tMin % options.interval)) 1013 while start <= tMax: 1014 suffix = ".%s.%s" % (options.flowcol, start) 1015 for flow in options.flowfiles: 1016 haveFlows = reader.readFlows( 1017 flow, start, start + options.interval) 1018 if haveFlows: 1019 reader.readSyntheticFlows(start, start + options.interval) 1020 if options.verbose: 1021 print("Calculating routes") 1022 net.initNet() 1023 net.calcRoutes() 1024 # run again (in forward only mode) if restricted routes were removed 1025 if net.applyRouteRestrictions(): 1026 net.calcRoutes(False) 1027 net.writeRoutes(routeOut, suffix) 1028 net.writeEmitters( 1029 emitOut, 60 * start, 60 * (start + options.interval), suffix) 1030 net.writeFlowPOIs(poiOut, suffix) 1031 else: 1032 if options.verbose: 1033 print("No flows found") 1034 reader.clearFlows() 1035 start += options.interval 1036 else: 1037 if options.verbose: 1038 print("Reading flows") 1039 for flow in options.flowfiles: 1040 reader.readFlows(flow) 1041 reader.readSyntheticFlows() 1042 if options.verbose: 1043 print("Calculating routes") 1044 net.initNet() 1045 net.calcRoutes() 1046 # run again (in forward only mode) if restricted routes were removed 1047 if net.applyRouteRestrictions(): 1048 net.calcRoutes(False) 1049 net.writeRoutes(routeOut, "." + options.flowcol) 1050 net.writeEmitters(emitOut, suffix=options.flowcol) 1051 net.writeFlowPOIs(poiOut) 1052 if routeOut: 1053 print("</routes>", file=routeOut) 1054 routeOut.close() 1055 if emitOut: 1056 print("</additional>", file=emitOut) 1057 emitOut.close() 1058 if poiOut: 1059 print("</pois>", file=poiOut) 1060 poiOut.close() 1061