Python iterating through nested dictionaries

Question

First of all, here is the question and the code written:

def family_lineage(familytree, lineage):
    '''(dict, list of strs) -> boolean
    Return True if lineage specifies a list of names who are directly related
    in a chain of parent-child relationships, and NOT child-parent, parent-grandchild..etc,
    beginning from the first generation listed.

    >>> trace_lineage({'Gina': {'Sam': {'Tina': {}},
                           'Li': {}},
                   'Guy': {}},
                      ['Gina'])
    True

    >>> trace_lineage({'Gina': {'Sam': {'Tina': {}},
                               'Li': {}},
                       'Guy': {}},
                      ['Gina', 'Sam', 'Tina'])
    True
    >>> trace_lineage({'Gina': {'Sam': {'Tina': {}},
                               'Li': {}},
                       'Guy': {}},
                      ['Gina', 'Tina'])
    False
    '''

So, in the above example, it shows the 'Guy' has no children, and 'Gina' has two children, 'Sam', and 'Li'. 'Sam' has one child, 'Tina'.

for k, v in familytree.items():
    for n, m in v.items():
        if lineage[0] == any(k) and len(lineage) == 1:
            return True
        elif lineage[0] == k and lineage[1] == n and len(lineage) ==2:
            return True
        elif lineage[0] == k and lineage[1] == n and lineage[2] == m and \
        len(lineage) == 3:
            return True
        else:
            return False

So, my question is, how would I write this if the familytree extended beyond three generations? Is there a more concise way of writing this code?

Make a recursive call, so it would work with a tree of any depth. — Jiminion
– Jiminion, Commented Jul 22, 2013 at 21:11
possible duplicate of in python, how do i iterate a nested dict with a dynamic number of nests? — Marcin
– Marcin, Commented Jul 22, 2013 at 21:21

Andrew Clark · Accepted Answer · 2013-07-22 21:24:38Z

4

Here is an iterative approach that will work even if lineage does not start at the top of the family tree:

def family_lineage(familytree, lineage):
    trees = [familytree]
    while trees:
        tree = trees.pop()
        trees.extend(t for t in tree.values() if t)
        for name in lineage:
            if name not in tree:
                break
            tree = tree[name]
        else:
            return True
    return False

answered Jul 22, 2013 at 21:24

Andrew Clark

210k36 gold badges285 silver badges310 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Martijn Pieters Over a year ago

Nice approach with using a queue.

user2489861 Over a year ago

Could you explain a bit on what you did? What was the purpose of putting familytree in square brackets, and then to use pop later on? And when the code breaks, does it go directly to return False?

Andrew Clark Over a year ago

trees is a container of all unvisited branches in the tree, so trees = [familytree] is just giving us a starting point of the entire tree. On each iteration of the while loop trees.pop() will give us a branch (node) of the tree to work with, and all non-empty children of that node are added to trees. When the code breaks it does not go directly to return False, it just breaks out of the for loop. The else clause on the for is only executed if there was no break, so this only returns True when every name in lineage is found. We return False when all branches have been visited.

Martijn Pieters · Accepted Answer · 2013-07-22 21:20:27Z

Basically, you want to see if you can traverse the tree; use reduce() to loop over the elements and if a KeyError is raised, the path doesn't exist:

def family_lineage(familytree, lineage):
    if not familytree:
        return False
    try:
        reduce(lambda d, k: d[k], lineage, familytree)
        return True
    except KeyError:
        # No match at this level, recurse down the family tree
        return any(family_lineage(val, lineage) for val in familytree.itervalues())

reduce() applies the lambda function recursively to lineage, starting with familytree.

To support finding lineages deeper down the tree, you need to recurse down the tree on KeyErrors.

Demo:

>>> tree = {'Gina': {'Sam': {'Tina': {}}, 'Li': {}}, 'Guy': {}}
>>> family_lineage(tree, ['Gina'])
True
>>> family_lineage(tree, ['Gina', 'Sam', 'Tina'])
True
>>> family_lineage(tree, ['Gina', 'Tina'])
False
>>> family_lineage(tree, ['Sam', 'Tina'])
True

Collectives™ on Stack Overflow

Python iterating through nested dictionaries

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related