Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
6  
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. – Rahul Oct 14 '12 at 2:53
    
Clever. I shall give this a go and if successful, make a little wrapper function. – jlv Oct 14 '12 at 3:05
1  
@Rahul Narain Dang. I was going to suggest that. Now I have to unpat myself on the back. – Daniel Lichtblau Oct 14 '12 at 16:26

IGraph/M 0.1.3 or later supports multigraph isomorphism testing directly.

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

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|>} *)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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