如何在NetworkX中正确匹配带边属性的子图？

作为子图匹配新手，我发现NetworkX提供了便捷的实现方式，但不确定如何正确匹配带边属性的图的子图。

示例图定义 #

主图（带边属性） #

import networkx as nx
import networkx.algorithms.isomorphism as iso

G = nx.MultiDiGraph()
G.add_edge(1, 2, label="A")
G.add_edge(1, 2, label="D")
G.add_edge(2, 1, label="B")
G.add_edge(2, 3, label="C")

目标子图（无边属性，匹配长度为2的简单路径结构） #

SG = nx.MultiDiGraph()
SG.add_edge(5, 6)
SG.add_edge(6, 7)

尝试的两种匹配方法 #

方法一：使用categorical_edge_match匹配边属性 #

gm = iso.MultiDiGraphMatcher(G, SG, edge_match=iso.categorical_edge_match("label", None))
print(gm.subgraph_is_monomorphic())

for subgraph_x in gm.subgraph_monomorphisms_iter():
    print(subgraph_x)

输出结果：

True
{1: 5, 2: 6, 3: 7}

我的预期是输出两个子图：((1,2) 带边标签"A", (2,3)带边标签"C")和((1,2)带边标签"D", (2,3)带边标签"C")，但当前输出仅返回节点映射，无法获取对应边的标签信息。

方法二：指定子图边属性匹配 #

SG = nx.MultiDiGraph()
SG.add_edge(5, 6, label="A")
SG.add_edge(6, 7, label="C")

gm = iso.MultiDiGraphMatcher(G, SG, edge_match=lambda x, y: x[0]['label'] == y[0]['label'])
print(gm.subgraph_is_monomorphic())
for subgraph_x in gm.subgraph_monomorphisms_iter():
    print(subgraph_x)

输出结果：

True
{1: 5, 2: 6, 3: 7}

此方法指定边属性后结果符合预期，但我的需求是子图无边属性的场景，因此需要让方法一生效。

无边属性图的匹配冗余问题 #

我测试了无边属性的多有向图，对比subgraph_isomorphisms_iter和subgraph_monomorphisms_iter的表现：

测试代码与subgraph_monomorphisms_iter结果 #

G = nx.MultiDiGraph([(1,2), (1,3), (1,4), (1,4), (4,5), (5,6), (1,7), (7,8)])
subgraph = nx.MultiDiGraph([(10,20), (10,30), (10,40), (40,50)])

subgraphs = []
GM = iso.MultiDiGraphMatcher(G,subgraph,edge_match=iso.categorical_edge_match([],[]))
for subgraph_x in GM.subgraph_monomorphisms_iter():
    subgraphs.append(subgraph_x)
subgraphs    

使用subgraph_monomorphisms_iter输出了12个冗余结果（实际应为3个子图）。

subgraph_isomorphisms_iter结果 #

subgraphs = []
GM = nx.algorithms.isomorphism.DiGraphMatcher(G,subgraph) # 主图节点到子图节点的映射字典
for subgraph_x in GM.subgraph_isomorphisms_iter():
    subgraphs.append(subgraph_x)

输出结果：

[{1: 10, 2: 20, 3: 30, 7: 40, 8: 50}, {1: 10, 3: 20, 2: 30, 7: 40, 8: 50}]

但将前两种带边属性的匹配方法切换为subgraph_isomorphisms_iter时，未找到任何子图，对此我感到困惑。

更新 #

我找到了关于NetworkX中同构与单态区别的清晰解释，也查看了匹配器的源码，了解到冗余结果是由对称性导致的，NetworkX的匹配器并未考虑对称性去重。

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