def getReachable(net, source_id, options, useIncoming=False):
    if not net.hasEdge(source_id):
        sys.exit("'{}' is not a valid edge id".format(source_id))
    source = net.getEdge(source_id)
    if options.vclass is not None and not source.allows(options.vclass):
        sys.exit("'{}' does not allow {}".format(source_id, options.vclass))
    fringe = [source]
    found = set()
    found.add(source)
    while len(fringe) > 0:
        new_fringe = []
        for edge in fringe:
            cands = edge.getIncoming() if useIncoming else edge.getOutgoing()
            for reachable in cands:
                if options.vclass is None or reachable.allows(options.vclass):
                    if not reachable in found:
                        found.add(reachable)
                        new_fringe.append(reachable)
        fringe = new_fringe

    if useIncoming:
        print("{} of {} edges can reach edge '{}':".format(len(found), len(net.getEdges()), source_id))
    else:
        print("{} of {} edges are reachable from edge '{}':".format(len(found), len(net.getEdges()), source_id))

    ids = sorted([e.getID() for e in found])
    if options.selection_output:
        with open(options.selection_output, 'w') as f:
            for e in ids:
                f.write("edge:{}\n".format(e))
    else:
        print(ids)

def getWeaklyConnected(net, vclass=None, ignore_connections=False):
    components = []
    edgesLeft = set(net.getEdges())
    queue = list()
    while len(edgesLeft) != 0:
        component = set()
        queue.append(edgesLeft.pop())
        while not len(queue) == 0:
            edge = queue.pop(0)
            if vclass is None or edge.allows(vclass):
                component.add(edge.getID())
                if ignore_connections:
                    for n in (edge.getFromNode().getOutgoing()
                              + edge.getFromNode().getIncoming()
                              + edge.getToNode().getOutgoing()
                              + edge.getToNode().getIncoming()):
                        if n in edgesLeft:
                            queue.append(n)
                            edgesLeft.remove(n)
                else:
                    for n in edge.getOutgoing():
                        if n in edgesLeft:
                            queue.append(n)
                            edgesLeft.remove(n)
                    for n in edge.getIncoming():
                        if n in edgesLeft:
                            queue.append(n)
                            edgesLeft.remove(n)
        if component:
            components.append(sorted(component))
    return components

def getReachable(net, source_id, options):
    if not net.hasEdge(source_id):
        sys.exit("'%s' is not a valid edge id" % source_id)
    source = net.getEdge(source_id)
    fringe = [source]
    found = set()
    found.add(source)
    while len(fringe) > 0:
        new_fringe = []
        for edge in fringe:
            for reachable in edge.getOutgoing().iterkeys():
                if not reachable in found:
                    found.add(reachable)
                    new_fringe.append(reachable)
        fringe = new_fringe

    print "%s of %s edges are reachable from edge '%s':" % (
            len(found), len(net.getEdges()), source_id)

    if options.selection_output:
        with open(options.selection_output, 'w') as f:
            for e in found:
                f.write("edge:%s\n" % e.getID())
    else:
        print [e.getID() for e in found]

def getReachable(net, source_id, options, useIncoming=False):
    if not net.hasEdge(source_id):
        sys.exit("'{}' is not a valid edge id".format(source_id))
    source = net.getEdge(source_id)
    if options.vclass is not None and not source.allows(options.vclass):
        sys.exit("'{}' does not allow {}".format(source_id, options.vclass))
    fringe = [source]
    found = set()
    found.add(source)
    while len(fringe) > 0:
        new_fringe = []
        for edge in fringe:
            if options.vclass == "pedestrian":
                cands = chain(chain(*edge.getIncoming().values()), chain(*edge.getOutgoing().values()))
            else:
                cands = chain(*(edge.getIncoming().values() if useIncoming else edge.getOutgoing().values()))
            # print("\n".join(map(str, list(cands))))
            for conn in cands:
                if options.vclass is None or (
                        conn.getFromLane().allows(options.vclass)
                        and conn.getToLane().allows(options.vclass)):
                    for reachable in [conn.getTo(), conn.getFrom()]:
                        if reachable not in found:
                            # print("added %s via %s" % (reachable, conn))
                            found.add(reachable)
                            new_fringe.append(reachable)
        fringe = new_fringe

    if useIncoming:
        print("{} of {} edges can reach edge '{}':".format(
            len(found), len(net.getEdges()), source_id))
    else:
        print("{} of {} edges are reachable from edge '{}':".format(
            len(found), len(net.getEdges()), source_id))

    ids = sorted([e.getID() for e in found])
    if options.selection_output:
        with open(options.selection_output, 'w') as f:
            for e in ids:
                f.write("edge:{}\n".format(e))
    else:
        print(ids)

