python_计算重庆地铁最短路径(Floyd)和断面客流量

本文主要是介绍python_计算重庆地铁最短路径(Floyd)和断面客流量，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、摘要

本文主要讲解：使用地铁客流业务逻辑来计算重庆地铁断面客流量
主要思路：

1. 使用Floyd佛洛依德算法找到重庆地铁的最短路径；
2. 计算每个段面的客流量（算某个时间段重庆所有断面的客流量）
3. 把断面客流量加到json里面去，利用累加的方式去计算

2、数据介绍

重庆各站点间的区间长度，18年的数据，共8条线142个站点

某个时间段的OD客流量，采用矩阵的方式进行存储

3、相关技术

1、panda读取文件后的数据为Dataframe，关于Dataframe的遍历方法itertuples
2、Json数据的key，value格式，适合存储与计算断面客流量

4、完整代码

代码输出如下：

Json格式的如下：

步骤1：根据每个站点的距离计算各个站点间的最短路径

from itertools import permutations

import pandas as pd

from my_utils.read_write import writeOneCsv, writeOneJson

subway_dict = []
transfer_dict = []

src = r'D:\项目\重庆地铁断面客流量计算\\'
try:
    yearStop = pd.read_excel(src + '区间长度.xlsx', encoding='gbk')
except Exception as e:
    yearStop = pd.read_excel(src + '区间长度.xlsx', encoding='utf-8')


def getRoute():
    for feature in yearStop.itertuples(index=False):
        line = str(getattr(feature, '线路名称'))
        SStation = str(getattr(feature, 'SStation'))
        EStation = str(getattr(feature, 'EStation'))
        Length_Dow = getattr(feature, 'Length_Dow')
        start = line + '-' + SStation
        end = line + '-' + EStation
        subway_dict.append([start, end, Length_Dow])


transfer = {}


def getTransfer():
    '''SStation	EStation	Length_Dow	线路名称'''
    features = yearStop.groupby('SStation')
    for name, feature in features:
        if feature.shape[0] > 0:
            for one in feature.itertuples():
                linename = getattr(one, '线路名称')
                line_station = str(linename) + '-' + str(name)
                if name not in transfer.keys():
                    transfer[name] = []
                transfer[name].append(line_station)
    # 列举排列结果[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
    data4 = list(permutations([i for i in range(0, 4)], 2))
    for key in transfer.keys():
        data = transfer[key]
        if len(data) == 2:
            transfer_dict.append([data[1], data[0], 120])
            transfer_dict.append([data[0], data[1], 120])
        elif len(data) == 3:
            transfer_dict.append([data[1], data[0], 180])
            transfer_dict.append([data[0], data[1], 180])
            transfer_dict.append([data[0], data[2], 180])
            transfer_dict.append([data[2], data[0], 180])
            transfer_dict.append([data[1], data[2], 180])
            transfer_dict.append([data[2], data[1], 180])
        elif len(data) == 4:
            for one in data4:
                transfer_dict.append([data[one[0]], data[one[1]], 240])


# getTransfer()

'''
弗洛伊德算法（Floyd算法）
'''


class Vertex:
    def __init__(self, key):
        self.id = key
        self.connectedTo = {}

    def addNeighbor(self, nbr, weight=0):
        self.connectedTo[nbr] = weight

    def __str__(self):
        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self, nbr):
        return self.connectedTo[nbr]


class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0

    def addVertex(self, key):
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self, n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def __contains__(self, n):
        return n in self.vertList

    def addEdge(self, f, t, cost=0):
        if f not in self.vertList:
            nv = self.addVertex(f)
        if t not in self.vertList:
            nv = self.addVertex(t)
        self.vertList[f].addNeighbor(self.vertList[t], cost)

    def getVertices(self):
        return self.vertList.keys()

    def __iter__(self):
        return iter(self.vertList.values())


