How to find all graph isomorphisms in FindGraphIsomorphism

Question

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?

Answer 1

Alternatively, you can use the Combinatorica package.

Block[{$ContextPath}, 
 Needs["Combinatorica`"]; 
 Needs["GraphUtilities`"]]

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

Combinatorica`Automorphisms@GraphUtilities`ToCombinatoricaGraph[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 System`Graph. However, the GraphUtilities`ToCombinatoricaGraph 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.

---

Update:

At least in version 10.0 and later, FindGraphIsomorphism[g1, g2, All] will correctly return all isomorphisms.

Once we have one isomorphism from g1 to g2, finding the rest is equivalent to finding the elements of the automorphism group of g1 (or g2). This can be done using

GroupElements@GraphAutomorphismGroup[g1]

The elements are returned as permutations in the cycles representation. It is convenient to transform them to other representation either by using Permute with VertexList[g1], or by using PermutationList (see two-argument form).

Since the automorphism group may have a very large number of elements, it is often more convenient to work with the group directly (GraphAutomorphismGroup and group theory functions) rather than explicitly listing its elements (FindGraphIsomorphism).

Answer 2

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.

Answer 3

Update: Be sure to also check out IGraph/M.

IGVF2FindIsomorphisms[graph, graph]

We can also get the automorphism group:

IGBlissAutomorphismGroup[graph]
(* {{2, 1}} *)

GroupElements@PermutationGroup[%]
(* {Cycles[{}], Cycles[{{1, 2}}]} *)

PermutationList[#, 2] & /@ %
(* {{1, 2}, {2, 1}} *)

Mathematica 10 also has this functionality built in:

$Version
(* "10.3.0 for Mac OS X x86 (64-bit) (October 9, 2015)" *)

FindGraphIsomorphism[graph, graph, All]
(* {<|1 -> 1, 2 -> 2|>, <|1 -> 2, 2 -> 1|>} *)

GraphAutomorphismGroup[graph]
(* PermutationGroup[{Cycles[{{1, 2}}]}] *)

---

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]