6
$\begingroup$

Bug introduced in 11.2 and fixed in 11.3.
This bug is specific to Windows.


When I evaluate

ga = Graph[{1 <-> 2, 2 <-> 3}];gb = Graph[{1 <-> 3, 2 <-> 3}];IsomorphicGraphQ[ga, gb],

Mathematica returns

enter image description here.

It does return False when I evaluate IsomorphicGraphQ[x,y].

The same occurs when I try to evaluate the functions given in the documentation.

Is it a know/recent issue ? I have found nothing online. I am using version 11.2 on Windows 64-bits.

Thank you.

$\endgroup$
  • $\begingroup$ I experienced the IsomorphicGraphQ issue as well, only on my Windows machine. I do not experience it on macOS. I am almost 100% certain it is a bug with Mathematica 11.2 on Windows. $\endgroup$ – user6014 Feb 16 '18 at 13:47
  • $\begingroup$ M11.3 is said to be nearing release. I'd expect such a serious bug to be fixed by then (but I do not know). $\endgroup$ – Szabolcs Feb 16 '18 at 14:37
  • $\begingroup$ Yes, it has been fixed in M11.3 $\endgroup$ – user58955 Mar 23 '18 at 10:51
4
$\begingroup$

IsomorphicGraphQ not evaluating is a known bug in Mathematica 11.2 for Windows. The bug is not present in older versions (<= 11.1) or in M11.2 for Mac and Linux.

As a workaround, you can use a different version of Mathematica, or you can use my IGraph/M package, which has multiple isomorphism testing functions. The drawback is that all IGraph/M functions have an overhead due to the need to convert the graph to the igraph format. Because of this, IGraph/M's isomorphism functions will be considerably slower than the built-in ones for small graphs. For big graphs (or for hard problems) IGBlissIsomorphicQ will be faster than the built-in function.


Examples:

g1 = IGShorthand["1-2-3-4-1"]

enter image description here

g2 = IGShorthand["a-d, a-b, d-c, b-c"]

enter image description here

IGIsomorphicQ[g1, g2]
(* True *)

IGBlissGetIsomorphism[g1, g2]
(* {<|1 -> "a", 2 -> "d", 3 -> "c", 4 -> "b"|>} *)

IGBlissAutomorphismGroup[g1]
(* {{1, 4, 3, 2}, {2, 1, 4, 3}} *)

GroupElements@PermutationGroup[%]
(* {Cycles[{}], Cycles[{{2, 4}}], Cycles[{{1, 2}, {3, 4}}], 
 Cycles[{{1, 2, 3, 4}}], Cycles[{{1, 3}}], Cycles[{{1, 3}, {2, 4}}], 
 Cycles[{{1, 4, 3, 2}}], Cycles[{{1, 4}, {2, 3}}]} *)
$\endgroup$
  • $\begingroup$ Indeed. I have edited the original question accordingly. Thank you. $\endgroup$ – Matthieu Jacquemet Feb 16 '18 at 14:11

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.