中国邮递员可视化设计

中国邮递员问题背景

中国邮递员问题是邮递员在某一地区的信件投递路程问题。邮递员每天从邮局出发，走遍该地区所有街道再返回邮局，问题是他应如何安排送信的路线可以使所走的总路程最短。这个问题由中国学者管梅谷在1960年首先提出，并给出了解法——“奇偶点图上作业法”，被国际上统称为“中国邮递员问题”。用图论的语言描述，给定一个连通图G，每边e有非负权)，要求一条回路经过每条边至少一次，且满足总权最小。

成品展示及功能介绍

左边一列有三个按钮，它们的功能依次是 初始化地图、下一步、上一步。

右边的大画布就是 地图的显示界面，地图的生成是根据用户在算法程序中输入的地图边信息构成的，地图中的每个结点的 相对位置是固定的 ，但是 **绝对位置是随机的 **，用户可以多按几次初始化地图按钮，生成他们想要的地图样式。

每当按下一步按钮，邮递员就会依照算法程序得到的最终路径来前进一步，上一步按钮顾名思义就是返回上一次邮递员的位置。

邮递员的前进是通过结点和边的颜色变化实现的，邮局（起点）为浅绿色、未走过的结点为浅蓝色、未走过的边为黑色，走过一次的结点和边都为金色，走过多次的结点和边都为紫色，经过邮局其颜色会变为红色，到达终点（回到邮局）其颜色又会变为浅绿色，边的权值为黑色方框中的白色字体。

走了一半：

到达终点：

不同的地图：

设计环境

python 3.9

使用的库主要有：

PyQt5、matplotlib、networkx、read_csv

设计思路

用 read_csv库读取由 C#编写的算法程序生成的保存有中国邮递员街区里的边的信息和 最短路径所经过的结点信息 的 csv文件，用 network库来构建无向图即 生成街区地图，邮递员每走过一条街道，这条 街道和其末端结点的颜色 就会被更改，以此来区分经过的结点和未经过的结点，并且每走一步会 判断这条街道和其末端结点是否被走过 ，被走过多次的街道和结点会用其他的颜色来标记它，用 matolotlib库将街区地图画在画布上，最后将承载街区地图的画布安置在 PyQt5 设计的 UI界面 上，并且添加 按钮控制 街区地图的生成、上一步、下一步。

具体实现

读取csv文件

代码实现还是很简单的，网上看一两个例子就能模仿出来，没啥好说的

import csv
# 读取csv至列表
def read_route():
    csvFile = open("graph.csv", "r")
    reader = csv.reader(csvFile)
    # 建立空列表
    result = []
    for item in reader:
        #print(item)
        result.append((item[0], item[1], item[2]))
    csvFile.close()
    #print(result)
    return result

network构造无向图（重点）

初始化

定义一个初始的无向图，然后给它添加边（边的信息是读取上面的csv得到的），边的属性包括它的权值 - weight，起始结点和末端结点，颜色 - color（初始化时所有的边默认为黑色，表示未走过）

import networkx as nx
G = nx.Graph()  # 定义初始无向图
G.add_weighted_edges_from(init_edgelist, color='black')  # 添加边

添加属性

为了让之后结点颜色发生变化，我们要给结点添加一个 color 属性，并且我们之后还得利用 nx.layout.spring_layout 函数来生成结点的坐标，这个函数是通过 Fruchterman-Reingold 力导向算法 来计算结点位置的，简单的说就是，边的吸引力属性值越大，这条边两端的结点离得越近，即边越短，所以我们通过将边的 weight（权值） 取倒数的方法构建 边的吸引力属性，0.5是由测试得到的效果较好的值。

#添加结点的颜色属性
      for m in self.nodelist:
          self.G.nodes[m].update({'color': 'lightskyblue'})  # 初始状态
      #添加边的吸引力属性，用于确定坐标
      for k in self.edgelist:
          self.G.edges[k].update({'attraction': str(0.5/int(nx.get_edge_attributes(self.G, 'weight')[k]))})
      # 起始点颜色属性
      self.G.nodes[self.start].update({'color': 'lightgreen'})

