4
$\begingroup$

If I run IsomorphicGraphQ on the following graphs, I get an error I don't understand:

ga = Graph[{1 <-> 2, 1 <-> 2, 2 <-> 3}];
gb = Graph[{a <-> b, a <-> b, b <-> c}];
IsomorphicGraphQ[ga, gb]

This gives:

"IsomorphicGraphQ::ngen: The generalized IsomorphicGraphQ[Graph[<3>,<3>],Graph[<3>,<3>]] is not implemented"

The above graphs have multiple edges between the same nodes in them. If I remove these, then the error goes away:

ga = Graph[{1 <-> 2, 2 <-> 3}];
gb = Graph[{a <-> b, b <-> c}];
IsomorphicGraphQ[ga, gb]

returns True.

Is this really a limitation of IsomorphicGraphQ or am I misunderstanding something?

I'm running version 10.0.0.0 on Linux x86 (64 bit).

$\endgroup$
4
  • $\begingroup$ An even shorter example that gives the same error message is ga = Graph[{1 <-> 2, 1 <-> 2}]; IsomorphicGraphQ[ga, ga]. I'm using 10.0.1 Windows 64-bit. I'm not sure why this occurs; maybe it can't handle multiple edges between two vertices? The documentation doesn't give any examples of multiple-edge graphs, but doesn't say it can't handle them. Strange, does anyone else know what might be afoot here? $\endgroup$ Jan 8, 2015 at 19:50
  • $\begingroup$ Ray, regardless of this specific problem, you really should upgrade to 10.0.2. It has lots of fixes compared to 10.0.0. $\endgroup$
    – Szabolcs
    Jan 12, 2015 at 15:09
  • $\begingroup$ Will do, thanks Szabolcs. $\endgroup$
    – Ray
    Jan 12, 2015 at 19:42
  • $\begingroup$ The answer I provided earlier was incorrect. Please see this one instead. $\endgroup$
    – Szabolcs
    Oct 17, 2015 at 9:48

1 Answer 1

4
$\begingroup$

IsomorphicGraphQ and CanonicalGraph don't yet support multigraphs (graphs that have more than one edge spanning two nodes). It's a known limitation and I believe it will come in a future release.

$\endgroup$
4
  • $\begingroup$ Thanks for the info. By any chance, is this limitation mentioned anywhere in the documentation, or is this undocumented? $\endgroup$ Jan 8, 2015 at 20:18
  • $\begingroup$ I personally couldn't find it. My source of information is being a WRI employee :) $\endgroup$
    – Carlo
    Jan 9, 2015 at 12:57
  • $\begingroup$ The documentation says, "IsomorphicGraphQ works for any graph object including Graph, DirectedGraph, TreeGraph, etc." This implies that it should work for multigraphs as well. Could you fix the documentation on this? $\endgroup$
    – Szabolcs
    Jan 12, 2015 at 15:09
  • $\begingroup$ There's an open bug. It should get fixed in the next release. $\endgroup$
    – Carlo
    Jan 14, 2015 at 19:07

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