Файлы Graphviz и изоморфизм графа

Question

Проблема заключается в следующем: учитывая два двунаправленных ориентированных графа, представленных в .dot-файлах, есть ли инструмент, который может проверить, являются ли эти два графика изоморфными?

Answer 1

Graphviz - это приложение макета; однако, по крайней мере, на python существует библиотека графического анализа, тесно интегрированная с Graphviz, которая называется «Networkx».

В целом, следует ли использовать Networkx или другую библиотеку анализа графиков - это, вероятно, вопрос личного выбора; однако в этом случае Networkx имеет одно существенное преимущество перед другими библиотеками анализа графов, а именно: может считывать файлы точечных напрямую (не совсем нативную поддержку, но переводит их на свой собственный объект графа).

NetworkX проста в установке (двоичные файлы для основных операционных систем), и даже легче, если вы установили «Easy Install» с питоном:

easy_install networkx 

import networkx as NX 

# convert dot files to the graph analysis package's native graph object: 
G1 = NX.read_dot("/maindir/mydir/my_bipartite_graph1.dot") 
G2 = NX.read_dot("/maindir/mydir/my_bipartite_graph1.dot") 

# returns 'True'/'False' 
NX.DiGraphMatcher.is_isomorphic(G1 G2) 

Answer 2

Есть инструменты для проверки того, являются ли два графика изоморфными или нет. Одна из возможностей - это библиотека под названием igraph, которая имеет интерфейсы более высокого уровня для R и Python. К сожалению, igraph не может читать файлы DOT на данный момент, поэтому вам нужно будет преобразовать свой график в другой формат (например, будет использоваться стандартный формат списка ребер). После преобразования, вы можете сделать что-то подобное в Python:

>>> from igraph import load 
>>> g = load("my_graph.txt", format="edgelist") 
>>> g2 = load("my_other_graph.txt", format="edgelist") 
>>> g.isomorphic(g2) 
False 

Другой выбор NetworkX который также пакет Python. Он может читать файлы DOT изначально, но он реализован в чистом Python, следовательно, он имеет тенденцию быть медленнее, чем igraph, который в основном реализован в C. Таким образом, в целом вам, вероятно, будет лучше с NetworkX, если ваши графики относительно малы или если они вряд ли будут изоморфны, так как последний случай обычно получается раньше, когда проверяется распределение степеней двух графиков. (Если они изоморфны, распределения степеней должны быть равны). Если два графика велики, и они, как ожидается, будут изоморфны, вам, вероятно, будет лучше с igraph, так как изоморфизм в этом случае будет более вычислительно более интенсивным.