Re: [igraph] graph isomorphism

[Gábor Csárdi]

Bhalchandra,

no, colored graphs are not supported. They can be easily supported by
the VF2 algorithm, in fact the original VF2 implementation supports
them, so you might just want to use that instead of rewriting it.

In theory this can be added to igraph easily, but in practice my
non-recursive implementation might be not that easy-to-follow. The
function that needs to be modified is 'igraph_isomorphic_function_vf2'
in topology.c, and there is a part that checks that the degrees of the
two (potentially) matching vertices are the same:

      if (VECTOR(indeg1)[cand1] != VECTOR(indeg2)[cand2] ||
          VECTOR(outdeg1)[cand1] != VECTOR(outdeg2)[cand2]) {
        end=1;
      }

Basically this can be extended to check that their "color" is the same
as well. And possibly we could have some optional heuristics that
check that the color distribution is the same in the two graphs,
before running the actual VF2 algorithm.

Gabor

On Fri, Sep 26, 2008 at 8:20 PM, Bhalchandra Thatte <address@hidden> wrote:
> Hi,
> I am not sure if you answered earlier and I missed your reply. So I
> apologize if I am asking again.
> Does the isomorphism program work if the graphs are coloured (so that
> isomorphism should preserve vertex or edge colours). If it does not
> handle coloured graphs, then I will be happy to contribute code to do
> something like that. But I will be slow, much much slower than you
> guys.
> Thanks,
> Bhalchandra Thatte
> Department of Statistics, 1 South Parks Road, University of Oxford,
> Oxford OX1 3TG, United Kingdom
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>