def Floyd(Graph, ShortestPath):
    global path

    NodeNum = len(Graph)

    lastShortestDistance = [[0 for i in range(NodeNum)] for j in range(NodeNum)]

    currentShortestDistance = [[0 for i in range(NodeNum)] for j in range(NodeNum)]

    path = [[0 for i in range(NodeNum)] for j in range(NodeNum)]
    for i in range(NodeNum):
        for j in range(NodeNum):
            path[i][j] = j

    for i in range(NodeNum):
        for j in range(NodeNum):
            lastShortestDistance[i][j] = Graph[i][j]
            currentShortestDistance[i][j] = lastShortestDistance[i][j]

    for k in range(NodeNum):
        for i in range(NodeNum):
            for j in range(NodeNum):
                if lastShortestDistance[i][j] > lastShortestDistance[i][k] + lastShortestDistance[k][j]:
                    currentShortestDistance[i][j] = lastShortestDistance[i][k] + lastShortestDistance[k][j]
                    path[i][j] = path[i][k]
            lastShortestDistance = currentShortestDistance

    for i in range(NodeNum):
        for j in range(NodeNum):
            # if i==j:
            #     ShortestPath[i][j]=0
            # else:
            ShortestPath[i][j] = currentShortestDistance[i][j]

    print("path is: ", path)
    print("shortestPath is: ", ShortestPath)
    # print(currentShortestDistance)
    return None


def printPath(i, j, shortestPath, path):
    print(zhandian[i] + "----" + zhandian[j] + "\n最短时间:" + str(shortestPath[i][j]) + "s\n路径:\n" + zhandian[i])
    temp = path[i][j]
    odName = zhandian[i] + "_" + zhandian[j]
    JsonData = {}
    routeSplitData = [zhandian[i]]
    while (temp != j):
        routeSplitData.append(zhandian[temp])
        print("-->" + zhandian[temp])
        temp = path[temp][j]
    routeSplitData.append(zhandian[j])
    JsonData[odName] = routeSplitData
    mainJson.append(JsonData)
    print("-->" + zhandian[j])


'''SStation	EStation	Length_Dow	线路名称'''


def splitTime(i, j, shortestPath, path):
    temp = path[i][j]
    routeSplitData = [zhandian[i]]
    time = shortestPath[i][j]
    while (temp != j):
        routeSplitData.append(zhandian[temp])
        temp = path[temp][j]
    routeSplitData.append(zhandian[j])
    start = zhandian[i]
    SStation = routeSplitData[len(routeSplitData) - 2].split('-')[1]
    EStation = zhandian[j].split('-')[1]
    if SStation != EStation:
        save = [start, SStation, EStation, time]
        print(save)
        writeOneCsv(save, src+r'all.csv')


def writeOneCsv(relate_record, src):
    with open(src, 'a', newline='\n') as csvFile:
        writer = csv.writer(csvFile)
        writer.writerow(relate_record)

#   写Json文件,一个数据一个文件
def writeOneJson(relate_record, src):
    Json_str = json.dumps(relate_record, ensure_ascii=False)
    with open(src, 'w', encoding='utf-8') as Json_file:
        Json_file.write(Json_str)
    Json_file.close()

if 
__name__ == "__main__":
    mainJson = []
    getRoute()
    getTransfer()
    g = Graph()
    # vel = 10  # 地铁的速度 m/s
    vel = 10  # 地铁的速度 m/s
    for x in subway_dict:
        g.addEdge(x[0], x[1], int(float(x[2]) / vel))  # 由距离得到时间
        g.addEdge(x[1], x[0], int(float(x[2]) / vel))  # 双向都有
    for x in transfer_dict:
        g.addEdge(x[0], x[1], int(float(x[2])))  # 换站给的直接就是时间
    print(len(g.getVertices()))  # 打印图中顶点数
    print(g.getVertices())  # 打印图中所有的顶()点
    zhandian = []
    for i in g.getVertices():
        zhandian.append(i)
    zhandian = tuple(list(zhandian))
    x = float('inf')
    matrix = [[x for i in range(338)] for i in range(338)]
    for i in range(338):
        matrix[i][i] = 0
    for v in g:  # 对图中的每一个顶点，获取与它有连接关系的顶点
        for w in v.getConnections():
            time = v.getWeight(w)
            matrix[zhandian.index(v.getId())][zhandian.index(w.getId())] = time
    graph = matrix
    nodeNum = len(graph)
    shortestPath = [[0 for i in range(nodeNum)] for j in range(nodeNum)]
    print("计算时间比较长，请耐心等待几分钟！")
    Floyd(graph, shortestPath)
    allStation = []
    '''SStation	EStation	Length_Dow	线路名称'''
    for one_s in yearStop.itertuples():
        line = str(getattr(one_s, '线路名称'))
        start = line + '-' + str(getattr(one_s, 'SStation'))
        end = line + '-' + str(getattr(one_s, 'EStation'))
        if start not in allStation:
            allStation.append(start)
        if end not in allStation:
            allStation.append(end)
    for start in allStation:
        for end in allStation:
            if start != end:
                s = zhandian.index(start)
                e = zhandian.index(end)
                printPath(s, e, shortestPath, path)
                # splitTime(s, e, shortestPath, path)
    writeOneJson(mainJson, src + '最短路径.json')

