数学建模：图论模型的 Python 求解 — NetworkX 简介_python networkx算法

NetworkX 的基本用法

常用函数

import numpy as np
import networkx as nx
import pylab as plt

Graph() #创建无向图 
Graph(A) #由邻接矩阵A创建无向图 
DiGraph() #创建有向图 
DiGraph(A) #由邻接矩阵A创建有向图 
MultiGraph() #创建多重无向图 
MultiDigraph() #创建多重有向图 
add_edge() #添加一条边 
add_edges_from(List) #从列表中添加多条边 
add_node() #添加一个顶点
add_nodes_from(List) #添加顶点集合

dijkstra_path(G, source, target, weight='weight') # Dijkstra 算法求最短路径
dijkstra_path_length(G, source, target, weight='weight') # Dijkstra 算法求最短距离
shortest_path(G, source=None, target=None, weight=None, method='dijkstra') #求所有顶点对之间最短路径
shortest_path_length(G, source=None, target=None, weight=None, method='dijkstra') #求所有顶点对之间最短距离

get_edge_attributes(G, name) #从图中获取边属性 ('weight','color'等)
#返回由边的属性为值的字典, 对于 (di)graphs, 键是2元组的形式(u, v), 对于multi(di)graphs, 键是3元组形式(u, v, key)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

画图

nx.draw_networkx

nx.draw_networkx(G, pos=None, arrows=None, with_labels=True, **kwds)
#带有节点位置、标签、标题和许多其他绘图功能的选项
#参数: 
# G: networkx图
# pos: 图形布局 以节点为键、位置为值的字典, 或下面的布局方式 如果未指定,使用spring_layout
# arrows: 绘制箭头的方法 布尔或None
# with_labels: 在节点上绘制标签 布尔
# **kwds: 其它参数
1
2
3
4
5
6
7
8

nx.draw

nx.draw(G, pos=None, ax=None, **kwds)
#没有标签或轴的简单绘图
# ax: Matplotlib 轴对象, 可选, 在指定的 Matplotlib 轴上绘制图形
#其他参数与 nx.draw_networkx 类似
1
2
3
4

其它参数

