python - 如何比较 Networkx 中的有向图？

Question

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

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

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

Answer 1

要确定两个图是否同构，您可以使用函数 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)