NetworkX：Python图与网络模型基础

在《运筹学》课堂上，我们学习过图与网络，当时用到R语言下的igraph包来计算和展示结果。Python下也有类似甚至更好的库： 。

安装命令如下

引入约定为

1 图的绘制

无向图

无向图由点和边构成，其绘制思路为：①新建空图→②添加点→③添加边。

新建空的无向图

以后所有的信息都添加在无向图G上。

添加点：addnode和add_nodes_from

虽然还没有讲到怎么展示这张图，但你可能想看看自己已经画了啥；所以我们剧透一下：输入nx.draw(G)看看吧。

添加边：add_edge和add_edges_from

移除点或边使用remove_*系列方法。

展示图

NetworkX可以结合matpltlib库来展示图，因此需要载入plt：

最常用的展示命令是 ，所有参数都是可选的。

简单介绍一些可选参数，如

ax：画纸名

nodecolor/edgecolor/font_color：点、边、字颜色

nodeshape/nodesize：点的形状和大小

style：边的形状（solid/dashed/dotted/dashdot）

alpha：点和边的透明度

with_labels：点是否显示标签

arrows/arrowstyle/arrowsize：有向图的箭头设定

我们并列展示默认和自定义结果：

另有 函数，支持自定义点的位置（类型）。

有向图

有向图和无向图的差别仅仅在边是有方向的：

新建空的有向图

添加点：略

添加有向边

2 从图到网络：权的添加

方法一

add_weighted_edges_from方法能够接受（起点，终点，权重）作为元素的序列。推荐这种方法。

方法二

add_edge方法可以添加weight参数。

方法三

类索引方法，在修改权重时非常有用。

添加权重标签

按照上述三个方法添加的边权重，将被记录在边属性下，我们可以通过G.edges(data=True)方法来查看：

特别注意参数data一定要为True，不指定data参数时默认只提取边的起点和终点。结果如下：

关系已经很明确了，我们用元组u,v,w来解包，并将其放在键为边，值为权的字典中：

绘制权重标签

我们分4步来画图：点→边→点标签→边标签（顺序不重要）。因为要分4个图层来画，所以需要明确点的位置，不能用nx.draw()这种随性的方法。

首先定义点的位置pos：

这表明我们使用Fruchterman-Reingold的力引导算法来画图，目的是减少边的交叉（推荐）。可选的pos还有circular_layout、kamada_kawai_layout、random_layout、rescale_layout、shell_layout和spectral_layout，点少的时候看不出来，点多就不一样了。

默认的标签是放在边的中间，可以用label_pos调节，这对双箭头的有向边很重要。

3 最短路

《运筹学》课程中，我们学习了Dijkstra算法；NetworkX提供了相应的命令：

dijkstra_predecessor_and_distance：给出某起点到所有点的最短路径和最短路程，结果也包含两部分，可以用元组解包提取；

dijkstra_path：给出从某起点到某终点的最短路径；

dijkstra_path_length：给出从某起点到某终点的最短路程。

构造一个有向图

求点1到点6的最短路。

展示这个有向图

Dijkstra算法求最短路

指定起点，不指定终点

结果：

指定起点和终点

将最短路径画出来：

附代码：

4 最大流

掌握了最短路再来看最大流，就是很简单的事情了。

通过capacity参数为边添加最大容量；

使用 函数求解。

构造包含最大容量的有向图

绘制这个图

图中边的标签表示最大容量（而非单位运价）。我们想求得从点1到点7的最大流。

计算最大流

通过提取flow_value，我们可以知道从点1到点7的最大流为10；

通过提取flow_dict，我们可以知道最大流情形下，每条边的实际流量：

我们也可以通过 来确定特定边上的实际容量，如 表示边(1,4)上的实际流量为5。

5 结语

NetworkX是复杂网络计算库，能做的事情远不止最短路和最大流。手册在这里，进步靠自己：