Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Dictionary to tree format (hopefully simple)

Reply
Thread Tools

Dictionary to tree format (hopefully simple)

 
 
Adam Powell
Guest
Posts: n/a
 
      08-05-2008
Hi!
I have seemingly simple problem, which no doubt someone out there has
already solved, but I'm stumped. Imagine I have a dictionary like
below, in which the keys are parent nodes and the values are a list of
children nodes.

dict = { 0: [1, 2], 1: [3], 2: [6], 3: [4,7], 4: [5,8], 8: [9] }

Is there an obvious way to produce a nested tree format for this
dictionary, like this:

[ 0 [ 1 [ 3 [ 4 [ 5 , 8 [ 9 ] ] , 7 ] ] , 2 [ 6 ] ]

Thanks for any help,

Adam
 
Reply With Quote
 
 
 
 
Diez B. Roggisch
Guest
Posts: n/a
 
      08-05-2008
Adam Powell schrieb:
> Hi!
> I have seemingly simple problem, which no doubt someone out there has
> already solved, but I'm stumped. Imagine I have a dictionary like
> below, in which the keys are parent nodes and the values are a list of
> children nodes.
>
> dict = { 0: [1, 2], 1: [3], 2: [6], 3: [4,7], 4: [5,8], 8: [9] }
>
> Is there an obvious way to produce a nested tree format for this
> dictionary, like this:
>
> [ 0 [ 1 [ 3 [ 4 [ 5 , 8 [ 9 ] ] , 7 ] ] , 2 [ 6 ] ]
>
> Thanks for any help,


d = { 0: [1, 2], 1: [3], 2: [6], 3: [4,7], 4: [5,8], 8: [9] }

nodelists = dict((node ,[node, []]) for node in d.keys())

for node, children in d.iteritems():
for child in children:
nodelists[node][1].extend(nodelists.setdefault(child, [child]))

print nodelists[0]


Two remarks:

- don't use "dict" as name for a dictionary - look at the above code
*why* not...

- the code assumes that 0 is the root. if that wouldn't be the case,
you need to search for the root node. I've got an idea - you to?

Diez
 
Reply With Quote
 
 
 
 
Adam Powell
Guest
Posts: n/a
 
      08-06-2008
Thanks very much for this, very concise!
 
Reply With Quote
 
John Nagle
Guest
Posts: n/a
 
      08-07-2008
Diez B. Roggisch wrote:
> Adam Powell schrieb:
>> Hi!
>> I have seemingly simple problem, which no doubt someone out there has
>> already solved, but I'm stumped. Imagine I have a dictionary like
>> below, in which the keys are parent nodes and the values are a list of
>> children nodes.
>>
>> dict = { 0: [1, 2], 1: [3], 2: [6], 3: [4,7], 4: [5,8], 8: [9] }
>>
>> Is there an obvious way to produce a nested tree format for this
>> dictionary, like this:
>>
>> [ 0 [ 1 [ 3 [ 4 [ 5 , 8 [ 9 ] ] , 7 ] ] , 2 [ 6 ] ]
>>
>> Thanks for any help,

>
> d = { 0: [1, 2], 1: [3], 2: [6], 3: [4,7], 4: [5,8], 8: [9] }
>
> nodelists = dict((node ,[node, []]) for node in d.keys())
>
> for node, children in d.iteritems():
> for child in children:
> nodelists[node][1].extend(nodelists.setdefault(child, [child]))
>
> print nodelists[0]
>
>
> Two remarks:
>
> - don't use "dict" as name for a dictionary - look at the above code
> *why* not...
>
> - the code assumes that 0 is the root. if that wouldn't be the case,
> you need to search for the root node. I've got an idea - you to?
>
> Diez


Not quite. That gets you

[0, [1, [3, [4, [5, 8, [9]], 7]], 2, [6]]]

which probably isn't what you want. Note that the children of 0 are

1, [3, [4, [5, 8, [9]], 7]],
2,
[6]

which probably isn't what was desired.
You probably want

[0, [1, [3, [4, [5], [8, [9]]], [7]]], [2, [6]]]

so that each list is [node, [children]].

The original poster wanted

[ 0 [ 1 [ 3 [ 4 [ 5 , 8 [ 9 ] ] , 7 ] ] , 2 [ 6 ] ]

but that's not a meaningful Python list expression.

Try this recursive form:

d = { 0: [1, 2], 1: [3], 2: [6], 3: [4,7], 4: [5,8], 8: [9] }

def getsubtree(d, node) :
if d.has_key(node) :
return([node] + [getsubtree(d,child) for child in d[node]])
else :
return([node])

getsubtree(d,min(d.keys())) # smallest node is assumed to be the root

John Nagle
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Performance ordered dictionary vs normal dictionary Navkirat Singh Python 6 07-29-2010 10:18 AM
Re: Performance ordered dictionary vs normal dictionary Chris Rebert Python 0 07-29-2010 06:11 AM
creating a dictionary from a dictionary with regex james_027 Python 1 08-22-2007 07:39 AM
[DICTIONARY] - Copy dictionary entries to attributes Ilias Lazaridis Python 6 02-21-2006 11:27 AM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM



Advertisments