[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] an igraph isomorphism problem
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] an igraph isomorphism problem |
Date: |
Sat, 24 Aug 2013 21:52:59 +0200 |
> 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
- [igraph] an igraph isomorphism problem, zhouda, 2013/08/21
- Re: [igraph] an igraph isomorphism problem, Gábor Csárdi, 2013/08/21
- Re: [igraph] an igraph isomorphism problem, zhouda, 2013/08/21
- Re: [igraph] an igraph isomorphism problem, Tamás Nepusz, 2013/08/22
- Re: [igraph] an igraph isomorphism problem, zhouda, 2013/08/23
- Re: [igraph] an igraph isomorphism problem, Tamás Nepusz, 2013/08/23
- Re: [igraph] an igraph isomorphism problem, zhouda, 2013/08/24
- Re: [igraph] an igraph isomorphism problem,
Tamás Nepusz <=
- Re: [igraph] an igraph isomorphism problem, zhouda, 2013/08/25