在Python中使用NetworkX进行图形优化

本文概述

• 激励图优化
• 图形介绍
• 载入资料
• 创建图
• 检查图
• 可视化
• CPP算法概述
• 假设与简化
• CPP步骤1：查找奇数度的节点
• CPP步骤2：查找最小距离对
• CPP步骤3：计算欧拉回路
• CPP解决方案
• 可视化CPP解决方案
• 下一步
• 参考文献

通过本教程, 你将解决图论中一个既定的问题, 称为中国邮递员问题。该算法的某些组件虽然在概念上很简单, 但在计算上却很严格。但是, 对于本教程, 只需要具备一些Python的先验知识即可：不需要严格的数学, 计算机科学或图论背景。

本教程将首先介绍图形的基本构造块(节点, 边, 路径等), 并使用Python中的NetworkX库解决实际图形(状态公园的足迹网络)上的问题。你将专注于核心概念和实现。对于感兴趣的读者, 提供了有关优化胆量的进一步阅读。

• 激励图优化
  • 问题
  • 个人动机
• 图形介绍
  • 引入NetworkX
  • 安装套件
• 载入资料
• 创建图
• 检查图
• 可视化图形
• 解决CPP
  • CPP算法概述
  • 假设与简化
  • CPP步骤1：查找奇数度的节点
  • CPP步骤2：查找最小距离对
  • CPP步骤3：计算欧拉回路
  • 计算CPP解决方案
  • 可视化CPP解决方案
• 下一步
• 参考文献

激励图优化

问题

你可能已经听说过”旅行推销员问题”, 它相当于找到连接一组节点(例如城市)的最短路线(例如道路)。尽管鲜为人知, 但中国邮递员问题(CPP)也称为路线检查或弧形布线问题, 非常相似。 CPP的目标是找到至少一次覆盖图形上所有链接(道路)的最短路径。如果可以做到, 而不必在同一条道路上加倍两次, 那就太好了；那是理想的情况, 问题很简单。但是, 如果必须多次穿越某些道路, 则需要进行一些数学运算才能找到最短的路线, 该路线至少在每条道路上击中一次, 且总行驶里程最低。

个人动机

(以下为个人说明：俗气, 厚脸皮和100％对于在Python中学习图优化不是必需的)

我有一个解决这个问题的真实应用程序：达到巨人马拉松运动员的等级。

什么是巨人大师？巨人大师(一头犬或人类)在他们的一生中都远足了Hamden CT(我家乡沃灵福德的邻居)的沉睡巨人州立公园的每条小路。马拉松大师(Giantmaster Marathoner)是一天内远足所有这些小径的人。

感谢沉睡的巨型公园协会(Sleeping Giant Park Association)的严格记录, 可以在此处找到巨人大师的完整花名册和他们的巨人大师水平。我必须承认, 这激发了我相当多的动力来启动这个副项目, 并在那里奔跑。当我本人在2006年冬季获得”巨人大师”身份时, 我是”沉睡的巨人小队”的一名新兴志愿者(很高兴看到SG档案中的记录), 此后又出现了新的挑战。尽管12个月和4季的Giantmaster类别令人印象深刻且引人入胜, 但他们还需要从我目前的住所(DC)到我的成年住所(CT)的旅行要比我能合理管理的更多…而且他们没有对于图优化很有趣, 所以它是巨人马拉松！

作为其他参考, 下面提供了沉睡的巨人步道地图：

图形介绍

关于图的好处是, 概念和术语通常是直观的。尽管如此, 这里还是一些基本的术语：

图是映射对象之间关系的结构。在本教程中, 将对象称为节点, 并将它们之间的连接称为边。请注意, 边和节点通常用几个名称来指, 它们通常意味着完全相同的东西：

node == vertex == point
edge == arc == link

起始图是无向的。也就是说, 你的边缘没有方向：它们是双向的。例如：A <-> B == B <-> A。

相比之下, 你可能创建的用于指定远足每条路径的最短路径的图形可以是有向图, 其中边的顺序和方向很重要。例如：A —> B！= B —> A。

该图也是边缘加权图, 其中每对相邻节点之间的距离(以英里为单位)表示边缘的权重。这被处理为名为”距离”的边缘属性。

度是指入射到(触摸)节点的边的数量。当此数字为奇数时, 节点称为奇数度节点；当偶数时, 节点称为奇数度节点。

解决该CPP问题的方法将是进行欧拉巡回：一个图形, 其中一个循环可以从起始节点返回到自身(无需回溯), 而该循环恰好通过每个边缘一次。欧拉之旅也有几个名字：

Eulerian tour == Eulerian circuit == Eulerian cycle

匹配是边的子集, 其中没有节点出现一次以上。最小权重匹配找到具有最低可能的总边缘权重的匹配。

NetworkX：图形操作和分析

NetworkX是用于处理和分析图形的最受欢迎的Python软件包。几个软件包提供了相同的基本图形操作级别, 特别是igraph, 它也具有R和C ++的绑定。但是, 我发现NetworkX具有解决CPP所需的最强大的图形算法。

安装套件

如果你已经用Python完成了任何类型的数据分析或使用了Anaconda发行版, 那么我猜你可能已经有了pandas和matplotlib。但是, 你可能没有networkx。这些应该是你在本教程中需要运行的Python标准库之外的唯一依赖项。它们很容易通过pip安装：

pip install pandas
pip install networkx
pip install matplotlib

这些应该是你现在需要的所有软件包。在最后导入imageio和numpy, 以创建CPP解决方案的GIF动画。动画嵌入在这篇文章中, 因此这些软件包是可选的。

import itertools
import copy
import networkx as nx
import pandas as pd
import matplotlib.pyplot as plt

载入资料

边列表

边列表是用于创建图形的简单数据结构。每行代表具有某些边缘属性的图形的单个边缘。

• node1＆node2：连接的节点的名称。
• Trail：边缘属性, 指示每个边缘的路径的缩写名称。例如：rs =红场
• distance：边缘属性, 指示步长(以英里为单位)。
• color：用于绘制的轨迹颜色。
• 估计：边缘属性, 指示由于未提供某些距离, 因此是否根据眼球跟踪图估计了边缘距离(1 =是, 0 =否)。仅供参考；它不用于分析。

# Grab edge list data hosted on Gist
edgelist = pd.read_csv('https://gist.githubusercontent.com/brooksandrew/e570c38bcc72a8d102422f2af836513b/raw/89c76b2563dbc0e88384719a35cba0dfc04cd522/edgelist_sleeping_giant.csv')

