NetworkX 系列教程 (7)- 对 graph 进行分析

发表于 更新于 分类于 ， 阅读次数： 本文字数： 3.6k 阅读时长 ≈ 3 分钟

graph 构建完成后，对 graph 的连通等属性进行分析.

注意：如果代码出现找不库，请返回第一个教程，把库文件导入.

对图进行分析

强连通：有向图中任意两点 v1、v2 间存在 v1 到 v2 的路径（path）及 v2 到 v1 的路径。
弱联通：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。

连通子图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#定义图的节点和边
nodes=['0','1','2','3','4','5','a','b','c']
edges=[('0','0',1),('0','1',1),('0','5',1),('0','5',2),('1','2',3),('1','4',5),('2','1',7),('2','4',6),('a','b',0.5),('b','c',0.5),('c','a',0.5)]

#定义graph
G = nx.Graph()
G.add_nodes_from(nodes)
G.add_weighted_edges_from(edges)

#找到所有连通子图
print('connected_components of graph: ',list(nx.connected_components(G)))

#显示该graph
nx.draw(G, with_labels=True, font_weight='bold')
plt.axis('on')
plt.xticks([])
plt.yticks([])
plt.show()

输出:

connected_components of graph:  [{'a', 'b', 'c'}, {'4', '0', '5', '1', '2'}, {'3'}]

png

弱联通

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#定义graph
G = nx.path_graph(4, create_using=nx.DiGraph())
G.add_path([7, 8, 3])
G.add_path([5, 6,9])

#找出所有的弱连通图
for c in nx.weakly_connected_components(G):
    print(c)
    
#由大到小的规模判断弱连通子图
print([len(c) for c in sorted(nx.weakly_connected_components(G), key=len, reverse=True)])

nx.draw(G, with_labels=True, font_weight='bold')
plt.axis('on')
plt.xticks([])
plt.yticks([])
plt.show()

输出:

{0, 1, 2, 3, 7, 8}
{9, 5, 6}
[6, 3]

png

强连通

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
G.clear()

#定义图
G = nx.path_graph(4, create_using=nx.DiGraph())
G.add_path([3, 8, 1])

#找出所有的强连通子图
con = nx.strongly_connected_components(G)
print(con,type(con),list(con))

#显示该图
nx.draw(G, with_labels=True, font_weight='bold')
plt.axis('on')
plt.xticks([])
plt.yticks([])
plt.show()

输出:

<generator object strongly_connected_components at 0x7fe0eefe9c50> <class 'generator'> [{8, 1, 2, 3}, {0}]

png

子图

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
G.clear()

#定义图
G = nx.DiGraph()
G.add_path([5, 6, 7, 8])
#抽取图G的节点作为子图
sub_graph = G.subgraph([5, 6, 8])

plt.subplots(1,2,figsize=(15,5))
#画原图
plt.subplot(121)
nx.draw(G, with_labels=True, font_weight='bold')
plt.title('原图',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])

#画子图
plt.subplot(122)
nx.draw(sub_graph, with_labels=True, font_weight='bold')
plt.title('子图',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])

plt.show()

png

条件过滤

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
37
#G.clear()

#定义有向图
G = nx.DiGraph()
road_nodes = {'a':{'id':1}, 'b':{'id':1}, 'c':{'id':3}, 'd':{'id':4}}
road_edges = [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'd')]
G.add_nodes_from(road_nodes.items())
G.add_edges_from(road_edges)

#过滤函数
def flt_func_draw():
    flt_func = lambda d: d['id'] != 1
    return flt_func

plt.subplots(1,2,figsize=(15,5))

#画出原图
plt.subplot(121)
nx.draw(G, with_labels=True, font_weight='bold')
plt.title('过滤前',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])

#过滤原图得到子图
flt_func = flt_func_draw()
part_G = G.subgraph(n for n, d in G.nodes(data=True) if flt_func(d))

#画出子图
plt.subplot(122)
nx.draw(part_G, with_labels=True, font_weight='bold')
plt.title('过滤后',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])

plt.show()

png