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?

$\endgroup$
  • $\begingroup$ Given the example of Compress/Uncompress I agree that this is a bug and I added that tag accordingly. $\endgroup$ – Mr.Wizard Jul 19 '15 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 Jul 19 '15 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 Jul 19 '15 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 Jul 20 '15 at 17:15
  • $\begingroup$ @alancalvitti is this poetry? $\endgroup$ – shrx Oct 16 '15 at 12:13
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 *)
$\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.