Re: [igraph] Graph isomorphism missed?

[Louis Aslett]

Fantastic!  Compiled the nightly from source and can confirm that the
code I provided at the start of the thread now correctly reports 1
instead of 0 isomorphisms.

I'm a very happy chap tonight, thanks!

Louis


On 12 September 2012 16:29, Gábor Csárdi <address@hidden> wrote:
> 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
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help