Dictionary to tree format (hopefully simple)

Discussion in 'Python' started by Adam Powell, Aug 5, 2008.

  1. Adam Powell

    Adam Powell Guest

    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
    Adam Powell, Aug 5, 2008
    #1
    1. Advertising

  2. 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
    Diez B. Roggisch, Aug 5, 2008
    #2
    1. Advertising

  3. Adam Powell

    Adam Powell Guest

    Thanks very much for this, very concise!
    Adam Powell, Aug 6, 2008
    #3
  4. Adam Powell

    John Nagle Guest

    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
    John Nagle, Aug 7, 2008
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Gardner
    Replies:
    0
    Views:
    351
    Chris Gardner
    Oct 29, 2003
  2. Jon Thackray

    Hopefully simple XPath question

    Jon Thackray, Nov 10, 2004, in forum: XML
    Replies:
    9
    Views:
    408
    Joris Gillis
    Nov 13, 2004
  3. Replies:
    4
    Views:
    259
  4. ©®
    Replies:
    3
    Views:
    389
  5. Replies:
    1
    Views:
    240
Loading...

Share This Page