# Preview edgelist
edgelist.head(10)

节点清单

提供边缘列表时, 在networkx和其他图形库中, 节点列表通常是可选的, 因为在边缘列表的前两列中提供了节点名称。但是, 在这种情况下, 我们要添加一些节点属性：节点的X, Y坐标(轨迹交叉点), 以便你可以使用与轨迹图相同的布局来绘制图形。

我花了一个下午用GIMP跟踪图像来手动注释这些：

• id：边缘列表中与node1和node2对应的节点的名称。
• X：节点相对于左上角的水平位置/坐标。
• 节点相对于左上角的Y垂直位置/坐标。

关于生成节点和边缘列表的注意事项

创建节点名称也需要一些手动工作。每个节点代表两个或更多路径的交集。在可能的情况下, 节点由Trail1_trail2命名, 其中Trail1以字母顺序在Trail2之前。

当相同的路径不止一次相交时, 事情变得更加困难。例如, 橙色和白色小径。在这些情况下, 我在节点名称后附加了_2或_3。例如, 对于橙色和白色的两个不同交集, 你有两个不同的节点名称：o_w和o_w_2。

这需要大量的反复试验, 并将X, Y坐标生成的图与真实的轨迹图进行比较。

# Grab node list data hosted on Gist
nodelist = pd.read_csv('https://gist.githubusercontent.com/brooksandrew/f989e10af17fb4c85b11409fea47895b/raw/a3a8da0fa5b094f1ca9d82e1642b384889ae16e8/nodelist_sleeping_giant.csv')

# Preview nodelist
nodelist.head(5)

创建图

现在, 你使用边缘列表和节点列表在networkx中创建图形对象。

# Create empty graph
g = nx.Graph()

循环浏览边列表的行, 并将每个边及其对应的属性添加到图g。

# Add edges and edge attributes
for i, elrow in edgelist.iterrows():
    g.add_edge(elrow[0], elrow[1], attr_dict=elrow[2:].to_dict())

为了说明这里发生的情况, 让我们从添加到图形g的边缘列表的最后一行中打印值：

# Edge list example
print(elrow[0]) # node1
print(elrow[1]) # node2
print(elrow[2:].to_dict()) # edge attribute dict

o_gy2
y_gy2
{'color': 'yellowgreen', 'estimate': 0, 'trail': 'gy2', 'distance': 0.12}

同样, 你可以循环浏览节点列表中的行并添加这些节点属性。

# Add node attributes
for i, nlrow in nodelist.iterrows():
    g.node[nlrow['id']] = nlrow[1:].to_dict()

这是节点列表最后一行的示例：

# Node list example
print(nlrow)

id    y_rt
X      977
Y     1666
Name: 76, dtype: object

检查图

边缘

图形边缘由长度为3的元组列表表示。前两个元素是由边缘链接的节点名称。第三是边缘属性字典。

# Preview first 5 edges
g.edges(data=True)[0:5]

[('rs_end_south', 'y_rs', {'color': 'red', 'distance': 0.39, 'estimate': 0, 'trail': 'rs'}), ('w_gy2', 'park_east', {'color': 'gray', 'distance': 0.12, 'estimate': 0, 'trail': 'w'}), ('w_gy2', 'g_gy2', {'color': 'yellowgreen', 'distance': 0.05, 'estimate': 0, 'trail': 'gy2'}), ('w_gy2', 'b_w', {'color': 'gray', 'distance': 0.42, 'estimate': 0, 'trail': 'w'}), ('w_gy2', 'b_gy2', {'color': 'yellowgreen', 'distance': 0.03, 'estimate': 1, 'trail': 'gy2'})]

节点数

同样, 你的节点由长度为2的元组列表表示。第​​一个元素是节点ID, 其后是节点属性字典。

# Preview first 10 nodes
g.nodes(data=True)[0:10]

[('rs_end_south', {'X': 1865, 'Y': 1598}), ('w_gy2', {'X': 2000, 'Y': 954}), ('rd_end_south_dupe', {'X': 273, 'Y': 1869}), ('w_gy1', {'X': 1184, 'Y': 1445}), ('g_rt', {'X': 908, 'Y': 1378}), ('v_rd', {'X': 258, 'Y': 1684}), ('g_rs', {'X': 1676, 'Y': 775}), ('rc_end_north', {'X': 867, 'Y': 618}), ('v_end_east', {'X': 2131, 'Y': 921}), ('rh_end_south', {'X': 721, 'Y': 1925})]

摘要统计

在可视化图形之前, 请打印一些摘要统计信息。

print('# of edges: {}'.format(g.number_of_edges()))
print('# of nodes: {}'.format(g.number_of_nodes()))

# of edges: 123
# of nodes: 77

可视化

操纵颜色和布局

位置：首先, 你需要将图形中的节点位置操作成字典。这将允许你使用与实际轨迹图相同的布局来重新创建图形。否定Y即可将Y轴原点从左上角转换为左下角。

# Define node positions data structure (dict) for plotting
node_positions = {node[0]: (node[1]['X'], -node[1]['Y']) for node in g.nodes(data=True)}

# Preview of node_positions with a bit of hack (there is no head/slice method for dictionaries).
dict(list(node_positions.items())[0:5])

{'b_rd': (268, -1744), 'g_rt': (908, -1378), 'o_gy1': (1130, -1297), 'rh_end_tt_2': (550, -1608), 'rs_end_south': (1865, -1598)}

颜色：现在, 你可以将图形中的边缘颜色处理到一个简单的列表中, 以便可以通过其颜色可视化轨迹。

# Define data structure (list) of edge colors for plotting
edge_colors = [e[2]['color'] for e in g.edges(data=True)]

# Preview first 10
edge_colors[0:10]

['red', 'gray', 'yellowgreen', 'gray', 'yellowgreen', 'blue', 'black', 'yellowgreen', 'gray', 'gray']

情节

现在, 你可以绘制一个与”沉睡的巨人”步道图很好地对齐的图：

plt.figure(figsize=(8, 6))
nx.draw(g, pos=node_positions, edge_color=edge_colors, node_size=10, node_color='black')
plt.title('Graph Representation of Sleeping Giant Trail Map', size=15)
plt.show()

这种图形表示形式显然不能捕获所有轨迹的弯曲和曲线, 但是不必担心：这些都可以在用于计算的边距属性中准确捕获。视觉效果确实捕捉了乌鸦飞行时节点之间的距离(小路口), 这似乎是一个不错的近似值。

CPP算法概述

