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