IsomorphicGraphQ issues?

Question

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

.

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.

Answer 1

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"]

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

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}}]} *)