Friday, January 29, 2010

Viewing a nested list as a tree

The problem, as discussed in the last post, is to "flatten" a list of nested lists of unspecified structure. One can look at such an object as a tree.

I thought about writing code to do a "depth-first traversal" of this tree, but then I remembered PyCogent. It has functions that manipulate trees. All we have to do is to convert our data to a form that it can recognize:

>>> L = [[[1, 2, 3], [4, 5]], 6]
>>> `L`
'[[[1, 2, 3], [4, 5]], 6]'
>>> t = `L`.replace('[','(')
>>> t = t.replace(']',')') + ';'
>>> t
'(((1, 2, 3), (4, 5)), 6);'

It's easiest to load the data from a file, so first we write it:

>>> FH = open('temp.tree','w')
>>> FH.write(t)
>>> FH.close()
>>>
>>> from cogent import LoadTree
>>> tr = LoadTree('temp.tree')
>>> tr
Tree("(((1,2,3),(4,5)),6);")
>>>
>>> print tr.asciiArt()
/-1
|
/edge.0--|--2
| |
/edge.2--| \-3
| |
| | /-4
-root----| \edge.1--|
| \-5
|
\-6
>>>
>>> [str(tip) for tip in tr.iterTips()]
['1;', '2;', '3;', '4;', '5;', '6;']