# How to find all graph isomorphisms in FindGraphIsomorphism

I found the second definition of the function FindGraphIsomorphism not working.

Here's the definition Mathematica 8 gives:

FindGraphIsomorphism[g1,g2] finds an isomorphism that maps the graph g1 to g2 by renaming vertices. FindGraphIsomorphism[g1,g2,n] finds at most n isomorphisms.

I tried the following two tests. Define a simple graph by

graph = AdjacencyGraph[{{1,0},{0,1}}];


Then running FindGraphIsomorphism[graph,graph] yields {1->1, 2->2}, this is good.

but running

FindGraphIsomorphism[graph,graph,2]


makes the Mathematica kernel dead. So I tried another graph,

graph = AdjacencyGraph[{{1,1},{1,1}}];


Running FindGraphIsomorphism[graph,graph,2] yielded error message:

FindGraphIsomorphism::nonopt: Options expected (instead of 2) beyond position 2 in FindGraphIsomorphism[graph,graph,2]. An option must be a rule or a list of rules.

My conclusion is that FindGraphIsomorphism[g1,g2,n] is a bug. Or am I wrong somewhere? What should I do to obtain a result like:

Input: FindGraphIsomorphism[graph,graph,2]

Output: {{1->1,2->2}, {1->2,2->1}}

Update:

It seems that the latest version of Mathematica does not support the third argument n in FindGraphIsomorphism. The form FindGraphIsomorphism[g1,g2,n] is no longer in the online documentation center. However, it exists in my older version 8.0.0, but fails to work.

I still want to know if there is any way to make it work: FindGraphIsomorphism[g1,g2] gives one isomorphism, but how to get the list of more than one, or, all isomorphisms?

-
I find nothing in the documentation of Mathematica v.8.0.4 that indicates that FindGraphIsomorphism takes a third argument. What version are you running? –  m_goldberg Nov 17 '12 at 5:32
I am running version 8.0.0.0. You are right, I checked the online documentation center at the link reference.wolfram.com/mathematica/ref/FindGraphIsomorphism.html, and they don't have the third argument in the description. It seems that they tried to allow this extra argument in version 8.0.0, but took it back later. Maybe it is too hard to give the list of more than one isomorphisms? –  9527 Nov 17 '12 at 5:54
The igraph library can compute all isomorphisms, or just count them. You may try using that library. If you are running Mathematica on Windows, and you would like to access igraph from it, you could use RLink and the R igraph interface. –  Szabolcs Feb 11 '13 at 21:51

Alternatively, you can use the Combinatorica package.

Block[{$ContextPath}, Needs["Combinatorica"]; Needs["GraphUtilities"]] graph = AdjacencyGraph[{{1, 0}, {0, 1}}]; CombinatoricaAutomorphisms@GraphUtilitiesToCombinatoricaGraph[graph] (* ==> {{1, 2}, {2, 1}} *)  The return values are to be interpreted as vertex permutations. Note: In this answer I load Combinatorica without adding it to the context path (see Block above), to avoid masking SystemGraph. However, the GraphUtilitiesToCombinatoricaGraph function will unfortunately re-add it to the context path every time it is called. If this bothers you, you can either modify the GraphUtilities package or wrap the culprit function using the Villegas-Gayley trick to restore the original context path after the function has run. - Good point to use GraphUtilities\ToCombinatoricaGraph. I noticed that similar to Automorphisms, the command Isomorphism[g1,g2,All] in Combinatorica gives all isomorphisms between the graphs g1 and g2. – 9527 Sep 6 '13 at 7:01 That localization of $ContextPath! +1 –  ssch Nov 8 '13 at 15:03

With apologies for the third, yet again independent answer, I recommend calling igraph through RLink using this package (only if you have v9 of Mathematica). Please see the instructions on how to set up the package, then you can do:

graph = AdjacencyGraph[{{1,0},{0,1}}];
res = IGraph["graph.get.isomorphisms.vf2"][graph, graph]

Round[res+1]


This will give you the list of mappings (automorphism).

Some graphs have a huge number of these, so before retrieving all automorphisms, you can count them using IGraph["graph.count.isomorphisms.vf2"][graph, graph]

-

I noticed that here you are looking for automorphisms. You can use Mark McClure's igraph link to compute these. I put an updated version of the link here. This version will work with igraph 0.6.5.

The package is a little rough around the edges, but it'll do the job.

To get the package working, you'll need to compile the C source first. On OS X, this is how to do it:

1. Install igraph. If you have MacPorts installed, this is as simple as sudo port install igraph

2. Go to IGLink/bin/Source and edit the Makefile. Make sure the paths to Mathematica are correct.

3. From the terminal, run make in the same folder.

4. Copy the generated igraph binary to IGLink/bin/MacOSX.

After loading IGLink (please see the included IGraph.nb on how to load it), you can do

graph = AdjacencyGraph[{{1, 0}, {0, 1}}];

(* convert to a suitable format for IGLink *)
edges = Rule @@@ EdgeList[graph];

IGAutomorphisms[edges]

(* ==> {{1 -> 1, 2 -> 2}, {1 -> 2, 2 -> 1}} *)


If you have a bigger graph, you may want to check IGAutomorphismCount[edges] to make sure IGAutomorphisms won't be returning a list that is two big to handle.

Also note that the graphs are considered to be undirected even though the edges are represented using Rule`.

-
Awesome! Although it worked for my purposes "Rough around the edges" is a polite description. The package was originally written to help some REU students solve some specific questions in graph theory. Thus, the current available functionality is small and chosen for a specific task. But it is a start and should be easy to add to, for those familiar with C programming and MathLink. And, thanks to Szabolcs for getting the package to work with the latest version of igraph! –  Mark McClure Mar 20 '13 at 18:54