def getWeaklyConnected(net):
    components = []
    edgesLeft = set(net.getEdges())
    queue = list()
    while len(edgesLeft) != 0:
        component = set()
        queue.append(edgesLeft.pop())
        while not len(queue) == 0:
            edge = queue.pop(0)
            component.add(edge.getID())
            for n in edge.getOutgoing().iterkeys():
                if n in edgesLeft:
                    queue.append(n)
                    edgesLeft.remove(n)
            for n in edge.getIncoming().iterkeys():
                if n in edgesLeft:
                    queue.append(n)
                    edgesLeft.remove(n)
        components.append(component)
    return components

def calcPaths(net, startEdgeLabel):
    for n in net.getNodes():
        n.preds = []
        n.wasUpdated = False
    for e in net.getEdges():
        e.weight = e.getLane(0).getLength()
        if options.traveltime:
            e.weight /= e.getLane(0).getSpeed()
    if startEdgeLabel:
        startVertex = net.getEdge[startEdgeLabel]._from
    else:
        startVertex = net.getNodes()[0]
    startVertex.preds.append(Predecessor(None, None, 0))
    updatedVertices = [startVertex]
    while len(updatedVertices) > 0:
        vertex = updatedVertices.pop(0)
        vertex.wasUpdated = False
        for edge in vertex.getOutgoing():
            if edge._to != startVertex and update(edge._to, edge):
                updatedVertices.append(edge._to)
    printRoutes(net, startVertex)

def getWeaklyConnected(net, vclass=None):
    components = []
    edgesLeft = set(net.getEdges())
    queue = list()
    while len(edgesLeft) != 0:
        component = set()
        queue.append(edgesLeft.pop())
        while not len(queue) == 0:
            edge = queue.pop(0)
            if vclass is None or edge.allows(vclass):
                component.add(edge.getID())
                for n in edge.getOutgoing():
                    if n in edgesLeft:
                        queue.append(n)
                        edgesLeft.remove(n)
                for n in edge.getIncoming():
                    if n in edgesLeft:
                        queue.append(n)
                        edgesLeft.remove(n)
        if component:
            components.append(component)
    return components

