Re: [igraph] Graph isomorphism missed?

[Gábor Csárdi]

Oh, indeed, sorry, my bad. I am afraid that this is this bug then:
https://bugs.launchpad.net/igraph/+bug/1032819

Gabor

On Wed, Sep 12, 2012 at 10:53 AM, Louis Aslett <address@hidden> wrote:
> Thanks, yes that's what I meant in my rather imperfect rambling
> definition!  In the example I sent in the first mail, nodes 1 and 4
> are colour 1; nodes 2 and 3 are colour 2.  My understanding is that
> simply switching labels within colours is an isomorphism?
>
> Thanks,
>
> Louis
>
>
> On 12 September 2012 14:49, Gábor Csárdi <address@hidden> wrote:
>> Well, that's not the definition we used for color isomorphism. What we
>> do is that in the mapping of the vertices, vertex 'v' can only be
>> mapped to vertex 'w' if they have the same color. My understanding is
>> that this is the "common" definition of isomorphism between colored
>> graphs, but I might be wrong.
>>
>> Gabor
>>
>> On Wed, Sep 12, 2012 at 9:22 AM, Louis Aslett <address@hidden> wrote:
>>> I might have misunderstood coloured graph isomorphisms, but from my
>>> understanding the following two graphs should be isomorphic (code in
>>> R).
>>>
>>> g1 <- graph.formula(1 -- 2:3, 2 -- 3, 3 -- 4)
>>> g2 <- graph.formula(1 -- 2, 2 -- 3, 2:3 -- 4)
>>> graph.count.isomorphisms.vf2(g1, g2, vertex.color1=c(1,2,2,1),
>>> vertex.color2=c(1,2,2,1))
>>>
>>> My understanding of coloured isomorphism is that two bijections are
>>> looked for f and g, say, such that f applied to one colour or vertex
>>> and g to the other results in equivalent adjacency to the original
>>> graph.  In this case, bijection f which switches 1 and 4, and another
>>> g which switches 2 and 3 does the job (I think).  However, the
>>> function says there are no isomorphisms.
>>>
>>> Any thoughts (or corrections to my understanding of coloured
>>> isomorphism) appreciated!
>>>
>>> Louis
>>>
>>> _______________________________________________
>>> igraph-help mailing list
>>> address@hidden
>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>>
>>
>> --
>> Gabor Csardi <address@hidden>     MTA KFKI RMKI
>>
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI