igraph-help
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Graph isomorphism missed?


From: Louis Aslett
Subject: Re: [igraph] Graph isomorphism missed?
Date: Wed, 12 Sep 2012 16:23:58 +0100

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?

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



reply via email to

[Prev in Thread] Current Thread [Next in Thread]