pre_order for subtrees fails

[GoogleCodeExporter]

When trying to list all leafs in a given subtree of the merge tree created by 
to_tree, it fails in some cases with 'Index out of bounds'

What steps will reproduce the problem?
Run the following code to get the exception:

from hcluster import *
dist = [1, 1, 1, 1, 2, 2, 2, 3, 3, 4]
x = linkage(dist)
t = to_tree(x)
t.right.right.pre_order()

What version of the product are you using? On what operating system?

I'm using the port py26-hcluster version 0.2.0 on OS X 10.6 with Python 2.6.

Please provide any additional information below.

Looking at hierarchy.py (revision 132), it looks like the problem is that the 
lists lvisited and rvisited (line 752 and 753) are indexed using node IDs, 
while their size is 2*n (n is the size of the subtree in that node). If the 
tree is large enough, the node ID of the (for example) rightmost leaf is 
actually larger than 2*n for most subtrees containing it.

Original issue reported on code.google.com by ondra...@gmail.com on 20 Jul 2010 at 9:30

[GoogleCodeExporter]

Thanks for the bug report. When performing preOrder on the root node, the leaf 
indices are guaranteed to be between 0 and N (exclusive) where N is the number 
of leaves (original observations). However, as you stated, this does not 
necessarily hold for preOrder on non-root nodes. One fix would be to change the 
lvisited and rvisited arrays to set objects but then it is not as efficient.

Thanks again. I hope to have a fix soon.

Damian Eads

Original comment by damian.e...@gmail.com on 20 Jul 2010 at 11:25