#8600: fibonacci tree
----------------------------+-----------------------------------------------
Reporter: schilly | Owner: rlm
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-5.0
Component: graph theory | Keywords:
Author: schilly | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Comment(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==1: T.add_vertex(0)
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]
T.add_edge(node, node-diff)
if level == 1: # only one child
pos[node - diff] = (node, y)
return
T.add_edge(node, node + diff)
fib(level, node - diff, y)
fib(level - 1, node + diff, y)
T.add_vertices(xrange(sum(F[:-1])))
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).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8600#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
