NetworkX DiGraphMatcher在有向图上不返回结果

Question

我有一个大图，我想在其中使用NetworkX中内置的VF2算法找到一个子图同构。干草堆图和针形图都是有向的。举以下琐碎的例子：

from networkx.algorithms.isomorphism import DiGraphMatcher
G1 = nx.complete_graph(20, nx.DiGraph)
G2 = nx.DiGraph()
G2.add_edge(1, 2)
list(DiGraphMatcher(G1, G2).subgraph_isomorphisms_iter())

最后一行返回一个空列表[]。

我的理解是，这应该返回图中的所有边，事实上，如果我用GraphMatcher代替DiGraphMatcher，我会得到所有边的列表。

DiGraphMatcher有什么问题吗，或者我对DiGraphMatcher应该做什么的理解有什么问题？

版本：

• Python:3.7.7
• NetworkX:2.4

---

示例无向图代码(用Graph替换所有DiGraph，否则相同(：

from networkx.algorithms.isomorphism import GraphMatcher
G1 = nx.complete_graph(20, nx.Graph)
G2 = nx.Graph()
G2.add_edge(1, 2)
list(GraphMatcher(G1, G2).subgraph_isomorphisms_iter())

Answer 1

在经历了许多小时的悲伤之后，回答我自己的问题。我希望这将是一个有趣的技术问题。原来这只是一个普通的命名问题！

NetworkX定义子图同构如下：

如果G'=(N'，E'(是节点诱导子图，则：

• N'是N的子集
• E'是与N'中的节点相关的E中的边的子集

(取自networkx内联代码注释。(

它定义了单声道​态射如下：

如果G'=(N'，E'(是单态性，则：

• N'是N的子集
• E’是N’中E相关节点的边集的子集

此外，注意：

注意，如果G'是G的节点诱导子图，那么它总是G的子图单态性，但相反并不总是成立的，作为单态性可以具有较少的边。

换句话说，因为该图中涉及的边比G2图所描述的边还多，所以DiGraphMatcher认为边的集合E'是而不是等于N'中E相关节点中的边的子集。

相反，E'中的边是N'中与E相关的节点中的边集的子集，因此networkx将其称为单态。

为了更好地说明这一点，请考虑以下内容：

from networkx.algorithms.isomorphism import DiGraphMatcher
G1 = nx.DiGraph()
G1.add_edge(1, 2)
G1.add_edge(2, 1)
G2 = nx.DiGraph()
G2.add_edge(1, 2)
print(list(DiGraphMatcher(G1, G2).subgraph_isomorphisms_iter()))
print(list(DiGraphMatcher(G1, G2).subgraph_monomorphisms_iter()))

这将打印以下内容：

[{1: 1, 2: 2}, {2: 1, 1: 2}] # subgraph MONOmorphism
[]                           # subgraph  ISOmorphism