NetworkX同构：如何获取边标签映射关系

问题背景 #

我有两个带不同边标签的同构图，定义代码如下：

import networkx as nx
from networkx.algorithms import isomorphism

G1 = nx.Graph()
G1.add_edges_from([(1,2), (2,3), (3,4), (4,2)])
attrs1 = {(1, 2): {'label': 'Albert'}, (2, 3): {'label': 'Bob'}, (3, 4): {'label': 'Cole'}, (4, 2): {'label': 'Dan'}}
nx.set_edge_attributes(G1, attrs1)

G2 = nx.Graph()
G2.add_edges_from([(13,14), (12,13), (11,12), (14,12)])
attrs2 = {(11, 12): {'label': 'Alice'}, (12, 13): {'label': 'Barbara'}, (13, 14): {'label': 'Cathrine'}, (14, 12): {'label': 'Delia'}}
nx.set_edge_attributes(G2, attrs2)

通过nx.isomorphism已获取正确的节点映射：

GM = isomorphism.GraphMatcher(G1, G2)
print(GM.is_isomorphic())  # 输出True
print(GM.mapping)
>>> {1: 11, 2: 12, 3: 13, 4: 14}

需要生成目标边标签映射字典：

{'Albert': 'Alice', 'Bob': 'Barbara', 'Cole': 'Cathrine', 'Dan': 'Delia'}

解决方案 #

利用已有的节点映射转换G1边节点到G2对应节点，再提取两边标签即可，以下是两种高效实现方式：

方式一：遍历边并处理无向图顺序问题 #

node_mapping = GM.mapping
edge_label_map = {}

for u, v, attrs in G1.edges(data=True):
    # 将G1的边节点映射到G2的节点
    u2, v2 = node_mapping[u], node_mapping[v]
    # 无向图中边可能以任意顺序存储，需确认两种顺序
    if (u2, v2) in G2.edges:
        g2_label = G2[u2][v2]['label']
    else:
        g2_label = G2[v2][u2]['label']
    edge_label_map[attrs['label']] = g2_label

print(edge_label_map)

方式二：用字典推导式+frozenset简化逻辑 #

frozenset可以统一无向边的表示，避免处理顺序问题：

node_mapping = GM.mapping
# 先构建G2的边-标签映射，用frozenset作为键
g2_edge_label_dict = {frozenset((u, v)): attrs['label'] for u, v, attrs in G2.edges(data=True)}

# 推导生成最终的标签映射
edge_label_map = {
    attrs['label']: g2_edge_label_dict[frozenset((node_mapping[u], node_mapping[v]))]
    for u, v, attrs in G1.edges(data=True)
}

print(edge_label_map)

两种方法的时间复杂度均为O(E)（E为图的边数），能高效生成目标映射。

内容的提问来源于stack exchange，提问作者coaxialquantum