def main(options):
    parser = make_parser()
    isBZ2 = False
    dataDir = options.datadir
    districts = os.path.join(dataDir, options.districtfile)
    matrix = os.path.join(dataDir, options.mtxfile)
    netfile = os.path.join(dataDir, options.netfile)
    print 'generate Trip file for:', netfile

    if "bz2" in netfile:
        netfile = bz2.BZ2File(netfile)
        isBZ2 = True

    matrixSum = 0.
    tripList = []
    net = Net()
    odConnTable = {}
    vehIDtoODMap = {}

    sumolib.net.readNet(options.netfile, net=net)

    if isBZ2:
        parser.parse(StringIO.StringIO(netfile.read()))
        netfile.close()
    else:
        parser.parse(netfile)

    parser.setContentHandler(DistrictsReader(net))
    parser.parse(districts)

    matrixPshort, startVertices, endVertices, currentMatrixSum, begin, period = getMatrix(
        net, options.debug, matrix, matrixSum)[:6]

    for edge in net.getEdges():
        edge.helpacttime = 0.

    if options.debug:
        print len(net._edges), "edges read"
        print len(net._startVertices), "start vertices read"
        print len(net._endVertices), "target vertices read"
        print 'currentMatrixSum:', currentMatrixSum

    if options.getconns:
        if options.debug:
            print 'generate odConnTable'
        for start, startVertex in enumerate(startVertices):
            if startVertex._id not in odConnTable:
                odConnTable[startVertex._id] = {}

            for source in startVertex.sourceConnNodes:
                targets = net.getTargets()
                D, P = dijkstraPlain(source, targets)
                for end, endVertex in enumerate(endVertices):
                    if startVertex._id != endVertex._id and matrixPshort[start][end] > 0.:
                        if endVertex._id not in odConnTable[startVertex._id]:
                            odConnTable[startVertex._id][endVertex._id] = []
                        net.checkRoute(
                            startVertex, endVertex, start, end, P, odConnTable, source, options)
    else:
        if options.debug:
            print 'import and use the given odConnTable'
        sys.path.append(options.datadir)
        from odConnTables import odConnTable

    # output trips
    if options.verbose:
        print 'output the trip file'
    vehID = 0
    subVehID = 0
    random.seed(42)
    matrixSum = 0.
    fouttrips = file(options.tripfile, 'w')
    fouttrips.write('<?xml version="1.0"?>\n')
    print >> fouttrips, """<!-- generated on %s by $Id: generateTripsXml.py 18096 2015-03-17 09:50:59Z behrisch $ -->
    """ % datetime.datetime.now()
    fouttrips.write("<tripdefs>\n")

    if options.demandscale != 1.:
        print 'demand scale %s is used.' % options.demandscale
        for start in range(len(startVertices)):
            for end in range(len(endVertices)):
                matrixPshort[start][end] *= options.demandscale

    for start, startVertex in enumerate(startVertices):
        for end, endVertex in enumerate(endVertices):
            if startVertex._id != endVertex._id and matrixPshort[start][end] > 0.:
                counts = 0.
                if options.odestimation:
                    if matrixPshort[start][end] < 1.:
                        counts, vehID, tripList, vehIDtoODMap = addVeh(
                            counts, vehID, begin, period, odConnTable, startVertex, endVertex, tripList, vehIDtoODMap)
                    else:
                        matrixSum += matrixPshort[start][end]
                        while (counts < float(math.ceil(matrixPshort[start][end])) and (matrixPshort[start][end] - counts) > 0.5 and float(subVehID) < matrixSum)or float(subVehID) < matrixSum:
                            counts, vehID, tripList, vehIDtoODMap = addVeh(
                                counts, vehID, begin, period, odConnTable, startVertex, endVertex, tripList, vehIDtoODMap)
                            subVehID += 1
                else:
                    matrixSum += matrixPshort[start][end]
                    while (counts < float(math.ceil(matrixPshort[start][end])) and (matrixPshort[start][end] - counts) > 0.5 and float(vehID) < matrixSum) or float(vehID) < matrixSum:
#.........这里部分代码省略.........