• node_size: 指定节点的尺寸大小(默认是300)
• node_color: 指定节点的颜色 (默认是红色，可以用字符串简单标识颜色，例如’r’为红色，'b’为绿色等)
• node_shape: 节点的形状（默认是圆形，用字符串’o’标识）
• alpha: 透明度 (默认是1.0，不透明，0为完全透明)
• width: 边的宽度 (默认为1.0)
• edge_color: 边的颜色(默认为黑色)
• style: 边的样式(默认为实现，可选： solid|dashed|dotted,dashdot)
• with_labels: 节点是否带标签（默认为True）
• font_size: 节点标签字体大小 (默认为12)
• font_color: 节点标签字体颜色（默认为黑色）

图形布局设置

circular_layout #顶点在一个圆环上均匀分布 
random_layout #顶点随机分布 
shell_layout #顶点在同心圆上分布 
spring_layout #用 Fruchterman-Reingold 算法排列顶点 
spectral_layout #根据图的拉普拉斯特征向量排列顶点
1
2
3
4
5

NetworkX 画图示例

例 1: 画无向图

邻接矩阵为
A = [ 0 9 2 4 7 9 0 3 4 0 2 3 0 8 4 4 4 8 0 6 7 0 4 6 0 ] A=\left[

$$\begin{array}{lllll} 0 & 9 & 2 & 4 & 7 \\ 9 & 0 & 3 & 4 & 0 \\ 2 & 3 & 0 & 8 & 4 \\ 4 & 4 & 8 & 0 & 6 \\ 7 & 0 & 4 & 6 & 0 \end{array}$$ \right] A=⎣⎢⎢⎢⎢⎡​09247​90340​23084​44806​70460​⎦⎥⎥⎥⎥⎤​

为了便于理解图的结构与 NetworkX 中的函数, 我们分别用三种方式来构造这个图, 最简单和常用的是用 nx.Graph() 用邻接矩阵构造

# 直接用邻接矩阵构造图
import numpy as np
import networkx as nx
import pylab as plt
A=np.array([[0,9,2,4,7],
            [9,0,3,4,0],
            [2,3,0,8,4],
            [4,4,8,0,6],
            [7,0,4,6,0]])
G=nx.Graph(A)
w = nx.get_edge_attributes(G,'weight') #获取边的权重
pos=nx.shell_layout(G)  #顶点在同心圆上分布
nx.draw(G, pos, with_labels=True, font_weight='bold',font_size=12) #画图
nx.draw_networkx_edge_labels(G,pos,edge_labels=w) #标注权重
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

为了熟悉图的结构和 NetworkX 的函数, 再用两种较复杂的方法构造图

# 构造顶点集、边集、标签再构造图
import numpy as np
import networkx as nx
import pylab as plt
A=np.array([[0,9,2,4,7],
            [9,0,3,4,0],
            [2,3,0,8,4],
            [4,4,8,0,6],
            [7,0,4,6,0]])
i,j=np.nonzero(A)  #提取顶点的编号
w=A[i,j]  #提出A中的非零元素
i,j=i+1,j+1
edges=list(zip(i,j,w)) #边集
#列表 元素为边的两顶点及其权重的三个元素的元组 {(a1,a2,w12), (a3,a4,w34), ...}
G=nx.Graph()
G.add_weighted_edges_from(edges) #添加边
key=range(1,6); s=[str(i+1) for i in range(5)]
s=dict(zip(key,s))  #用于顶点标注的字符字典
plt.rc('font',size=18)

plt.subplot(121)
pos=nx.shell_layout(G)  #顶点在同心圆上分布
nx.draw(G,pos,font_weight='bold',labels=s) #画图, 边不标注权重, 用构造的字典标注顶点
#nx.draw(G,pos,with_labels=True,font_weight='bold') #画图, 边不标注权重
# font_weight='bold' 加粗

plt.subplot(122)
pos=nx.shell_layout(G)  #顶点在同心圆上分布
#nx.draw(G,pos,with_labels=True,node_size=260)
nx.draw(G,pos,node_size=260,labels=s) #用构造的字典标注顶点
w = nx.get_edge_attributes(G,'weight') 
#获取边的权重, 字典 键为相邻顶点编号的元组, 值为这条边的权重 {(a,b): weight, ...} 
#print(w)
nx.draw_networkx_edge_labels(G,pos,font_size=12,edge_labels=w) #标注权重
#plt.savefig("figure10_2.png", dpi=500) 
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# 输入列表构造赋权图
import networkx as nx
import pylab as plt
import numpy as np
edges=[(1,2,9),(1,3,2),(1,4,4),(1,5,7),
  (2,3,3),(2,4,4),(3,4,8),(3,5,4),(4,5,6)] #边集
G=nx.Graph()
G.add_nodes_from(range(1,6)) #添加顶点
G.add_weighted_edges_from(edges) #添加边
pos=nx.shell_layout(G) #顶点在同心圆上分布
w = nx.get_edge_attributes(G,'weight') #获取边的权重
nx.draw(G, pos, with_labels=True, font_weight='bold',font_size=12) #画图
nx.draw_networkx_edge_labels(G,pos,edge_labels=w) #标注权重
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14

例 2: 画有向图

邻接矩阵
A = [ 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 ] A=\left[

$$\begin{array}{llllll} 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \end{array}$$ \right] A=⎣⎢⎢⎢⎢⎢⎢⎡​000000​101110​110000​000010​001001​000110​⎦⎥⎥⎥⎥⎥⎥⎤​

这里也用两种方式来构造图

# 直接用邻接矩阵构造图
import numpy as np
import networkx as nx
import pylab as plt
A=np.array([[0, 1, 1, 0, 0, 0], 
            [0, 0, 1, 0, 0, 0], 
            [0, 1, 0, 0, 1, 0], 
            [0, 1, 0, 0, 0, 1], 
            [0, 1, 0, 1, 0, 1], 
            [0, 0, 0, 0, 1, 0]])
G=nx.DiGraph(A)
plt.rc('font',size=16)
pos=nx.shell_layout(G) #顶点在同心圆上分布
nx.draw(G,pos,with_labels=True, font_weight='bold',node_color='r')
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 构造顶点集、边集、标签再构造图
import numpy as np
import networkx as nx
import pylab as plt
G=nx.DiGraph()
edges=[(1,2),(1,3),(2,3),(3,2),(3,5),(4,2),(4,6),
      (5,2),(5,4),(5,6),(6,5)] #边集, 无权
G.add_nodes_from(range(1,7)) #顶点
G.add_edges_from(edges) #边
plt.rc('font',size=16)
pos=nx.shell_layout(G) #顶点在同心圆上分布
nx.draw(G,pos,with_labels=True, font_weight='bold',node_color='r')
#plt.savefig("figure10_3.png", dpi=500) 
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14

图数据的导出

import numpy as np
import networkx as nx
import pylab as plt
A=np.array([[0, 9, 2, 4, 7],
            [0, 0, 3, 4, 0],
            [0, 0, 0, 8, 4],
            [0, 0, 0, 0, 6],
            [0, 0, 0, 0, 0]])
G=nx.Graph(A)    #利用邻接矩阵构造赋权无向图
plt.rc('font',size=16)
pos=nx.shell_layout(G) #顶点在同心圆上分布
nx.draw(G,pos,with_labels=True, font_weight='bold')
plt.show()
print("图的顶点集为：", G.nodes())
print("边集为：", G.edges())
print("邻接表为：", list(G.adjacency()))  #显示图的邻接表
print("列表字典为：", nx.to_dict_of_lists(G)) 
B=nx.to_numpy_matrix(G)  #从图G中导出邻接矩阵B，这里B=A
C=nx.to_scipy_sparse_matrix(G)  #从图G中导出稀疏矩阵C
print(f'邻接矩阵：\n{B}')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

图的顶点集为： [0, 1, 2, 3, 4]
边集为： [(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4)]
邻接表为： [(0, {1: {'weight': 9}, 2: {'weight': 2}, 3: {'weight': 4}, 4: {'weight': 7}}), (1, {0: {'weight': 9}, 2: {'weight': 3}, 3: {'weight': 4}}), (2, {0: {'weight': 2}, 1: {'weight': 3}, 3: {'weight': 8}, 4: {'weight': 4}}), (3, {0: {'weight': 4}, 1: {'weight': 4}, 2: {'weight': 8}, 4: {'weight': 6}}), (4, {0: {'weight': 7}, 2: {'weight': 4}, 3: {'weight': 6}})]
列表字典为： {0: [1, 2, 3, 4], 1: [0, 2, 3], 2: [0, 1, 3, 4], 3: [0, 1, 2, 4], 4: [0, 2, 3]}
邻接矩阵：
[[0. 9. 2. 4. 7.]
 [9. 0. 3. 4. 0.]
 [2. 3. 0. 8. 4.]
 [4. 4. 8. 0. 6.]
 [7. 0. 4. 6. 0.]]
1
2
3
4
5
6
7
8
9
10