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

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

1 голос
/ 23 марта 2020

У меня есть большой граф, в котором я хочу найти изоморфизм подграфа, используя встроенный алгоритм 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())

1 Ответ

2 голосов
/ 24 марта 2020

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

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

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

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

(взято из сетевой строки комментарии к коду .)

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

Если 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
...