好, 现在你已经定义了一些术语并创建了图形, 如何找到通过它的最短路径？

从概念上讲, 解决中国邮递员问题非常简单：

1. 查找所有奇数度的节点(非常容易)。 (找到所有与该路口相交的路口数量为奇数的路口)
2. 向图中添加边, 以使奇数度的所有节点均变为偶数。这些添加的边必须是原始图的重复边(我们将假定对此问题不设任何限制)。添加的边集应为可能的最小距离之和(精确地说是hard … np-hard)。 (用更简单的术语来说, 将击中每条路径的路线上的双重支持量减至最少)
3. 在给定起点的情况下, 在增强数据集上找到欧拉游记(相当容易)。 (一旦我们知道我们将对哪些路径进行双重支持, 请实际计算起点到终点的路线)

假设与简化

尽管通过放宽以下假设可以生成更短, 更精确的路径, 但这将增加复杂度, 超出本教程的重点CPP。

假设1：仅必需的路径

从上面的步道地图可以看到, 公园边界上的道路可以用来连接步道, 特别是红色步道。还有一些踪迹(马蹄形和未标记的火焰), 对于Giantmaster日志而言并不是必需的, 但对于防止冗长的双重后盾很有帮助。包含可选路径实际上是CPP的既定变体, 称为农村邮递员问题。在本教程中, 我们将忽略可选的路径, 而仅关注必需的路径。

假设2：上坡==下坡

CPP假定无论沿着哪个方向行走, 走一条小路的成本都等于其距离。但是, 其中一些步道颇为丘陵, 步行而不是步行需要更多的能量。可以将有向图上结合了距离和高程变化的某些度量标准合并到CPP的扩展中, 该扩展称为Windy Postman问题。

假设3：没有平行边(后跟)

在可能的情况下, 包含平行边(连接相同两个节点的多条路径)会增加计算的复杂性。幸运的是, 在此仅发生两次(蓝色<=>红色菱形和蓝色<=>塔径)。这可以通过对边缘列表的一些破解来解决：_dupe后缀包含重复的节点, 以捕获每条路径, 同时保持边缘的唯一性。如果你想在自己的具有许多平行边的图形上求解CPP, 我在postman_problems包中编写的CPP实现将以更优雅的方式稳健地处理平行边。

CPP步骤1：查找奇数度的节点

这是非常简单的计数计算。你会看到76个节点中的36个具有奇数度。这些主要是死路(1度)和3条路的交叉点。有几个5级节点。

# Calculate list of nodes with odd degree
nodes_odd_degree = [v for v, d in g.degree_iter() if d % 2 == 1]

# Preview
nodes_odd_degree[0:5]

['rs_end_south', 'rc_end_north', 'v_end_east', 'rh_end_south', 'b_end_east']

# Counts
print('Number of nodes of odd degree: {}'.format(len(nodes_odd_degree)))
print('Number of total nodes: {}'.format(len(g.nodes())))

Number of nodes of odd degree: 36
Number of total nodes: 77

CPP步骤2：查找最小距离对

这确实是问题的根源。你将其分为5部分：

1. 计算所有可能的奇数度节点对。
2. 计算1中计算的每个节点对之间的最短路径。
3. 创建一个完整的图, 将图1中的每个节点对与图2中计算出的最短路径距离属性连接起来。
4. 计算在3中计算出的图表的最小权重匹配。
   (这归结为确定如何配对奇数节点, 以使两对之间的距离之和尽可能小)。
5. 使用4中计算的节点对之间的最短路径增强原始图。

步骤2.1：计算节点对

你可以使用itertools组合功能来计算所有可能的奇数度节点对。你的图形是无向的, 因此我们不在乎顺序：例如(a, b)==(b, a)。

# Compute all pairs of odd nodes. in a list of tuples
odd_node_pairs = list(itertools.combinations(nodes_odd_degree, 2))

# Preview pairs of odd degree nodes
odd_node_pairs[0:10]

[('rs_end_south', 'rc_end_north'), ('rs_end_south', 'v_end_east'), ('rs_end_south', 'rh_end_south'), ('rs_end_south', 'b_end_east'), ('rs_end_south', 'b_bv'), ('rs_end_south', 'rt_end_south'), ('rs_end_south', 'o_rt'), ('rs_end_south', 'y_rt'), ('rs_end_south', 'g_gy2'), ('rs_end_south', 'b_tt_3')]

# Counts
print('Number of pairs: {}'.format(len(odd_node_pairs)))

Number of pairs: 630

让我们用下面的组合来确认这个对数是正确的。幸运的是, 你只需要担心630对。解决此CPP示例的计算时间很短(几秒钟)。

但是, 如果你有3, 600个奇数节点对, 则需要优化约650万对。如果输入大小增加100倍, 则输出增加10, 000倍。

\ begin {equation *} \＃\; of \; pairs = n \; choose \; r = {n \ choose r} = \ frac {n！} {r！(nr)！} = \ frac {36！ } {2！ (36-2)！} = 630 \ end {equation *}

步骤2.2：计算节点对之间的最短路径

这是涉及一些实际计算的第一步。幸运的是, networkx可以轻松实现Dijkstra算法, 以计算两个节点之间的最短路径。你可以将此函数应用于上面在odd_node_pairs中计算出的每对(共630个)。

def get_shortest_paths_distances(graph, pairs, edge_weight_name):
    """Compute shortest distance between each pair of nodes in a graph.  Return a dictionary keyed on node pairs (tuples)."""
    distances = {}
    for pair in pairs:
        distances[pair] = nx.dijkstra_path_length(graph, pair[0], pair[1], weight=edge_weight_name)
    return distances

# Compute shortest paths.  Return a dictionary with node pairs keys and a single value equal to shortest path distance.
odd_node_pairs_shortest_paths = get_shortest_paths_distances(g, odd_node_pairs, 'distance')

# Preview with a bit of hack (there is no head/slice method for dictionaries).
dict(list(odd_node_pairs_shortest_paths.items())[0:10])

{('b_bv', 'y_gy1'): 1.22, ('b_bw', 'rc_end_south'): 1.35, ('b_end_east', 'b_bw'): 3.0400000000000005, ('b_end_east', 'rd_end_north'): 3.83, ('g_gy1', 'nature_end_west'): 0.9900000000000001, ('o_rt', 'y_gy1'): 0.53, ('rc_end_north', 'rd_end_south'): 2.21, ('rc_end_north', 'rs_end_north'): 1.79, ('rs_end_north', 'o_tt'): 2.0999999999999996, ('w_bw', 'rd_end_north'): 1.02}

