Recursive tree list from dictionary

[David Pratt]

Hi. I am wanting to create a tree list result structure from a
dictionary to categorize results. The dictionary contains elements that
identify its parent. The levels of categorization is not fixed, so there
is a need for the code to be recursive to drill down to the lowest
level. I have contrived a small source and result list to illustrate:

source_list =[
{'title': 'Project', 'parent':'root'},
{'title': 'Geometry', 'parent':'root'},
{'title': 'Soil', 'parent':'root'},
{'title': 'Geometries', 'parent':'Project'},
{'title': 'Verticals', 'parent':'Project'},
{'title': 'Points', 'parent':'Geometry'},
{'title': 'Layers', 'parent':'Geometry'},
{'title': 'Water', 'parent':'Geometry'},
{'title': 'Soiltypes', 'parent':'Soil'}]

What I want to do is a tree list like this:

tree_result_list = [
# Project
['Project', ['Geometries','Verticals']],
# Geometry
['Geometry', ['Points', 'Layers', 'Water']],
# Soil
['Soil', ['Soiltypes']]
]

I have not been successful and am hoping someone can
advise a solution to accomplish this. Many thanks.

Regards
David

[bearophileHUGS]

This isn't much tested, so don't trust it much, and I hope it's not
overkill.
You can find Graph here:
http://sourceforge.net/projects/pynetwork/
With this you can plot the tree, if you want:
g.springCoords(); g.plot2d()

Bear hugs,
bearophile
def scan(g, parent):
subs = [scan(g, sub) for sub in g.outNodes(parent)]
if subs:
return [parent, subs]
else:
return parent

from graph import Graph
g = Graph()
for d in source_list:
g.addArc(d["parent"], d["title"])
roots = [n for n in g if not g.inNodes(n)]
assert len(roots) == 1 # optional
result = scan(g, roots[0])[1]
print result, "\n\n", tree_result_list

[Alan Franzoni]

Il Sat, 14 Jan 2006 13:52:43 -0400, David Pratt ha scritto:

source_list =[

I don't understand what you mean by saying that 'levels of categorization
is not fixed', are there more than two keys in any dictionary?

Basically, thus, you have a list of dictionaries and you want to get a list
of lists, right? You haven't specified what order would you like the list
to be sorted, though. Maybe you would benefit from use and ordered
dictionary implementation like orderedDict, but such behaviour can be
created anyway. I would use a kind of 'helper dictionary' to map the list
position to the root element:

def convertList(dictlist):
helpdict={}
for elem in dictlist:
helpdict.setdefault(elem['parent'],[])
helpdict[elem['parent']].append(elem['title'])

return [k,v for k,v in helpdict.items() if k!='root']

--
Alan Franzoni <al***************@gmail.com>
-
Togli .xyz dalla mia email per contattarmi.
To contact me, remove .xyz from my email address.
-
GPG Key Fingerprint:
5C77 9DC3 BD5B 3A28 E7BC 921A 0255 42AA FE06 8F3E