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？

版本：

• 蟒蛇：3.7.7
• 网络X：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

经过几个小时的悲伤之后回答我自己的问题。我希望这将是一个有趣的技术问题。事实证明这只是一个普通的命名问题！

\n\n

NetworkX 定义子图同构如下：

\n\n

\n

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

\n\n

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

\n

\n\n

（摘自networkx内联代码注释。）

\n\n

它定义了一个单态\xe2\x80\x8b 态射如下：

\n\n

\n

如果 G\'=(N\',E\') 是单态，则：

\n\n

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

\n

\n\n

进一步指出：

\n\n

\n

请注意，如果 G\' 是 G 的节点诱导子图，则它始终是 G 的子图单态，但反之并不总是如此，因为单态可以具有更少的边。

\n

\n\n

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

\n\n

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

\n\n

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

\n\n

from networkx.algorithms.isomorphism import DiGraphMatcher\n\nG1 = nx.DiGraph()\nG1.add_edge(1, 2)\nG1.add_edge(2, 1)\n\nG2 = nx.DiGraph()\nG2.add_edge(1, 2)\n\nprint(list(DiGraphMatcher(G1, G2).subgraph_isomorphisms_iter()))\nprint(list(DiGraphMatcher(G1, G2).subgraph_monomorphisms_iter()))\n

\n\n

这将打印以下内容：

\n\n

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

\n