Recursive (pedigree) tree building from (child, parent) list in Python

Question

Hi All,

I have as input a list of tuples (child, parent).

Given that a child only have one parent.

I would like for every child to build an ordered ancestors list.

Any tip ?

input would be like : [('3', '4'), ('1', '2'), ('2', '3')]
output would be like: 
1, [2, 3, 4] 
2, [3, 4]
3, [4]
4, [None]

Answer 1

Do you want to prebuild the data structure, or just generate it on the fly? The latter is not (nearly) as fast, but much easier:

mapping = { int( key ): int( val ) for key, val in input }
cache = { }
def pedigree( child ):
    pedigree = cache.get( child, [ ] )
    if pedigree:
        return pedigree

    try:
        while True:
            child = mapping[ child ]
            pedigree.append( child )
    except KeyError:
        pass
    cache[ child ] = pedigree
    return pedigree

Edit: added cache

Answer 2

Here is a way to do it using recursion. The output for 4 doesn't match your expected output. Should be easy enough for you to fix though

>>> inp =[('3', '4'), ('1', '2'), ('2', '3')]
>>> inp = dict(inp)
>>> def pedigree(x):
...     if x in inp:
...         parent = inp[x]
...         return [parent]+pedigree(parent)
...     return []
...
>>> for i in '1234':
...     print i, pedigree(i)
...
1 ['2', '3', '4']
2 ['3', '4']
3 ['4']
4 []