Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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 Narain 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
    
@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
add comment

1 Answer 1

You can use this package to call igraph through RLink. igraph does support multi-edges. After setting up the package, do

edgelist1 = {{1, 2}, {2, 3}, {3, 4}, {4, 1}, {1, 2}, {1, 4}}

GraphPlot[Rule @@@ edgelist1]

(* see the multiple edges *)

This is a bit more complex than passing a graph object because in Mathematica you can't construct a graph with multi-edges (as you discovered). So we use IGraphR's intermediary representation:

igobj = RObject[edgelist1, RAttributes["mmaDirectedGraph" :> {False}]]

Then call igraph:

IGraph["graph.isomorphic"][igobj, igobj]

(* ==> True *)
share|improve this answer
add comment

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.