# Isomorphisms for graphs with loops and multiple edges

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.

• You could replace each edge with an edge-vertex-edge path, converting your multigraph into a unique simple graph which you can compare for isomorphism.
– user484
Oct 14, 2012 at 2:53
• Clever. I shall give this a go and if successful, make a little wrapper function. Oct 14, 2012 at 3:05
• @Rahul Narain Dang. I was going to suggest that. Now I have to unpat myself on the back. Oct 14, 2012 at 16:26

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|>} *)
`
• Is there a way to test isomorphism of Edge-colored and Vertex-colored multigraphs with IGraphM ? Dec 12, 2017 at 12:56
• The approach given bellow can deal with multi-graphs only non-simple graphs. Is there any way around this? Aug 3, 2020 at 18:19
• @jonaprieto I don't understand what "can deal with multi-graphs only non-simple graphs" means. Aug 3, 2020 at 18:22
• Try a graph with multiple edges and some loops. It won't work or am I missing something? trying to compute Aut(Bn), where Bn is the graph of n-loops and one vertex. Aug 3, 2020 at 18:24
• @jonaprieto Please give a complete example and explain what you mean by "does not work". It's probably best to ask a new question. Aug 3, 2020 at 18:26