Isomorphisms for graphs with loops and multiple edges

Question

I am working with graphs with multiple edges and loops, and I want to eliminate all isomorphic graphs from a long list I've generated. The FindGraphIsomorphism function is very nice, but only works for simple graphs. I'm looking to find such a function or its equivalent for multigraphs. For example,

Is there possibly a third-party package, or maybe even an external program that would find such graph isomorphisms?

Also, is it possible to compare graphics objects in Mathematica, to see whether they are similar? I have tried SameQ, but to no avail.

I am assuming this is the result because Mathematica plots the graphs with floating-point values, so it is impossible to have two identical graphs like this. So is there a function that looks at the similarity between two graphics objects? I think something like that might do the trick for me in most cases.

Answer 1

IGraph/M 0.1.3 or later supports multigraph isomorphism testing directly. Note: Version 0.3.110 fixes important bugs in multigraph (sub-)isomorphism. Upgrade to this release or later.

<< IGraphM`

g1 = Graph[{1 -> 3, 1 -> 4, 1 -> 4, 2 -> 3, 2 -> 3, 2 -> 4}]

g2 = Graph[{1 -> 2, 1 -> 2, 1 -> 3, 2 -> 4, 3 -> 4, 3 -> 4}]

As directed graphs they are not isomorphic:

IGIsomorphicQ[g1, g2]
(* False *)

As undirected ones they are:

g1 = Graph[{1 <-> 3, 1 <-> 4, 1 <-> 4, 2 <-> 3, 2 <-> 3, 2 <-> 4}]

g2 = Graph[{1 <-> 2, 1 <-> 2, 1 <-> 3, 2 <-> 4, 3 <-> 4, 3 <-> 4}]

IGIsomorphicQ[g1, g2]
(* True *)

We can get a specific mapping like so:

IGGetIsomorphism[g1, g2]
(* {<|1 -> 1, 3 -> 3, 4 -> 2, 2 -> 4|>} *)

The implementation is based on igraph's support for edge-colored graphs. Note that at the moment igraph itself (the library underlying IGraph/M) does not support multigraph isomorphism. It won't error on multigraphs, but it may not give correct results. It is important to be aware of this when using igraph from R/Python/C. IGraph/M, the Mathematica interface, does have checks for multigraphs, and can test for multigraph isomorphism by transforming them to edge-coloured simple graphs.

There's no builtin implementation for finding isomorphisms for multigraphs, but we can do the translation to edge-coloured graphs by hand:

asc1 = Counts[Sort /@ EdgeList[g1]]
(* <|1 <-> 3 -> 1, 1 <-> 4 -> 2, 2 <-> 3 -> 2, 2 <-> 4 -> 1|> *)

asc2 = Counts[Sort /@ EdgeList[g2]]
(* <|1 <-> 2 -> 2, 1 <-> 3 -> 1, 2 <-> 4 -> 1, 3 <-> 4 -> 2|> *)

IGVF2FindIsomorphisms[{Graph[VertexList[g1],Keys[asc1]], "EdgeColors" -> asc1}, {Graph[VertexList[g2],Keys[asc2]], "EdgeColors" -> asc2}]
(* {<|1 -> 1, 3 -> 3, 4 -> 2, 2 -> 4|>, <|1 -> 3, 3 -> 1, 4 -> 4, 2 -> 2|>, 
    <|1 -> 2, 3 -> 4, 4 -> 1, 2 -> 3|>, <|1 -> 4, 3 -> 2, 4 -> 3, 2 -> 1|>} *)