Re: [igraph] Re: [igraph] graph isomorphism

[Gábor Csárdi]

Ulrike, OK, I got it. You can follow the issue here, in case you want
to be notified when this is added:
https://bugs.launchpad.net/igraph/+bug/321508

Btw. you can still use the original VF2 implementation, although for
that you need to program in C.

Best,
Gabor

On Sun, Mar 29, 2009 at 9:49 PM, Ulrike Grömping
<address@hidden> wrote:
> Bhalchandra and Gabor,
>
> although this thread is old (from September 2008), I would like to let you
> know that I would also be very interested in having the subgraph isomorphism
> check pay tribute to colors. It would very nicely solve one of my problems if
> I could define two different types of vertices.
>
> Unfortunately, I can not offer to contribute code, as I am by no means an
> expert in graphs.
>
> Regards, Ulrike
>
> ***********************************************************************
> 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
>
>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM