NetworkX DiGraphMatcher не возвращает результатов на ориентированных графах?

У меня есть большой граф, в котором я хочу найти изоморфизм подграфа, используя встроенный алгоритм VF2 в NetworkX. И графы "стог сена", и "иглы" являются направленными. Возьмем следующий тривиальный пример:

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

Пример кода неориентированного графа (заменяет все 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())

python graph networkx isomorphism
person j6m8    schedule 23.03.2020    source источник
comment
В вашем примере и DiGraphMatcher, и GraphMatcher возвращают пустой список на моем компьютере.   -  person Andy L.    schedule 23.03.2020
comment
@AndyL. только что добавил пример кода неориентированного графа, спасибо за проверку!   -  person j6m8    schedule 24.03.2020

Ответы (1)


arrow_upward
2
arrow_downward

Отвечая на свой вопрос после многих часов печали. Я надеялся, что это будет интересный технический вопрос. Оказывается, это банальный номенклатурный вопрос!

NetworkX определяет изоморфизм подграфов следующим образом:

Если G '= (N', E ') - подграф, индуцированный узлами, то:

  • N 'является подмножеством N
  • E '- это подмножество ребер в E, связывающих узлы в N'

(Взято из встроенных комментариев кода networkx. )

Он определяет морфизм моно следующим образом:

Если G '= (N', E ') - мономорфизм, то:

  • N 'является подмножеством N
  • E '- это подмножество множества ребер в E, связывающих узлы в N'

И далее примечания:

Обратите внимание, что если G 'является индуцированным узлами подграфом G, то это всегда мономорфизм подграфа G, но обратное не всегда верно, поскольку мономорфизм может иметь меньше ребер.

Другими словами, поскольку в этом графе участвуют другие ребра, чем описанные 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
person j6m8    schedule 23.03.2020