Skip to main content
 首页 » 编程设计

python之如何比较 Networkx 中的有向图

2024年11月01日9myhome

我有两个具有相同节点数和边数的有向 Networkx 图。

如何在 Networkx 中比较这两个不同图的结构?节点名称无关紧要。我尝试使用 Information about graph structure 中的 Networkx DiGraph.order()、DiGraph.degree() 等但我的图表的所有参数都相等。

以及通常如何比较 2 个以上图的结构并仅找到具有独特结构的图。 Networkx 有专门的功能吗?

请您参考如下方法:

要确定两个图是否同构,您可以使用函数 is_isomorphic()。不幸的是,没有比较 2 个以上图表的功能。但是您可以比较所有可能的图组合,并根据同构的组合构建图 iso_graph。要查找所有同构图组,您可以使用函数 connected_components() 或 find_cliques() 和 iso_graph:

import networkx as nx 
from itertools import combinations 
 
G1 = nx.path_graph(4) 
G2 = nx.path_graph(4) 
G3 = nx.path_graph(4) 
G4 = nx.path_graph(5) 
G5 = nx.path_graph(5) 
G6 = nx.path_graph(5) 
 
graphs = {G1: 'G1', G2: 'G2', G3: 'G3', G4: 'G4', G5: 'G5', G6: 'G6'} 
iso_pairs = {(graphs[g1], graphs[g2]) for g1, g2 in combinations(graphs, 2) if nx.is_isomorphic(g1, g2)} 
# {('G1', 'G3'), ('G5', 'G6'), ('G4', 'G6'), ('G1', 'G2'), ('G4', 'G5'), ('G2', 'G3')} 
 
iso_graph = nx.from_edgelist(iso_pairs)  
for c in nx.connected_components(iso_graph): 
    print(c) 
# {'G1', 'G3', 'G2'} 
# {'G5', 'G6', 'G4'} 
 
%matplotlib inline # jupyter notebook 
nx.draw(iso_graph, with_labels=True)