6
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – m_goldberg
    Nov 17, 2012 at 5:32
  • 2
    $\begingroup$ 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? $\endgroup$
    – 9527
    Nov 17, 2012 at 5:54
  • $\begingroup$ 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. $\endgroup$
    – Szabolcs
    Feb 11, 2013 at 21:51

3 Answers 3

9
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – 9527
    Sep 6, 2013 at 7:01
  • $\begingroup$ That localization of $ContextPath! +1 $\endgroup$
    – ssch
    Nov 8, 2013 at 15:03
6
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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! $\endgroup$ Mar 20, 2013 at 18:54
  • 1
    $\begingroup$ @MarkMcClure Here's a package that is a spiritual successor of the project (even though it's a reimplementation): mathematica.stackexchange.com/a/97233/12 :-) $\endgroup$
    – Szabolcs
    Oct 17, 2015 at 11:48
  • $\begingroup$ Thanks for the info! I've not been using Mathematica of late but, if I find myself needing to study graph theory within Mathematica at some point, I'm sure I'll have a look. $\endgroup$ Oct 23, 2015 at 11:40
2
$\begingroup$

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]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.