时间戳

首页 > 解决方案 > NetworkX DiGraphMatcher 在有向图上不返回结果？

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

问题描述

我有一个大图，我想在其中使用 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吗？

版本：

示例无向图代码（全部替换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())

标签： pythongraphnetworkxisomorphism

解决方案

经过数小时的悲伤后回答我自己的问题。我希望这将是一个有趣的技术问题。原来这只是一个普通的命名问题！

NetworkX 将子图同构定义如下：

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

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

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

它定义了一个单态如下：

如果 G'=(N',E') 是一个单态，那么：

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

此外，请注意：

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

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

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

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

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

推荐阅读