步骤2.3：创建完整图

完整图只是一个图, 其中每个节点都通过唯一的边缘连接到每个其他节点。

这是Wikipedia的一个基本示例, 该示例具有7个节点的完整图形, 其中具有21个(7个选择2个)边缘：

你在下面创建的图形包含36个节点和630条边线, 以及它们相应的边线权重(距离)。

定义create_complete_graph进行计算。 flip_weights参数用于将距离转换为weight属性, 其中较小的数字表示较大的距离, 较大的数字表示较短的距离。这听起来有点不直观, 但是对于步骤2.4(在整个图形上计算最小权重匹配)而言, 这是必需的。

理想情况下, 你应该直接计算最小权重匹配, 但是NetworkX仅实现max_weight_matching函数, 该函数最大化而不是最小化边缘权重。我们通过对distance属性取反(乘以-1)来获得权重, 从而对此有所帮助。这样可以确保按距离排序和缩放, 但保持相反。

def create_complete_graph(pair_weights, flip_weights=True):
    """
    Create a completely connected graph using a list of vertex pairs and the shortest path distances between them
    Parameters:
        pair_weights: list[tuple] from the output of get_shortest_paths_distances
        flip_weights: Boolean. Should we negate the edge attribute in pair_weights?
    """
    g = nx.Graph()
    for k, v in pair_weights.items():
        wt_i = - v if flip_weights else v
        g.add_edge(k[0], k[1], attr_dict={'distance': v, 'weight': wt_i})
    return g

# Generate the complete graph
g_odd_complete = create_complete_graph(odd_node_pairs_shortest_paths, flip_weights=True)

# Counts
print('Number of nodes: {}'.format(len(g_odd_complete.nodes())))
print('Number of edges: {}'.format(len(g_odd_complete.edges())))

Number of nodes: 36
Number of edges: 630

对于视觉道具, 下面绘制了奇数度节点对的完全连接图。请注意, 你保留了每个节点的X, Y坐标, 但是边缘不一定代表实际的路径。例如, 在此图中, 两个节点可以通过一条边连接, 但是它们之间的最短路径可能是经过偶数度节点(此处未显示)的5个跃点。

# Plot the complete graph of odd-degree nodes
plt.figure(figsize=(8, 6))
pos_random = nx.random_layout(g_odd_complete)
nx.draw_networkx_nodes(g_odd_complete, node_positions, node_size=20, node_color="red")
nx.draw_networkx_edges(g_odd_complete, node_positions, alpha=0.1)
plt.axis('off')
plt.title('Complete Graph of Odd-degree Nodes')
plt.show()

步骤2.4：计算最小重量匹配

这是CPP中最复杂的步骤。你需要找到其(它们之间的距离的)总和尽可能小的奇数度节点对。因此, 对于你的问题, 这归结为从在2.3中生成的图形的毛发球中选择最佳的18条边(36个奇数度节点/ 2)。

这种优化的实现和直觉都超出了本教程的范围…例如800余行代码和超出该范围的大量学术文献。

但是, 有兴趣的读者可以快速阅读：

非常感谢Joris van Rantwijk早在2008年就在他的博客中编写了原始实现。我以与Joris相同的意图偶然发现了这个问题。从Joris 2008年的帖子中：

由于我没有找到最大加权匹配的任何Perl实现, 因此我决定自己编写一些代码。原来, 我已经低估了这个问题, 但是当我意识到自己的错误时, 我对这个问题如此着迷, 以至于我拒绝放弃。

但是, 我没有放弃。幸运的是乔里斯没有。

此最大重量匹配已折叠并保留在NetworkX软件包中。还要感谢GitHub上的10多个贡献者, 他们维护了这个庞大的代码库。

这是一项艰巨而密集的计算。 1965年的首次突破证明, 最大匹配问题可以在多项式时间内解决。它由杰克·埃德蒙兹(Jack Edmonds)出版, 也许是有史以来最美丽的学术论文之一：”路径, 树木和花朵” [1]。此后, 已有大量文献改进了优化程序。 NetworkX函数max_weight_matching中实现的代码基于Galil, Zvi(1986)[2], 该算法采用O(n3)时间算法。

# Compute min weight matching.
# Note: max_weight_matching uses the 'weight' attribute by default as the attribute to maximize.
odd_matching_dupes = nx.algorithms.max_weight_matching(g_odd_complete, True)

print('Number of edges in matching: {}'.format(len(odd_matching_dupes)))

Number of edges in matching: 36

匹配的输出(odd_matching_dupes)是一个字典。尽管此匹配中有36条边, 但你只需要18条边。每个边对出现两次(一次以节点1为键, 第二次以节点2为字典的键)。

# Preview of matching with dupes
odd_matching_dupes

{'b_bv': 'v_bv', 'b_bw': 'rh_end_tt_1', 'b_end_east': 'g_gy2', 'b_end_west': 'rd_end_south', 'b_tt_3': 'rt_end_north', 'b_v': 'v_end_west', 'g_gy1': 'rc_end_north', 'g_gy2': 'b_end_east', 'g_w': 'w_bw', 'nature_end_west': 'o_y_tt_end_west', 'o_rt': 'o_w_1', 'o_tt': 'rh_end_tt_2', 'o_w_1': 'o_rt', 'o_y_tt_end_west': 'nature_end_west', 'rc_end_north': 'g_gy1', 'rc_end_south': 'y_gy1', 'rd_end_north': 'rh_end_north', 'rd_end_south': 'b_end_west', 'rh_end_north': 'rd_end_north', 'rh_end_south': 'y_rh', 'rh_end_tt_1': 'b_bw', 'rh_end_tt_2': 'o_tt', 'rh_end_tt_3': 'rh_end_tt_4', 'rh_end_tt_4': 'rh_end_tt_3', 'rs_end_north': 'v_end_east', 'rs_end_south': 'y_gy2', 'rt_end_north': 'b_tt_3', 'rt_end_south': 'y_rt', 'v_bv': 'b_bv', 'v_end_east': 'rs_end_north', 'v_end_west': 'b_v', 'w_bw': 'g_w', 'y_gy1': 'rc_end_south', 'y_gy2': 'rs_end_south', 'y_rh': 'rh_end_south', 'y_rt': 'rt_end_south'}

你可以将此字典转换为元组列表, 因为你具有无向图, 并且顺序无关紧要。删除重复项将产生唯一的18个边对, 这些边对累计总和为最小距离。

