NetworkX DiGraphMatcher returns 没有关于有向图的结果？

Question

我有一个大图，我想在其中使用 NetworkX 中内置的 VF2 算法找到子图同构。 'haystack' 和 'needle' 图都是有向的。举以下简单的例子：

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())

最后一行 return 是一个空列表 []。

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

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

版本：

Python: 3.7.7
NetworkX: 2.4

示例无向图代码（将所有DiGraph替换为Graph，否则相同）：

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 定义子图同构如下：

If G'=(N',E') is a node-induced subgraph, then:

N' is a subset of N

E' is the subset of edges in E relating nodes in N'

（取自 networkx 内联 code comments。）

它定义了一个mono 态射如下：

If G'=(N',E') is a monomorphism, then:

N' is a subset of N

E' is a subset of the set of edges in E relating nodes in N'

此外，注释：

Note that if G' is a node-induced subgraph of G, then it is always a subgraph monomorphism of G, but the opposite is not always true, as a monomorphism can have fewer edges.

换句话说，因为除了 G2 图所描述的以外，该图中还涉及其他边，因此 DiGraphMatcher 认为边集 E' 是不等于E中边的子集相关节点在N'.

相反，E' 中的边是 E 中与 N' 中的节点相关的边集的子集，因此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

NetworkX DiGraphMatcher returns 没有关于有向图的结果？

NetworkX DiGraphMatcher returns no results on directed graphs?

python

graph

networkx

isomorphism