获取结点的坐标

这个布局函数是我们构建图的关键，我们需要了解它的参数

self.pos = nx.spring_layout(self.G, weight='attraction', iterations=pow(node_num, 2))

官方文档：

这里我只介绍几个关键参数：

weight :

它的值必须是边的属性，布局函数会依照它的值调用 Fruchterman-Reingold 力导向算法 定位节点生成所有点的坐标，我们填入的属性可以被称为 边两端结点吸引力，即一个边的该属性值越大，它两端的结点离得越近，边越短。所以我之前在给边添加属性的时候，添加了一个 ‘attraction’ 属性，它就是用于此处，它的值是边权值属性的倒数，即边的权值越大，边两端结点的吸引力越小，边越长。

力引导布局（Force-directed Layout）

力引导布局最早由Peter Eades在1984年的“启发式画图算法”一文中提出，目的是减少布局中边的交叉，尽量保持边的长度一致。此方法借用弹簧模型模拟布局过程：用弹簧模拟两个点之间的关系，受到弹力的作用后，过近的点会被弹开而过远的点被拉近；通过不断的迭代，整个布局达到动态平衡，趋于稳定。其后，“力引导”的概念被提出，演化成 力引导布局算法FR（Fruchterman-Reingold算法）——丰富两点之间的物理模型，加入点之间的静电力，通过计算系统的总能量并使得能量最小化，从而达到布局的目的。这种改进的能量模型，可看成弹簧模型的一般化。

无论是弹簧模型还是能量模型，其算法的本质是要接一个能量优化问题，区别在于优化函数的组成不同。优化对象包括引力和斥力部分，不同算法对引力和斥力的表达方式不同。

itrations:

它的值是一个int类型数值，表示 Fruchterman-Reingold算法的 最大迭代次数，理论上这个值越大，图上点的分布越符合预期，但是过大的值又会影响运行效率。我给它设定的值是图中结点个数的平方。

seed

它的值是一个int类型数值，默认为None，Fruchterman-Reingold算法会根据它的值生成不同的结点布局，如果这个值被固定了，那么生成的图将是唯一的。为了带有随机性，我没有设置它，保持默认值。

将图画出来

这一步就是设定一些字体大小，结点大小，用 nx.draw 画出所有结点的初始状态，然后再用nx.draw_networkx_nodes 单独画起点结点，再用 nx.draw_networkx_labels 和 nx.draw_networkx_edge_labels 画出结点的标签——结点名称或边的权值，最后将图画在画布上。

# 画出无向图
nx.draw(self.G, self.pos, font_size=16, with_labels=False, width=5, node_color='lightskyblue', edge_color='black', node_size=1200, edgecolors='black', linewidths=2.0)  # 画所有结点和边
nx.draw_networkx_nodes(self.G, self.pos, nodelist=self.start, node_color=nx.get_node_attributes(self.G, 'color')[self.start], node_size=1200, edgecolors='black', linewidths=2.0)  # 画起点结点
nx.draw_networkx_labels(self.G, self.pos, font_size=30, font_family="sans-serif") # 画结点的标签-名字
nx.draw_networkx_edge_labels(self.G, self.pos_attrs, edge_labels=self.edge_weight, font_size=26, font_color='white', bbox=dict(fc="#222629", ec="black", boxstyle="round", lw=1)) # 画边的标签-权值

# 在画布上绘图
self.figure.set_facecolor("mintcream") # 设定背景颜色
self.canvas.draw_idle()	 	# 在画布是作画
self.canvas.flush_events() # 刷新画布

上一步与下一步的控制

这里我定义了一个 全局变量i 来记录邮递员在走最终路径时走到了第几个结点，即i作为最终路径经过的结点列表的下标，按下一步按钮，变量i的值加一；按上一步减一。

邮递员每走一步或者退一步，都要判断当前点是否走过，即利用结点的颜色属性和边的颜色属性，如果满足条件就更新当前结点的颜色属性以及边的颜色属性，然后将其画到画布上。