# Convert matching to list of deduped tuples
odd_matching = list(pd.unique([tuple(sorted([k, v])) for k, v in odd_matching_dupes.items()]))

# Counts
print('Number of edges in matching (deduped): {}'.format(len(odd_matching)))

Number of edges in matching (deduped): 18

# Preview of deduped matching
odd_matching

[('rs_end_south', 'y_gy2'), ('b_end_west', 'rd_end_south'), ('b_bv', 'v_bv'), ('rh_end_tt_3', 'rh_end_tt_4'), ('b_bw', 'rh_end_tt_1'), ('o_tt', 'rh_end_tt_2'), ('g_w', 'w_bw'), ('b_end_east', 'g_gy2'), ('nature_end_west', 'o_y_tt_end_west'), ('g_gy1', 'rc_end_north'), ('o_rt', 'o_w_1'), ('rs_end_north', 'v_end_east'), ('rc_end_south', 'y_gy1'), ('rh_end_south', 'y_rh'), ('rt_end_south', 'y_rt'), ('b_tt_3', 'rt_end_north'), ('rd_end_north', 'rh_end_north'), ('b_v', 'v_end_west')]

让我们在前面步骤2.3中绘制的完整图表上可视化这些对。和以前一样, 虽然节点位置在此处反映了真实的图形(足迹图), 但是所示的边距(蓝线)与乌鸦飞过的距离相同。从一个节点到另一个节点的实际最短路径可能涉及多个沿相当长的距离扭曲和转向的边。

plt.figure(figsize=(8, 6))

# Plot the complete graph of odd-degree nodes
nx.draw(g_odd_complete, pos=node_positions, node_size=20, alpha=0.05)

# Create a new graph to overlay on g_odd_complete with just the edges from the min weight matching
g_odd_complete_min_edges = nx.Graph(odd_matching)
nx.draw(g_odd_complete_min_edges, pos=node_positions, node_size=20, edge_color='blue', node_color='red')

plt.title('Min Weight Matching on Complete Graph')
plt.show()

为了说明这与原始图形的适合程度, 你绘制了相同的最小权重对(蓝线), 但在轨迹图上(渐变)而不是完整的图上。同样, 请注意, 蓝线是丛林砍伐路线(因为乌鸦飞过边缘, 而不是实际踪迹)。在步骤3中, 你还需要做一些工作来查找构成每对之间最短路径的边。

plt.figure(figsize=(8, 6))

# Plot the original trail map graph
nx.draw(g, pos=node_positions, node_size=20, alpha=0.1, node_color='black')

# Plot graph to overlay with just the edges from the min weight matching
nx.draw(g_odd_complete_min_edges, pos=node_positions, node_size=20, alpha=1, node_color='red', edge_color='blue')

plt.title('Min Weight Matching on Orginal Graph')
plt.show()

步骤2.5：扩充原始图形

现在, 你可以使用在2.4中计算出的匹配结果中的边来扩展原始图形。下面定义了一个简单的函数来完成此操作, 该函数还指出这些新边来自增强图。在通过图实际创建欧拉回路时, 你需要在3.中知道这一点。

def add_augmenting_path_to_graph(graph, min_weight_pairs):
    """
    Add the min weight matching edges to the original graph
    Parameters:
        graph: NetworkX graph (original graph from trailmap)
        min_weight_pairs: list[tuples] of node pairs from min weight matching
    Returns:
        augmented NetworkX graph
    """

    # We need to make the augmented graph a MultiGraph so we can add parallel edges
    graph_aug = nx.MultiGraph(graph.copy())
    for pair in min_weight_pairs:
        graph_aug.add_edge(pair[0], pair[1], attr_dict={'distance': nx.dijkstra_path_length(graph, pair[0], pair[1]), 'trail': 'augmented'}
                          )
    return graph_aug

让我们确认你的扩充图添加了预期的边数(18)：

# Create augmented graph: add the min weight matching edges to g
g_aug = add_augmenting_path_to_graph(g, odd_matching)

# Counts
print('Number of edges in original graph: {}'.format(len(g.edges())))
print('Number of edges in augmented graph: {}'.format(len(g_aug.edges())))

Number of edges in original graph: 123
Number of edges in augmented graph: 141

我们还要确认每个节点现在都具有偶数度：

pd.value_counts(g_aug.degree())

4    54
2    18
6     5
dtype: int64

CPP步骤3：计算欧拉回路

现在, 你有了一个具有偶数度的图形, 艰苦的优化工作已经结束。正如欧拉在1736年以柯尼斯堡问题的七桥而著名地假设的那样, 存在一条路径, 如果所有节点都具有偶数度, 则该路径恰好访问每个边一次。卡尔·希尔霍泽(Carl Hierholzer)在1870年代后期正式证明了这一结果。

可以构造许多具有相同距离的欧拉回路。你可以使用NetworkX eulerian_circuit函数获得90％的处理率。但是, 有一些限制。

你将解决的限制：

1. 扩充图可能(并且很可能会)包含原始图上不存在的边。要获得电路(不打草), 你必须将这些扩展的边分解为通过实际存在的边的最短路径。
2. eulerian_circuit仅返回我们击中每个节点的顺序。它不返回完成电路所需的边沿属性。这是必要的, 因为当两个节点之间存在多个边时, 你需要跟踪已经走过的边。

你无法解决的限制：

1. 为了节省双腿的工作, 你可以放宽欧拉循环的假设, 即在同一节点处开始和结束。如果恰好有两个奇数度的节点, 也可以找到一条欧拉路径(欧拉回路的一般情况)。这将为你节省一些双重支持…假设你可以从公园的另一端搭车回来。但是, 在撰写本文时, NetworkX还没有提供Euler Path算法。 eulerian_circuit代码还不错, 在这种情况下可以采用, 但是在这里你将使其保持简单。

天真电路

尽管如此, 让我们从简单但不完整的解决方案开始：

naive_euler_circuit = list(nx.eulerian_circuit(g_aug, source='b_end_east'))

如预期的那样, 幼稚的欧拉回路的长度等于扩充图中的边数。

print('Length of eulerian circuit: {}'.format(len(naive_euler_circuit)))

Length of eulerian circuit: 141

输出只是代表节点对的元组列表。请注意, 每对的第一个节点与前一对的第二个节点相同。

# Preview naive Euler circuit
naive_euler_circuit[0:10]

[('b_end_east', 'g_gy2'), ('g_gy2', 'b_g'), ('b_g', 'b_w'), ('b_w', 'b_gy2'), ('b_gy2', 'w_gy2'), ('w_gy2', 'b_w'), ('b_w', 'w_rs'), ('w_rs', 'g_rs'), ('g_rs', 'b_g'), ('b_g', 'b_rs')]