主运行程序入口

import pandas as pd

from my_utils.read_write import writeOneJson, readJson, writeOneCsv

'''
此文件用于计算重庆地铁线路断面客流量
计算步骤：1、找到最短路径；
2、计算每个段面的客流量（算0这个时间段所有深圳所有断面的客流量）
'''
src = r'D:\项目\重庆地铁断面客流量计算\\'
try:
    od_people = pd.read_excel(src + 'OD客流量.xlsx', encoding='gbk')
except Exception as e:
    od_people = pd.read_excel(src + 'OD客流量.xlsx', encoding='utf-8')

try:
    yearStop = pd.read_excel(src + '区间长度.xlsx', encoding='gbk')
except Exception as e:
    yearStop = pd.read_excel(src + '区间长度.xlsx', encoding='utf-8')
all_split = []
for one_s in yearStop.itertuples():
    line = str(getattr(one_s, '线路名称'))
    start = line + '-' + str(getattr(one_s, 'SStation'))
    end = line + '-' + str(getattr(one_s, 'EStation'))
    all_split.append(start + '_' + end)
    all_split.append(end + '_' + start)


def add_count(split, od_count, routeSplitJson):
    if split not in routeSplitJson.keys():
        routeSplitJson[split] = 0
    # 某个断面某个时间加入od的数量
    routeSplitJson[split] = routeSplitJson[split] + od_count

def readJson(filepath):
    try:
        with open(filepath, 'r', encoding='GBK') as file_open:
            data = json.load(file_open)
        file_open.close()
        return data
    except:
        try:
            with open(filepath, 'r', encoding='utf-8') as file_open:
                data = json.load(file_open)
                file_open.close()
                return data
        except:
            with open(filepath, 'r', encoding="unicode_escape") as file_open:
                data = json.load(file_open)
            file_open.close()
            return data

def routeSplit(df, routeSplitJson):
    minWays = readJson(src + '最短路径.json')
    min_ways = {}
    for one in minWays:
        keys = one.keys()
        for i in keys:
            if i not in min_ways.keys():
                min_ways[i] = {}
                # 某个断面某个时间加入od的数量
            min_ways[i] = one[i]
    allStation = []
    for one_s in yearStop.itertuples():
        line = str(getattr(one_s, '线路名称'))
        start = line + '-' + str(getattr(one_s, 'SStation'))
        end = line + '-' + str(getattr(one_s, 'EStation'))
        if start not in allStation:
            allStation.append(start)
        if end not in allStation:
            allStation.append(end)
    # o_station,d_station,tw,od
    for row in df.itertuples(index=False):
        line = str(getattr(row, '线路'))
        start = line + '-' + str(getattr(row, '车站编号'))
        for n in range(len(allStation)):
            if start != allStation[n]:
                od_count = row[n + 2]
                od_name = start + '_' + allStation[n]
                # 获取到最短路径的数据
                minStations = min_ways[od_name]
                for m in range(0, len(minStations)):
                    if m + 1 < len(minStations):
                        split = minStations[m] + '_' + minStations[m + 1]
                        if split in all_split:
                            # 把断面客流量加到json里面去
                            add_count(split, od_count, routeSplitJson)


def final():
    routeSplitJson = {}
    routeSplit(od_people, routeSplitJson)
    writeOneJson(routeSplitJson, src + '重庆断面客流量.json')


def deal_json():
    data = readJson(src + '重庆断面客流量.json')
    # 上行客流量,断面,下行客流量
    alr = []
    one = []
    for key in data.keys():
        if key not in alr:
            split_data = key.split('_')
            add = split_data[0].split('-')[1] + '-' + split_data[1].split('-')[1]
            down_key = split_data[1] + '_' + split_data[0]
            alr.append(down_key)
            alr.append(key)
            if down_key in data.keys():
                writeOneCsv([data[key], add, data[down_key]], src + '重庆地铁断面客流量.csv')
            else:
                writeOneCsv([data[key], add, 0], src + '重庆地铁断面客流量.csv')


if __name__ == '__main__':
    deal_json()
    final()

read_write文件在我的下载里有，请自行搜索
如需数据示例请私聊我，有偿

5、参考链接

60行python代码_计算深圳地铁断面客流量

python_pandas_计算深圳地铁线路断面客流量

这篇关于python_计算重庆地铁最短路径(Floyd)和断面客流量的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！