#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2011
    Posts
    69
    Rep Power
    8

    Recursion, tree with one to many relationship


    Hi,

    I have users who each have a parent user.

    I want to display like the example below:

    - parent (level 0)
    -- child (level 1)
    --- child (level 2)
    -- child (level 1)
    -- child (level 1)
    --- child (level 2)
    ---- child (level 3)

    The values come from relational database.
    I have built a dict "mydict" with key as parent id and a list of child id's
    So any parent (of 1 or more children) features even if they are also a child of another parent.

    I'm trying to recursively build an array of output (in the order of the example above), one line per node.

    Code:
    def get_ordered_list(mydict, x, level=0, myout=[]):           
        myout.append(get_data(mydict, x, level))
        if x in mydict:
            for r in mydict[x]:  # each child in list for parent
                return get_ordered_list(mydict, r, level + 1, myout)
        else:
            return myout
    It bottoms out once the first lowest child is reached. How do I fix this please to traverse all branches?

    Thanks
    Last edited by userdefined; March 20th, 2012 at 10:32 AM.
  2. #2
  3. Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Aug 2011
    Posts
    5,974
    Rep Power
    510
    Code:
    '''
        create and display this structure recursively
    
        - parent (level 0)   a  
        -- child (level 1)   b
        --- child (level 2)  c
        -- child (level 1)   d
        -- child (level 1)   e
        --- child (level 2)  f
        ---- child (level 3) g
    '''
    
    mydict = {
        'a': 'bde',
        'b': 'c',
        'c': None,
        'd': None,
        'e': 'f',
        'f': 'g',
        #'g': None   or no definition works too
        }
    
    CUTOFF = 9
    
    def f(D,K,L):
        if CUTOFF < L:
            raise ValueError('Probably have a recursively defined dictionary')
        M = L + 1
        print(('-'*M)+' '+('child','parent',)[not L]+'(level '+str(L)+')')
        try:
            iter(D[K])
        except:
            pass
        else:
            for CHILD in D[K]:
                f(D,CHILD,M)
    
    f(mydict,'a',0)
    or, instead of recursive cutoff trap, you could remove the key K from dictionary passed on to recursive incarnation of f.

    Comments on this post

    • userdefined agrees
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2011
    Posts
    69
    Rep Power
    8
    Brilliant, thanks so much

IMN logo majestic logo threadwatch logo seochat tools logo