正确电路

现在, 让我们定义一个函数, 该函数利用原始图形来告诉你从节点A到节点B使用哪些路径。尽管代码很冗长, 但这种逻辑实际上非常简单。你只需仅使用原始图中存在的边, 即可将包含原始图中不存在的边的朴素电路转换为欧拉电路。

你遍历幼稚的欧拉回路(naive_euler_circuit)中的每个边。遇到原始图形中不存在的边的任何地方, 都可以使用原始图形将其替换为包含其节点之间最短路径的边序列。

def create_eulerian_circuit(graph_augmented, graph_original, starting_node=None):
    """Create the eulerian path using only edges from the original graph."""
    euler_circuit = []
    naive_circuit = list(nx.eulerian_circuit(graph_augmented, source=starting_node))

    for edge in naive_circuit:
        edge_data = graph_augmented.get_edge_data(edge[0], edge[1])    

        if edge_data[0]['trail'] != 'augmented':
            # If `edge` exists in original graph, grab the edge attributes and add to eulerian circuit.
            edge_att = graph_original[edge[0]][edge[1]]
            euler_circuit.append((edge[0], edge[1], edge_att))
        else:
            aug_path = nx.shortest_path(graph_original, edge[0], edge[1], weight='distance')
            aug_path_pairs = list(zip(aug_path[:-1], aug_path[1:]))

            print('Filling in edges for augmented edge: {}'.format(edge))
            print('Augmenting path: {}'.format(' => '.join(aug_path)))
            print('Augmenting path pairs: {}\n'.format(aug_path_pairs))

            # If `edge` does not exist in original graph, find the shortest path between its nodes and
            #  add the edge attributes for each link in the shortest path.
            for edge_aug in aug_path_pairs:
                edge_aug_att = graph_original[edge_aug[0]][edge_aug[1]]
                euler_circuit.append((edge_aug[0], edge_aug[1], edge_aug_att))

    return euler_circuit

你可以通过在Blue步道(节点” b_end_east”)的公园的最东端启动欧拉循环来稍微突破限制3。实际运行该程序时, 你可以跳过最后一个翻倍的方向。

添加了详细的打印语句, 以传达当你使用实际存在的边用最短路径替换扩充图中不存在的边时发生的情况。

# Create the Eulerian circuit
euler_circuit = create_eulerian_circuit(g_aug, g, 'b_end_east')

Filling in edges for augmented edge: ('b_end_east', 'g_gy2')
Augmenting path: b_end_east => b_y => b_o => b_gy2 => w_gy2 => g_gy2
Augmenting path pairs: [('b_end_east', 'b_y'), ('b_y', 'b_o'), ('b_o', 'b_gy2'), ('b_gy2', 'w_gy2'), ('w_gy2', 'g_gy2')]

Filling in edges for augmented edge: ('b_bw', 'rh_end_tt_1')
Augmenting path: b_bw => b_tt_1 => rh_end_tt_1
Augmenting path pairs: [('b_bw', 'b_tt_1'), ('b_tt_1', 'rh_end_tt_1')]

Filling in edges for augmented edge: ('b_tt_3', 'rt_end_north')
Augmenting path: b_tt_3 => b_tt_2 => tt_rt => v_rt => rt_end_north
Augmenting path pairs: [('b_tt_3', 'b_tt_2'), ('b_tt_2', 'tt_rt'), ('tt_rt', 'v_rt'), ('v_rt', 'rt_end_north')]

Filling in edges for augmented edge: ('rc_end_north', 'g_gy1')
Augmenting path: rc_end_north => v_rc => b_rc => g_rc => g_gy1
Augmenting path pairs: [('rc_end_north', 'v_rc'), ('v_rc', 'b_rc'), ('b_rc', 'g_rc'), ('g_rc', 'g_gy1')]

Filling in edges for augmented edge: ('y_gy1', 'rc_end_south')
Augmenting path: y_gy1 => y_rc => rc_end_south
Augmenting path pairs: [('y_gy1', 'y_rc'), ('y_rc', 'rc_end_south')]

Filling in edges for augmented edge: ('b_end_west', 'rd_end_south')
Augmenting path: b_end_west => b_v => rd_end_south
Augmenting path pairs: [('b_end_west', 'b_v'), ('b_v', 'rd_end_south')]

Filling in edges for augmented edge: ('rh_end_north', 'rd_end_north')
Augmenting path: rh_end_north => v_rh => v_rd => rd_end_north
Augmenting path pairs: [('rh_end_north', 'v_rh'), ('v_rh', 'v_rd'), ('v_rd', 'rd_end_north')]

Filling in edges for augmented edge: ('v_end_east', 'rs_end_north')
Augmenting path: v_end_east => v_rs => rs_end_north
Augmenting path pairs: [('v_end_east', 'v_rs'), ('v_rs', 'rs_end_north')]

Filling in edges for augmented edge: ('y_gy2', 'rs_end_south')
Augmenting path: y_gy2 => y_rs => rs_end_south
Augmenting path pairs: [('y_gy2', 'y_rs'), ('y_rs', 'rs_end_south')]

你会看到, 欧拉回路的长度比幼稚回路的长度长, 这是有道理的。

print('Length of Eulerian circuit: {}'.format(len(euler_circuit)))

Length of Eulerian circuit: 158

CPP解决方案

文本

这是文本中解决方案的打印输出：

# Preview first 20 directions of CPP solution
for i, edge in enumerate(euler_circuit[0:20]):
    print(i, edge)

