igraph-help
[Top][All Lists]

## Re: [igraph] Cayley Tree

 From: Gábor Csárdi Subject: Re: [igraph] Cayley Tree Date: Wed, 18 Nov 2009 23:26:19 +0100

On Wed, Nov 18, 2009 at 11:17 PM, Marco <address@hidden> wrote:
> Dear Gabor,
>
> thank you for the R code.
>
> I will look into it, even if my R skills are *very* low. :)

Not much Rism in this code, probably the only non-obvious thing is,
that %du% calls graph.disjoint.union() on the two graphs.

G.

> If I don't come up with a pythonic version of this, I will ask you, if
> it is ok with you.
>
> Thank you!
>
> marco
>
> --
> restituiremo il riso ai salici
>
>
>
> On Wed, Nov 18, 2009 at 11:12 PM, Gábor Csárdi <address@hidden> wrote:
>> Yep, but the degree of the root node must be the same as for the other
>> nodes. graph.tree() creates graphs, where the degree of the root is
>> one less.
>>
>> It is not too hard to fix this, with something like:
>>
>> cayley.tree <- function(coord, depth) {
>>  if (depth==0) return(graph.empty(1))
>>  if (depth==1) return(graph.tree(4, 3, mode="undir"))
>>  d <- coord-1
>>  n1 <- (d^(depth+1)-1) / (d-1)
>>  n2 <- (d^depth -1)/ (d-1)
>>  g <- graph.tree(n1, d, mode="undir") %du% graph.tree(n2, d, mode="undir")
>> }
>>
>> Best,
>> Gabor
>>
>> On Wed, Nov 18, 2009 at 1:41 PM, Tamas Nepusz <address@hidden> wrote:
>>> If I understand it right, a k-Cayley tree is simply a tree where each
>>> non-leaf vertex has degree k. The standard tree generation routine in
>>> igraph therefore builds a Cayley tree if the number of nodes is set
>>> appropriately. (See igraph_tree in C, graph.tree in R, Graph.Tree in
>>> Python).
>>>
>>> --
>>> Tamas
>>>
>>> On Wed, Nov 18, 2009 at 12:29:59AM +0100, Marco wrote:
>>>> Hi all,
>>>>
>>>> any ideas on how to implement efficiently a routine to build a Cayley tree?
>>>>
>>>>
>>>> marco
>>>>
>>>> --
>>>> restituiremo il riso ai salici
>>>>
>>>>
>>>> _______________________________________________
>>>> igraph-help mailing list
>>>> http://lists.nongnu.org/mailman/listinfo/igraph-help
>>>
>>>
>>> _______________________________________________
>>> igraph-help mailing list
>>> http://lists.nongnu.org/mailman/listinfo/igraph-help
>>>
>>
>>
>>
>> --
>> Gabor Csardi <address@hidden>     UNIL DGM
>>
>>
>> _______________________________________________
>> igraph-help mailing list
>> http://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>
>
> _______________________________________________
> igraph-help mailing list
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>

--