def main():
    # for measuring the required time for reading input files
    inputreaderstart = datetime.datetime.now()
    foutlog = file('%s_log.txt' % options.type, 'w')
    foutlog.write('The stochastic user equilibrium traffic assignment will be executed with the %s model.\n' % options.type)
    foutlog.write('All vehicular releasing times are determined randomly(uniform).\n')
  
    matrices = options.mtxpsfile.split(",")
    parser = make_parser()
    
    if options.verbose:
        print "Reading net"
    print 'net file:', options.netfile
    net = Net()
    sumolib.net.readNet(options.netfile, net=net)
    parser.setContentHandler(DistrictsReader(net))
    parser.parse(options.confile)
    if options.sigfile:
        parser.setContentHandler(ExtraSignalInformationReader(net))
        parser.parse(options.sigfile)
    foutlog.write('- Reading network: done.\n')
    foutlog.write('number of total startVertices:%s\n' % net.getstartCounts())
    foutlog.write('number of total endVertices:%s\n' % net.getendCounts())
    if options.verbose:
        print net.getfullEdgeCounts(), "edges read (internal edges included)"

    if options.curvefile:
        updateCurveTable(options.curvefile)
        
    if options.hours == 24.:
        assignHours = 16.
    else:
        assignHours = options.hours 

    for edge in net.getEdges():
        if edge._lanes:
            edge.getCapacity()
            edge.getAdjustedCapacity(net)
            edge.estcapacity *= assignHours
            edge.getConflictLink()

    if options.dijkstra == 'boost':
        net.createBoostGraph()
    if options.verbose:
        print "after link reduction:", net.getfullEdgeCounts(), "edges read"

    # calculate link travel time for all district connectors 
    getConnectionTravelTime(net._startVertices, net._endVertices)
            
    foutlog.write('- Initial calculation of link parameters : done.\n')
    # the required time for reading the network     
    timeForInput(inputreaderstart)
    
    if options.debug:
        outputNetwork(net)
        
    # initialize the map for recording the number of the assigned vehicles
    AssignedVeh = {}
    # initialize the map for recording the number of the assigned trips
    AssignedTrip = {}
    smallDemand = []
    linkChoiceMap = {}
    odPairsMap = {}
    for start, startVertex in enumerate(net._startVertices):
        AssignedVeh[startVertex]={}
        AssignedTrip[startVertex]={}
        smallDemand.append([])
        for end, endVertex in enumerate(net._endVertices):
            AssignedVeh[startVertex][endVertex] = 0
            AssignedTrip[startVertex][endVertex] = 0.
            smallDemand[-1].append(0.)
            
    # initialization
    vehID = 0
    matrixSum = 0.0
    lohse = (options.type == "lohse")
    incremental = (options.type == "incremental")
    checkKPaths = False
    
    if not incremental and options.kPaths > 1:
        checkKPaths = True
    if not incremental:
        net.initialPathSet()
 
    starttime = datetime.datetime.now()
    # initialize the file for recording the routes
    if options.odestimation:
        net.getDetectedEdges(options.outputdir)
    else:
        foutroute = open('routes.rou.xml', 'w')
        print >> foutroute, """<?xml version="1.0"?>
<!-- generated on %s by $Id: Assignment.py 11700 2012-01-10 22:20:15Z behrisch $ -->
<routes>""" % starttime
    
    for counter, matrix in enumerate(matrices):  #for counter in range (0, len(matrices)):
        # delete all vehicle information related to the last matrix for saving the disk space
        vehicles = []
        iterInterval = 0
        matrixPshort, startVertices, endVertices, CurrentMatrixSum, begintime, assignPeriod, Pshort_EffCells, matrixSum, smallDemandRatio = getMatrix(net, options.verbose, matrix, matrixSum, options.demandscale)
        options.hours = float(assignPeriod)
#.........这里部分代码省略.........

    metavar="NUM",
    default=3,
    help="calculate the shortest k paths [default: %default]",
)
optParser.add_option("-s", "--start-edge", dest="start", default="", help="start at the start vertex of this edge")
optParser.add_option(
    "-t", "--travel-time", action="store_true", dest="traveltime", help="use minimum travel time instead of length"
)
optParser.add_option(
    "-l",
    "--no-loops",
    action="store_true",
    dest="noloops",
    default=False,
    help="omit routes which travel an edge twice",
)
optParser.add_option(
    "-v", "--verbose", action="store_true", dest="verbose", default=False, help="tell me what you are doing"
)
(options, args) = optParser.parse_args()
if not options.netfile:
    optParser.print_help()
    sys.exit()
parser = make_parser()
if options.verbose:
    print "Reading net"
net = sumolib.net.readNet(options.netfile)
if options.verbose:
    print len(net.getEdges()), "edges read"
calcPaths(net, options.start)