[Scipy-tickets] [SciPy] #1652: scipy.cluster.hierarchy.ClusterNode.pre_order returns IndexError for non-root node

SciPy Trac scipy-tickets@scipy....
Mon Apr 30 13:51:13 CDT 2012


#1652: scipy.cluster.hierarchy.ClusterNode.pre_order returns IndexError for non-
root node
--------------------------------------------------------+-------------------
 Reporter:  MarkPundurs                                 |       Owner:  somebody   
     Type:  defect                                      |      Status:  new        
 Priority:  normal                                      |   Milestone:  Unscheduled
Component:  scipy.cluster                               |     Version:  0.9.0      
 Keywords:  cluster, hierarchy, ClusterNode, pre_order  |  
--------------------------------------------------------+-------------------
Changes (by rgommers):

 * cc: david.warde-farley (added)


Old description:

> To reproduce the error, run the following script:
>
> import random, numpy
> from scipy.cluster.hierarchy import linkage, to_tree
>
> datalist = []
> for i in range(8000):
>     datalist.append(random.random())
> datalist = numpy.array(datalist)
> datalist = numpy.reshape(datalist, (datalist.shape[0], 1))
> Z = linkage(datalist)
> root_node_ref = to_tree(Z)
> left_root_node_ref = root_node_ref.left
> left_root_node_ref.pre_order()
>
> The result is:
>
> Traceback (most recent call last):
>   File "C:\ReproduceError-pre_order.py", line 12, in <module>
>     left_root_node_ref.pre_order()
>   File "C:\Python27\lib\site-packages\scipy\cluster\hierarchy.py", line
> 732, in pre_order
>     if not lvisited[ndid]:
> IndexError: index out of bounds
>
> One possible solution (successfully tested with preceding script) is to
> change pre_order in hierarchy.py as follows:
>
>         n = self.count
>
>         curNode = [None] * (2 * n)
>         #following two lines changed: dictionaries instead of lists
>         lvisited = {}
>         rvisited = {}
>         curNode[0] = self
>         k = 0
>         preorder = []
>         while k >= 0:
>             nd = curNode[k]
>             ndid = nd.id
>             if nd.is_leaf():
>                 preorder.append(func(nd))
>                 k = k - 1
>             else:
>                 #following line changed: check existence of dictionary
> key rather than value of list item
>                 if ndid not in lvisited.keys():
>                     curNode[k + 1] = nd.left
>                     lvisited[ndid] = True
>                     k = k + 1
>                 #following line changed: check existence of dictionary
> key rather than value of list item
>                 elif ndid not in rvisited.keys():
>                     curNode[k + 1] = nd.right
>                     rvisited[ndid] = True
>                     k = k + 1
>                 else:
>                     k = k - 1
>
>         return preorder

New description:

 To reproduce the error, run the following script:
 {{{
 import random, numpy
 from scipy.cluster.hierarchy import linkage, to_tree

 datalist = []
 for i in range(8000):
     datalist.append(random.random())
 datalist = numpy.array(datalist)
 datalist = numpy.reshape(datalist, (datalist.shape[0], 1))
 Z = linkage(datalist)
 root_node_ref = to_tree(Z)
 left_root_node_ref = root_node_ref.left
 left_root_node_ref.pre_order()
 }}}
 The result is:
 {{{
 Traceback (most recent call last):
   File "C:\ReproduceError-pre_order.py", line 12, in <module>
     left_root_node_ref.pre_order()
   File "C:\Python27\lib\site-packages\scipy\cluster\hierarchy.py", line
 732, in pre_order
     if not lvisited[ndid]:
 IndexError: index out of bounds
 }}}
 One possible solution (successfully tested with preceding script) is to
 change pre_order in hierarchy.py as follows:
 {{{
         n = self.count

         curNode = [None] * (2 * n)
         #following two lines changed: dictionaries instead of lists
         lvisited = {}
         rvisited = {}
         curNode[0] = self
         k = 0
         preorder = []
         while k >= 0:
             nd = curNode[k]
             ndid = nd.id
             if nd.is_leaf():
                 preorder.append(func(nd))
                 k = k - 1
             else:
                 #following line changed: check existence of dictionary key
 rather than value of list item
                 if ndid not in lvisited.keys():
                     curNode[k + 1] = nd.left
                     lvisited[ndid] = True
                     k = k + 1
                 #following line changed: check existence of dictionary key
 rather than value of list item
                 elif ndid not in rvisited.keys():
                     curNode[k + 1] = nd.right
                     rvisited[ndid] = True
                     k = k + 1
                 else:
                     k = k - 1

         return preorder
 }}}

--

Comment:

 <reformat description>

-- 
Ticket URL: <http://projects.scipy.org/scipy/ticket/1652#comment:1>
SciPy <http://www.scipy.org>
SciPy is open-source software for mathematics, science, and engineering.


More information about the Scipy-tickets mailing list