Why are some of the isomorphisms not bijective?
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]
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}