5
$\begingroup$

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,

two multigraphs

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.

graphs with self-loops

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.

$\endgroup$
3
  • 7
    $\begingroup$ 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. $\endgroup$
    – user484
    Oct 14, 2012 at 2:53
  • $\begingroup$ Clever. I shall give this a go and if successful, make a little wrapper function. $\endgroup$ Oct 14, 2012 at 3:05
  • 1
    $\begingroup$ @Rahul Narain Dang. I was going to suggest that. Now I have to unpat myself on the back. $\endgroup$ Oct 14, 2012 at 16:26

1 Answer 1

6
$\begingroup$

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|>} *)
$\endgroup$
10
  • $\begingroup$ Is there a way to test isomorphism of Edge-colored and Vertex-colored multigraphs with IGraphM ? $\endgroup$
    – yarchik
    Dec 12, 2017 at 12:56
  • $\begingroup$ The approach given bellow can deal with multi-graphs only non-simple graphs. Is there any way around this? $\endgroup$ Aug 3, 2020 at 18:19
  • $\begingroup$ @jonaprieto I don't understand what "can deal with multi-graphs only non-simple graphs" means. $\endgroup$
    – Szabolcs
    Aug 3, 2020 at 18:22
  • $\begingroup$ 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. $\endgroup$ Aug 3, 2020 at 18:24
  • $\begingroup$ @jonaprieto Please give a complete example and explain what you mean by "does not work". It's probably best to ask a new question. $\endgroup$
    – Szabolcs
    Aug 3, 2020 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.