这里就是需要注意一下获取具体某一条边的颜色属性时，nx.get_edge_attributes(self.G, ‘color’)[(visited_node[m - 1], visited_node[m])] 后面 [] 里的值填入当前边起始结点和末端结点组成的元组时，有时候会找不到这条边的属性，发生报错。这是因为无向图的一条边有两种表现形式，但获取边的属性值时只能使用添加边时的那种表现形式，比如边AB,z在无向图中可以写成(‘A’,’B’)，也可以写成 (‘B’,’A’),但是添加边时用的是(‘A’,’B’)，那个查询边AB属性时，填入(‘B’,’A’)，就会报错。所以我这里使用了 try…except…语句。

try:
    nx.draw_networkx_edges(self.G, self.pos, edgelist=[(visited_node[m - 1], visited_node[m])],
                           edge_color=nx.get_edge_attributes(self.G, 'color')[
                               (visited_node[m - 1], visited_node[m])], width=5)
except:
    nx.draw_networkx_edges(self.G, self.pos, edgelist=[(visited_node[m - 1], visited_node[m])],
                           edge_color=nx.get_edge_attributes(self.G, 'color')[
                               (visited_node[m], visited_node[m - 1])], width=5)

PyQT5设计UI

很常见的设计，这里就直接贴代码了，下面有一个 eval()函数还是挺有意思的

NumButtons = ['init_graph', 'next_step', 'previous_step']

def initUI(self):

    self.setGeometry(200, 200, 1600, 1000)
    self.center()
    self.setWindowTitle('中国邮递员算法演示')

    grid = QGridLayout()
    self.setLayout(grid)
    self.createVerticalGroupBox()

    buttonLayout = QVBoxLayout()
    buttonLayout.addWidget(self.verticalGroupBox)

    self.figure = plt.figure(facecolor='mintcream', edgecolor='black')
    # self.figure = plt.figure(facecolor='#222629', edgecolor='black')
    self.canvas = FigureCanvas(self.figure)
    grid.addWidget(self.canvas, 0, 1, 9, 9)
    grid.addLayout(buttonLayout, 0, 0, 1, 1)
    self.show()
    
# 创建按钮
def createVerticalGroupBox(self):
    self.verticalGroupBox = QGroupBox()

    layout = QVBoxLayout()
    for i in self.NumButtons:
    button = QPushButton(i)
    button.setFixedSize(200, 50)
    button.setObjectName(i)
    layout.addWidget(button)
    layout.setSpacing(20)
    self.verticalGroupBox.setLayout(layout)
    button.clicked.connect(self.submitCommand)
    
# 按钮控制事件链接
def submitCommand(self):
    eval('self.' + str(self.sender().objectName()) + '()')

UI美化

这里仅仅简单地调用了别人写好的皮肤，直接加载到UI上，有了它UI高大上了好多

from qt_material import apply_stylesheet
apply_stylesheet(app, theme='dark_teal.xml')    # 导入QSS皮肤

总结

这次数据结构大作业我是负责UI设计部分的，一共花了5天时间，中间摸鱼了好一段时间，写的时间还是挺长的。一开始对实现这种图的可视化还是一概不知的，到处找资料，找了一天了解到了python的networkx库专门用于构建和操作复杂的图结构，然后就想去b站找视频学习一下，但是b站关于networkx的视频几乎没有，索性上油管上看着机翻字幕学了一会，再加上看各个博客关于networkx用法，自己再复制别人的代码调调，感觉有点认识后，直接照着官方文档写了两天，写出了充满bug的demo，最后就不断优化不断删删改改。

总的来说，这几天的生活还是很充实的，学到了挺多东西的，不仅挑战了自己，锻炼了python基本功，还见识了很多有意思的东西。但是也有一些遗憾，有几个想实现的东西没有实现，有一些想尝试的东西没有时间去尝试，希望下次再遇到这种做项目的挑战的时候，自己能做的更好。