Re: [igraph] an igraph isomorphism problem

[Tamás Nepusz]

> using g1.isomorphic_vf2( g2, ... ... , return_mapping_12=True ), we'll get 
> this result: (True,[3,2,1],None), because their in and out degrees match. but 
> the edge multiplicities do not match at all. that means edge_color1 and 
> edge_color2 options are ignored for some unknown reason( is that possible to 
> be a bug? ).
You are right, this is a bug and it occurs only with the Python interface, and 
only if you use isomorphic_vf2. I have recently committed a fix into our 
repository:

https://github.com/igraph/igraph/commit/38b76ddee419053cbb8b3428d32f22adb6bcf483

If you compiled the Python interface of igraph from source, the easiest is 
probably to make the same change yourself (it involves changing a single line 
in src/graphobject.c) and then recompile the Python interface. Alternatively, 
there are two workarounds that you can use:

1. Instead of isomorphic_vf2, use count_isomorphisms_vf2, which is not affected 
by this bug. count_isomorphisms_vf2 is slower if there exist many isomorphisms 
between the two graphs, but otherwise it should be comparable to isomorphic_vf2 
in terms of speed.

2. isomorphic_vf2 accepts a parameter named edge_compat_fn, which must be a 
function that decides whether two edges are compatible with each other. Create 
a function similar to the one below and pass that to isomorphic_vf2 in the 
edge_compat_fn parameter:

def are_edges_compatible(g1, g2, i, j):
    return g1.es[i]["multiplicity"] == g2.es[j]["multiplicity"]

This will probably be a bit slower than using isomorphic_vf2 with the proper 
fix I introduced above because the execution has to return from the C layer to 
the Python layer every time two edges are matched to each other (in order to 
execute the are_edges_compatible) function; on the other hand, it will stop at 
the first isomorphism found, unlike count_isomorphisms_vf2, which would 
enumerate all isomorphisms.

> I have tried Mathematica-combinatorica` package and the NetworkX, and they 
> both have full support for multi-graph calculation. [...] I may face tens of 
> billions of graphs, so igraph is my only choice and hope. I'm wondering why 
> it doesn't have native support for multigraphs.
We use third-party implementations of isomorphism algorithms in igraph; igraph 
0.6 includes the BLISS and VF2 isomorphism algorithms, neither of these 
supports multigraphs and we haven't added that, so that's the reason. 

All the best,
-- 
Tamas