Re: [igraph] Graph isomorphism missed?

[Gábor Csárdi]

On Wed, Sep 12, 2012 at 11:23 AM, Louis Aslett <address@hidden> wrote:
> Ok, thanks -- yes I can reproduce the bug linked so it is present in
> my R version.  I note the bug says fixed now ... any idea when you
> plan to push out an updated R package?

Soon. There are some annoying bugs in the 0.6-2 version, so we'll try
to do a release very soon, we'll just fix some more bugs.

As usual a nightly build is available at
https://code.google.com/p/igraph/downloads/list

Best,
G.

> Thanks again for a great piece of software,
>
> Louis
>
>
> On 12 September 2012 16:00, Gábor Csárdi <address@hidden> wrote:
>> 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
>>
>> _______________________________________________
>> 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