12
$\begingroup$

Bug introduced in 10.4 and fixed in 11.0.1


Mathematica computes all the isomorphisms between graph g1 and g2:

g1 = Graph[{1 <-> 3, 1 <-> 4, 1 <-> 6, 2 <-> 4, 2 <-> 5, 2 <-> 7, 3 <-> 5, 
 3 <-> 8, 4 <-> 9, 5 <-> 10, 6 <-> 7, 6 <-> 10, 7 <-> 8, 8 <-> 9, 
 9 <-> 10}]
g2 = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 5, 5 <-> 1, 2 <-> 6, 6 <-> 7, 
 7 <-> 8, 8 <-> 3, 9 <-> 8, 10 <-> 9, 10 <-> 4, 5 <-> 7, 1 <-> 9, 
 6 <-> 10}]
isos = FindGraphIsomorphism[g1, g2, All]

But looking at some of them confuses me, like isos[[84]] is

<|1 -> 8, 7 -> 10, 10 -> 1, 3 -> 7, 8 -> 6, 9 -> 2, 4 -> 3, 2 -> 4, 5 -> 5|>

This can't be right, here 7->10->1->8->6->? If 8 goes to 6, then what is vertex 6 mapped to? Am I missing something, or is this a problem with FindGraphIsomorphism?

$\endgroup$
  • $\begingroup$ Approving.IsomorphicGraphQ[VertexReplace[g1,Normal[isos[[84]]]],#]&/@{g1,g2} will give False $\endgroup$ – yode May 31 '16 at 17:11
  • $\begingroup$ @yode so should I report as a bug? $\endgroup$ – M.R. May 31 '16 at 17:58
  • $\begingroup$ As a workaround, try IGraph/M. It has superior isomorphism functionality, with many features Mathematica doesn't have and much better performance for large/hard graphs. $\endgroup$ – Szabolcs May 31 '16 at 20:01
8
$\begingroup$

This is a bug. The length of each association returned should be VertexCount[g1], but it isn't.

Length /@ FindGraphIsomorphism[g1, g2, All]
(* {10, 6, 8, 6, 8, 6, 9, 9, 9, 9, 6, 8, 8, 10, 8, 10, 10, 9, \
9, 10, 9, 10, 9, 10, 10, 9, 9, 10, 8, 10, 10, 9, 10, 8, 9, 10, 9, 10, \
9, 10, 10, 9, 8, 10, 9, 10, 8, 10, 10, 10, 10, 9, 8, 9, 10, 10, 6, 9, \
10, 9, 8, 9, 6, 9, 10, 10, 9, 10, 10, 9, 10, 10, 10, 10, 9, 10, 10, \
9, 6, 9, 10, 10, 8, 9, 9, 6, 9, 8, 9, 10, 10, 10, 10, 10, 10, 9, 10, \
10, 9, 10, 9, 8, 10, 10, 9, 6, 9, 10, 10, 9, 10, 10, 10, 10, 9, 8, 9, \
10, 9, 6} *)

The bug is present in M10.4.1 but not in M10.3.1.


As a workaround, try IGraph/M, which has superior isomorphism functionality.

To find all isomorphisms, you can use the VF2 and LAD algorithms in the package.

<<IGraphM`

IGVF2FindIsomorphisms[g1, g2]

IGLADFindSubisomorphisms[g1, g2]

The Bliss algorithm can find one isomorphism:

IGBlissGetIsomorphism[g1, g2]

Or get the number of isomoprhisms:

IGBlissAutomorphismCount[g1]
(* 120 *)

Or get the automorphism group, which can then be used to generate all isomorphisms:

group = PermutationGroup[IGBlissAutomorphismGroup[g2]]

iso = First@IGBlissGetIsomorphism[g1, g2]

AssociationThread[Keys[iso], #] & /@ (Permute[Values[iso], #] &) /@ GroupElements[group]
| improve this answer | |
$\endgroup$
  • $\begingroup$ I have to say this is a wonderful package.Thanks very very much. $\endgroup$ – yode May 31 '16 at 20:30
2
$\begingroup$

I think this is a bug of FindGraphIsomorphism.And you should give a report to Wolfram.This is what my thinking about it.

IsomorphicGraphQ[VertexReplace[g1, Normal[#]], g1] & /@ isos // Counts

<|True -> 64, False -> 56|>


But I still think there are work-around to find the isomorphic graph.This is my solution.

Find the permutation group all of isomorphism

permute = GraphAutomorphismGroup[g1]

PermutationGroup[{Cycles[{{2, 4}, {6, 7}, {8, 10}}], Cycles[{{2, 4,3}, {5, 6, 10, 9, 8, 7}}], Cycles[{{1, 2, 8, 7, 5, 3}, {4, 6,9}}]}]

Then check what we get

ruleYouWant = Rule @@@ Transpose[{VertexList[g1], #}] & /@ 
   Permute[VertexList[g1], permute];
IsomorphicGraphQ[VertexReplace[g1, #], g1] &/@ruleYouWant

{True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True,True}

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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