Графвиз файлов и граф изоморфизм - PullRequest
Новая
       11

Графвиз файлов и граф изоморфизм

2 голосов
/ 16 апреля 2010

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

Ответы [ 2 ]

2 голосов
/ 17 апреля 2010

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

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

Networkx прост в установке (двоичные файлы для основных ОС), и даже проще, если вы установили ' Easy Install ' с python: 

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)
0 голосов
/ 16 апреля 2010

Существуют инструменты для проверки того, являются ли два графика изоморфными или нет. Одной из возможностей является библиотека под названием 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 , поскольку в этом случае доказательство изоморфности в вычислительном отношении более интенсивно.

...