14
$\begingroup$

Bug introduced in 9.0.1 or earlier and fixed in 11.0.1

Consider the following two graphs:

g1 = Graph[{1, 2, 3}, {}];

g2 = SimpleGraph@Graph[{1, 2, 3}, {1 <-> 1}];

They are clearly the same thing because SimpleGraph will remove the self loop (only edge) from g2.

Yet IsomorphicGraphQ disagrees:

IsomorphicGraphQ[g1, g2]

(* False *)

I believe this is a bug and it exists in all of 9.0.1 through to 10.4.0.

Is there a workaround?

Improve this question
$\endgroup$
6
  • $\begingroup$ Given the example of Compress/Uncompress I agree that this is a bug and I added that tag accordingly. $\endgroup$
    – Mr.Wizard
    Commented Jul 19, 2015 at 10:55
  • $\begingroup$ @Mr.Wizard, given your geo, any chance you can be in Pasadena early Aug for a day? ... Szabolcs, I'd extend the same invite but you're a bit further @ away this time. $\endgroup$
    – alancalvitti
    Commented Jul 19, 2015 at 12:30
  • 1
    $\begingroup$ @alancalvitti I don't think that will be possible but I must say I am curious why you ask. $\endgroup$
    – Mr.Wizard
    Commented Jul 19, 2015 at 12:53
  • $\begingroup$ @Mr.Wizard, you already know why: software is eating the world and M.SE is a global lever. Take a look at some of the tech in this useful fiction like Ghost Fleet >> bit.ly/1e7MJ38. If you like it I'll msg you a 2-part key w/ info. $\endgroup$
    – alancalvitti
    Commented Jul 20, 2015 at 17:15
  • $\begingroup$ @alancalvitti is this poetry? $\endgroup$
    – shrx
    Commented Oct 16, 2015 at 12:13

1 Answer 1

Reset to default
13
$\begingroup$

A simple workaround is to re-build the graph object by cycling it through some other representation. Here are two possible solutions:

rebuildGraph[g_] := Uncompress@Compress[g] (* solution 1 *)
rebuildGraph[g_] := Graph[VertexList[g], EdgeList[g]] (* solution 2 destroys properties but it's fine for isomorphism testing purposes *)

isomorphicGraphQ[g1_, g2_] := 
 IsomorphicGraphQ[rebuildGraph[g1], rebuildGraph[g2]]

Now this gives a correct result:

isomorphicGraphQ[g1, g2]
(* True *)
Improve this answer
$\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.