# Ticket #8600(closed enhancement: fixed)

Opened 3 years ago

## fibonacci tree

Reported by: Owned by: schilly rlm minor sage-4.4 graph theory N/A Robert Miller Harald Schilly, Yann Laigle-Chapuy sage-4.4.alpha0

### Description

the fibonacci tree,  wikipedia

## Change History

### comment:1 Changed 3 years ago by schilly

• Status changed from new to needs_review

### comment:2 Changed 3 years ago by ylchapuy

I find the placement of the nodes strange (and even more if the tree is big).

I would prefer an implementation using Fibonacci numbers all over the construction:

```def FibonacciTree(n):
T = Graph(name="Fibonacci-Tree-%d"%n)
if n<2: return T

F = list(fibonacci_sequence(n + 2))
s = 2.0 ** (n / 2.0 - 2)
pos = {}

def fib(level, node, y):
pos[node] = (node, y)
if level < 2: return
level -= 1
y -= s
diff = F[level]
if level == 1: # only one child
pos[node - diff] = (node, y)
return
fib(level, node - diff, y)
fib(level - 1, node + diff, y)

fib(n, F[n + 1] - 1, 0)
T.set_pos(pos)

return T
```

but maybe it's just a matter of taste.

With n=7 you obtain the same graph as  http://www.delorie.com/gnu/docs/avl/avlmuchbal.png . Notice that the name of each node is also it's x-coordinate (except for the only children where I prefer to put them under their father).

### comment:3 Changed 3 years ago by schilly

Thanks for your example and quick response, I like it! I've modified it a bit, added your name and made some changes so that it fits into the sage library.

### comment:4 follow-up: ↓ 5 Changed 3 years ago by ylchapuy

I like it too, and the golden_ratio is indeed well suited. I would give it a positive review, but I'm not sure if I can anymore as it's mainly my code.

### comment:5 in reply to: ↑ 4 Changed 3 years ago by schilly

I would give it a positive review...

good! now we just need a third party.

### comment:6 Changed 3 years ago by rlm

• Status changed from needs_review to positive_review
• Reviewers set to Robert Miller
• Authors changed from schilly to Harald Schilly, Yann Laigle-Chapuy

### comment:7 follow-up: ↓ 8 Changed 3 years ago by jhpalmieri

Is there a reason that the milestone for this is version 5.0 rather than 4.4? Should we try to merge it in 4.4?

### comment:8 in reply to: ↑ 7 Changed 3 years ago by schilly

• Milestone changed from sage-5.0 to sage-4.4

Is there a reason that the milestone for this is version 5.0 rather than 4.4?

No, I think there was no 4.4 when i created it, that's all. It's really trivial and just a small addition.

### comment:9 Changed 3 years ago by jhpalmieri

• Status changed from positive_review to closed
• Resolution set to fixed
• Merged in set to sage-4.4.alpha0

Merged "fibonaccy-graph.patch" in 4.4.alpha0

Note: See TracTickets for help on using tickets.