By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
464,668 Members | 1,419 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 464,668 IT Pros & Developers. It's quick & easy.

Dictionary to tree format (hopefully simple)

P: n/a
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
Aug 5 '08 #1
Share this Question
Share on Google+
3 Replies

P: n/a
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
Aug 5 '08 #2

P: n/a
Thanks very much for this, very concise!
Aug 6 '08 #3

P: n/a
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
Aug 7 '08 #4

This discussion thread is closed

Replies have been disabled for this discussion.