Graphviz files and graph ismomorphism

Question

The problem is the following: given two bipartite directed graphs represented in .dot files, is there a tool which can check if the two graphs are isomorphic?

Answer 1

There are tools for checking whether two graphs are isomorphic or not. One possibility is a library called igraph, which has higher level interfaces to R and Python. Unfortunately igraph cannot read DOT files at the moment, so you will have to convert your graph to some other format (e.g., a standard edge list format will do). After conversion, you can do something like this in Python:

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

Another choice is NetworkX which is also a Python package. It can read DOT files natively, but it is implemented in pure Python, hence it tends to be slower than igraph which is mostly implemented in C. So, in general, you will probably be better off with NetworkX if your graphs are relatively small or if they are not likely to be isomorphic, since the latter case usually turns out early when one checks the degree distributions of the two graphs. (If they are isomorphic, the degree distributions must be equal). If the two graphs are large and they are expected to be isomorphic, you are probably better off with igraph, since proving isomorphy is computationally more intensive in this case.

Answer 2

Graphviz is a layout application; however, in python at least, there is a graph analysis library closely integrated with Graphviz, which is called 'Networkx'.

In general, whether you ought to use Networkx or another graph analysis library is probably just a matter of personal choice; however, in this case, Networkx has one significant advantage over other graph analysis libraries, which is that it can read dot files directly (not exactly native support, but it translates them to its native graph object).

Networkx is straightforward to install (binaries for the major OSs), and even easier if you have installed 'Easy Install' with 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)