Recursive tree list from dictionary

[Bengt Richter]

On Sat, 14 Jan 2006 16:46:29 -0400, David Pratt <fairwinds at eastlink.ca> wrote:

>Hi Allan, Max, and bearophile
>
>Many thanks for your replies to this. The number of levels can be deeper 
>than two for creating child, sibling relationships. This can lead to 
>futher nesting as shown in my sample result list (the result I am 
>attempting to acheive) which is reason that I believe this has to be 
>recursive to work. As an illustration, I have altered the source_dict to 
>show this by making Geometries the parent of Geometry. I should have 
>gone one more level to illustrate this properly - my apologies for not 
>doing this better.
>
>source_list = [{'title': 'Project', 'parent':'root'},
>	{'title': 'Geometry', 'parent':'Geometries'},
>	{'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'}
>	]
>
>Project and Soil in root,
>Geometries (Geometries containing Geometry with its siblings) and 
>Verticals in Project,
>Soiltypes in Soil
>
>In this instance, I am looking for a result list that looks like this:
>
>result_list = [
>	# Project
>	['Project', ['Geometries',['Geometry', ['Points', 
>'Layers','Water']],'Verticals']],
>	# Soil
>	['Soil', ['Soiltypes']]
>	]
>
>I have not yet installed http://sourceforge.net/projects/pynetwork/ but 
>will also give this a try. What I need is something like elementree 
>minus the xml since I am working with list of dicts obtained from more 
>than one type of source.
>
If you literally want "# Project" comments in the output, it will have
to be a source code (string) output, e.g., the following generates and
prints both:

----< david_pratt.py >--------------------------------------------------
source_list = [{'title': 'Project', 'parent':'root'},
    {'title': 'Geometry', 'parent':'Geometries'},
    {'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'}
    ]
children = {}
for d in source_list:
    children.setdefault(d['parent'], []).append(d['title'])

def get_progeny(title, d=children):
    if title in d: return [title] + [get_progeny(child) for child in d[title]]
    else: return title

source = ['result_list = [']
result_list = []
for child in children['root']:
    source.append('    # %s'%child)
    source.append('    %r,'% get_progeny(child))
    result_list.append(get_progeny(child))
source.append('    ]')
result_list_source = '\n'.join(source)
print result_list_source
print result_list
------------------------------------------------------------------------

[18:20] C:\pywk\clp>py24 david_pratt.py
result_list = [
    # Project
    ['Project', ['Geometries', ['Geometry', 'Points', 'Layers', 'Water']], 'Verticals'],
    # Soil
    ['Soil', 'Soiltypes'],
    ]
[['Project', ['Geometries', ['Geometry', 'Points', 'Layers', 'Water']], 'Verticals'], ['Soil', '
Soiltypes']]

Regards,
Bengt Richter