0 ('b_end_east', 'b_y', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 1.32})
1 ('b_y', 'b_o', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.08})
2 ('b_o', 'b_gy2', {'color': 'blue', 'estimate': 1, 'trail': 'b', 'distance': 0.05})
3 ('b_gy2', 'w_gy2', {'color': 'yellowgreen', 'estimate': 1, 'trail': 'gy2', 'distance': 0.03})
4 ('w_gy2', 'g_gy2', {'color': 'yellowgreen', 'estimate': 0, 'trail': 'gy2', 'distance': 0.05})
5 ('g_gy2', 'b_g', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.45})
6 ('b_g', 'b_w', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.16})
7 ('b_w', 'b_gy2', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.41})
8 ('b_gy2', 'w_gy2', {'color': 'yellowgreen', 'estimate': 1, 'trail': 'gy2', 'distance': 0.03})
9 ('w_gy2', 'b_w', {'color': 'gray', 'estimate': 0, 'trail': 'w', 'distance': 0.42})
10 ('b_w', 'w_rs', {'color': 'gray', 'estimate': 1, 'trail': 'w', 'distance': 0.06})
11 ('w_rs', 'g_rs', {'color': 'red', 'estimate': 0, 'trail': 'rs', 'distance': 0.18})
12 ('g_rs', 'b_g', {'color': 'green', 'estimate': 1, 'trail': 'g', 'distance': 0.05})
13 ('b_g', 'b_rs', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.07})
14 ('b_rs', 'g_rs', {'color': 'red', 'estimate': 0, 'trail': 'rs', 'distance': 0.11})
15 ('g_rs', 'g_rc', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.45})
16 ('g_rc', 'g_gy1', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.37})
17 ('g_gy1', 'g_rt', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.26})
18 ('g_rt', 'g_w', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.31})
19 ('g_w', 'o_w_1', {'color': 'gray', 'estimate': 0, 'trail': 'w', 'distance': 0.18})

你可以很快地说出该算法对任何特定路径都不是很忠实, 可以很快地从一个跳到下一个。对该方法的扩展可能会很花哨, 并将跟踪忠诚度的概念构建到目标函数中, 以使实际运行此路由更易于管理。

统计资料

让我们深入了解你的解决方案, 看看它的合理性。

(对于详细代码, 仅打印输出, 不重要)

# Computing some stats
total_mileage_of_circuit = sum([edge[2]['distance'] for edge in euler_circuit])
total_mileage_on_orig_trail_map = sum(nx.get_edge_attributes(g, 'distance').values())
_vcn = pd.value_counts(pd.value_counts([(e[0]) for e in euler_circuit]), sort=False)
node_visits = pd.DataFrame({'n_visits': _vcn.index, 'n_nodes': _vcn.values})
_vce = pd.value_counts(pd.value_counts([sorted(e)[0] + sorted(e)[1] for e in nx.MultiDiGraph(euler_circuit).edges()]))
edge_visits = pd.DataFrame({'n_visits': _vce.index, 'n_edges': _vce.values})

# Printing stats
print('Mileage of circuit: {0:.2f}'.format(total_mileage_of_circuit))
print('Mileage on original trail map: {0:.2f}'.format(total_mileage_on_orig_trail_map))
print('Mileage retracing edges: {0:.2f}'.format(total_mileage_of_circuit-total_mileage_on_orig_trail_map))
print('Percent of mileage retraced: {0:.2f}%\n'.format((1-total_mileage_of_circuit/total_mileage_on_orig_trail_map)*-100))

print('Number of edges in circuit: {}'.format(len(euler_circuit)))
print('Number of edges in original graph: {}'.format(len(g.edges())))
print('Number of nodes in original graph: {}\n'.format(len(g.nodes())))

print('Number of edges traversed more than once: {}\n'.format(len(euler_circuit)-len(g.edges())))  

print('Number of times visiting each node:')
print(node_visits.to_string(index=False))

print('\nNumber of times visiting each edge:')
print(edge_visits.to_string(index=False))

Mileage of circuit: 33.59
Mileage on original trail map: 25.76
Mileage retracing edges: 7.83
Percent of mileage retraced: 30.40%

Number of edges in circuit: 158
Number of edges in original graph: 123
Number of nodes in original graph: 77

Number of edges traversed more than once: 35

Number of times visiting each node:
n_nodes  n_visits
     18         1
     38         2
     20         3
      1         4

Number of times visiting each edge:
n_edges  n_visits
     88         1
     35         2

可视化CPP解决方案

尽管NetworkX还提供了可视化图形的功能, 但在该部门中它们显然是谦虚的：

NetworkX提供了用于可视化图形的基本功能, 但是其主要目标是启用图形分析而不是执行图形可视化。将来, 图形可视化功能可能会从NetworkX中删除, 或者只能作为附加软件包使用。正确的图形可视化很难, 我们强烈建议人们使用专用于该任务的工具可视化图形。专用且功能齐全的图形可视化工具的著名示例是Cytoscape, Gephi, Graphviz, 而对于LaTeX排版, 则是PGF / TikZ。

就是说, 带有matplotlib的内置NetworkX绘图功能足够强大, 足以盯眼并直观地浏览基本图形, 因此你在本教程中始终坚持使用NetworkX绘图。

我使用graphviz和点图描述语言来可视化我的Python包postman_problems中的解决方案。尽管将NetworkX图形结构转换为点状图形花了一些工夫, 但它确实可以提高质量并控制可视化。

创建CPP图

第一步是将要在Euler电路中行走的边列表转换为具有打印友好属性的边列表。

create_cpp_edgelist创建一个边缘列表, 其中包含一些用于绘制的其他属性：

• 序列：记录我们每条边的行走顺序。
• 造访次数：简单来说, 就是我们走到特定边缘的次数。

def create_cpp_edgelist(euler_circuit):
    """
    Create the edgelist without parallel edge for the visualization
    Combine duplicate edges and keep track of their sequence and # of walks
    Parameters:
        euler_circuit: list[tuple] from create_eulerian_circuit
    """
    cpp_edgelist = {}

    for i, e in enumerate(euler_circuit):
        edge = frozenset([e[0], e[1]])

        if edge in cpp_edgelist:
            cpp_edgelist[edge][2]['sequence'] += ', ' + str(i)
            cpp_edgelist[edge][2]['visits'] += 1

        else:
            cpp_edgelist[edge] = e
            cpp_edgelist[edge][2]['sequence'] = str(i)
            cpp_edgelist[edge][2]['visits'] = 1

    return list(cpp_edgelist.values())

让我们创建CPP边缘列表：

cpp_edgelist = create_cpp_edgelist(euler_circuit)

不出所料, 边缘列表的边缘数量与原始图相同。

print('Number of edges in CPP edge list: {}'.format(len(cpp_edgelist)))

Number of edges in CPP edge list: 123

CPP边缘列表看起来与euler_circuit类似, 只是具有一些其他属性。

# Preview CPP plot-friendly edge list
cpp_edgelist[0:3]

[('rh_end_tt_4', 'nature_end_west', {'color': 'black', 'distance': 0.2, 'estimate': 0, 'sequence': '73', 'trail': 'tt', 'visits': 1}), ('rd_end_south', 'b_rd', {'color': 'red', 'distance': 0.13, 'estimate': 0, 'sequence': '95', 'trail': 'rd', 'visits': 1}), ('w_gy1', 'w_rc', {'color': 'gray', 'distance': 0.33, 'estimate': 0, 'sequence': '151', 'trail': 'w', 'visits': 1})]

现在让我们来做图：

# Create CPP solution graph
g_cpp = nx.Graph(cpp_edgelist)

可视化1：追溯步骤

在这里, 你说明了哪些边缘走过一次(灰色)并且走过了一次(蓝色)。这是在2.4中创建的可视化的”正确”版本, 该版本显示了奇数节点对(红色)之间的幼稚(乌鸦飞过)连接。通过在每对奇数度节点对中实际存在的边缘跟踪最短路径, 可以对此进行更正。

如果优化效果良好, 则这些蓝线应表示可能的最小距离。具体而言, 生成奇数度节点匹配所需的最小距离。

plt.figure(figsize=(14, 10))

visit_colors = {1:'lightgray', 2:'blue'}
edge_colors = [visit_colors[e[2]['visits']] for e in g_cpp.edges(data=True)]
node_colors = ['red'  if node in nodes_odd_degree else 'lightgray' for node in g_cpp.nodes()]

nx.draw_networkx(g_cpp, pos=node_positions, node_size=20, node_color=node_colors, edge_color=edge_colors, with_labels=False)
plt.axis('off')
plt.show()

可视化2：CPP解决方案序列

在这里, 你绘制了原始图(足迹图), 并标有序列号, 我们按照CPP解决方案在其中行走。多个数字表示必须重新加倍的路径。

你从右下角的蓝色轨迹开始(第0和第157个方向)。

plt.figure(figsize=(14, 10))

edge_colors = [e[2]['color'] for e in g_cpp.edges(data=True)]
nx.draw_networkx(g_cpp, pos=node_positions, node_size=10, node_color='black', edge_color=edge_colors, with_labels=False, alpha=0.5)

bbox = {'ec':[1, 1, 1, 0], 'fc':[1, 1, 1, 0]}  # hack to label edges over line (rather than breaking up line)
edge_labels = nx.get_edge_attributes(g_cpp, 'sequence')
nx.draw_networkx_edge_labels(g_cpp, pos=node_positions, edge_labels=edge_labels, bbox=bbox, font_size=6)

plt.axis('off')
plt.show()

可视化3：电影

下面嵌入了追踪欧拉电路的下面的电影。边缘在第一次行走时被涂成黑色, 而第二次则被涂成红色。

请注意, 此gif不能完全重叠重叠或太小而无法正确可视化的边缘。更强大的可视化库(例如graphviz)可以通过绘制样条曲线而不是节点之间的直线来解决此问题。

创建它的代码在下面提供作为参考。

首先, 从CPP解决方案的每个方向(沿边走)生成PNG图像。

visit_colors = {1:'black', 2:'red'}
edge_cnter = {}
g_i_edge_colors = []
for i, e in enumerate(euler_circuit, start=1):

    edge = frozenset([e[0], e[1]])
    if edge in edge_cnter:
        edge_cnter[edge] += 1
    else:
        edge_cnter[edge] = 1

    # Full graph (faded in background)
    nx.draw_networkx(g_cpp, pos=node_positions, node_size=6, node_color='gray', with_labels=False, alpha=0.07)

    # Edges walked as of iteration i
    euler_circuit_i = copy.deepcopy(euler_circuit[0:i])
    for i in range(len(euler_circuit_i)):
        edge_i = frozenset([euler_circuit_i[i][0], euler_circuit_i[i][1]])
        euler_circuit_i[i][2]['visits_i'] = edge_cnter[edge_i]
    g_i = nx.Graph(euler_circuit_i)
    g_i_edge_colors = [visit_colors[e[2]['visits_i']] for e in g_i.edges(data=True)]

    nx.draw_networkx_nodes(g_i, pos=node_positions, node_size=6, alpha=0.6, node_color='lightgray', with_labels=False, linewidths=0.1)
    nx.draw_networkx_edges(g_i, pos=node_positions, edge_color=g_i_edge_colors, alpha=0.8)

    plt.axis('off')
    plt.savefig('fig/png/img{}.png'.format(i), dpi=120, bbox_inches='tight')
    plt.close()

然后将PNG图像缝合在一起以制作上面漂亮的小gif。

首先, PNG按照从0到157的顺序进行排序。然后使用imageio将它们缝合在一起, 速度为每秒3帧以创建gif。

import glob
import numpy as np
import imageio
import os

def make_circuit_video(image_path, movie_filename, fps=5):
    # sorting filenames in order
    filenames = glob.glob(image_path + 'img*.png')
    filenames_sort_indices = np.argsort([int(os.path.basename(filename).split('.')[0][3:]) for filename in filenames])
    filenames = [filenames[i] for i in filenames_sort_indices]

    # make movie
    with imageio.get_writer(movie_filename, mode='I', fps=fps) as writer:
        for filename in filenames:
            image = imageio.imread(filename)
            writer.append_data(image)

make_circuit_video('fig/png/', 'fig/gif/cpp_route_animation.gif', fps=3)

下一步

恭喜, 你已经完成了本教程, 以Python解决中文邮递员问题。在本教程中, 你已经学习了很多内容(准确地说是33.6英里的路程)。为了更深入地了解网络基础知识, 你可能对srcmini的Python网络分析课程感兴趣, 该课程提供了对核心概念的更彻底的处理。

请不要犹豫地查看NetworkX文档, 以获取有关如何创建, 操作和遍历这些复杂网络的更多信息。这些文档非常全面, 包含大量示例和一系列教程。

如果你有兴趣在自己的图上求解CPP, 我已将本教程中的功能打包到Github上的postman_problems Python包中。你还可以将本教程中的代码块与不同的边缘和节点列表组合在一起, 但是postman_problems包可能会使你更快更干净地到达那里。

有一天, 我计划在此处实施CPP的扩展(“农村和有风邮递员问题”)。我也有雄心勃勃地写这些扩展程序, 并有经验在我的博客上测试路线上的路线。我计划探索和编写的另一个应用程序是合并经纬度坐标, 以开发(或使用)一种将转弯方向发送到Garmin手表的机制。

当然还有最后一步：走出去, 沿着路线行驶！

如果你想了解有关NetworkX库的更多信息, 请参加srcmini的Python网络分析(第1部分)课程。

参考文献

1：埃德蒙兹, 杰克(1965)。 “路径, 树木和花朵”。加纳。 J.数学17：449–467。

2：Galil, Z。(1986)。 “用于在图中找到最大匹配的有效算法”。 ACM计算调查。卷18, No。1：23-38。