get parent keys from nested dictionary

get_parent_keys

import collections
def get_parent_keys(dct, capture_nested_key_parents=True):
    """Get parent keys for all values in dictionary of dictionaries.
    Returns k,v dictionary with lists of parent keys.
    Modified from http://stackoverflow.com/a/18820433
    """

    reverse_dict = {}

    def keypaths(nested):
        for key, value in nested.iteritems():
            if isinstance(value, collections.Mapping):
                top_keys = set()
                for subkey, subvalue in keypaths(value):
                    if capture_nested_key_parents:
                        if key not in top_keys:
                            top_keys.add(key)
                            yield key, subkey
                    yield subkey, subvalue
            else:
                yield key, value

    for k, v in keypaths(dct):
        try:
            reverse_dict[v].append(k)
        except KeyError:
            reverse_dict[v] = list()
            reverse_dict[v].append(k)

    return reverse_dict


def _test_get_parent_keys():
    import itertools

    example_dict = {'key1': 'value1',
                    'key2': 'value2',
                    'key3_has_dict': {'key3a': 'value3a'},
                    'key4_has_dict': {'key4a_has_dict': {'key4aa': 'value4aa',
                                                         'key4ab': 'value4ab',
                                                         'key4ac': 'value1'},
                                      'key4b': 'value4b'}
    }
    expected_result_with_capture_nested_key_parents = {'key3a': ['key3_has_dict'],
                                                       'key4a_has_dict': ['key4_has_dict'],
                                                       'key4ab': ['key4a_has_dict'],
                                                       'value1': ['key4ac', 'key1'],
                                                       'value2': ['key2'],
                                                       'value3a': ['key3a'],
                                                       'value4aa': ['key4aa'],
                                                       'value4ab': ['key4ab'],
                                                       'value4b': ['key4b']
    }
    expected_result_without_capture_nested_key_parents = {
        'value1': ['key4ac', 'key1'],
        'value2': ['key2'],
        'value3a': ['key3a'],
        'value4aa': ['key4aa'],
        'value4ab': ['key4ab'],
        'value4b': ['key4b']
    }
    try:
        for expected_result, capture_nested_key_parents in (
                (expected_result_with_capture_nested_key_parents, True,),
                (expected_result_without_capture_nested_key_parents, False,),):
            assert (len(set(get_parent_keys(example_dict,
                    capture_nested_key_parents=capture_nested_key_parents).iterkeys()).difference(
                        set(expected_result.iterkeys()))) == 0)
            assert (
                set(
                    tuple(
                        tuple(
                            get_parent_keys(
                                example_dict, capture_nested_key_parents=capture_nested_key_parents).iterkeys()) +
                        tuple(
                            itertools.chain.from_iterable(
                                get_parent_keys(example_dict,
                                        capture_nested_key_parents=capture_nested_key_parents).itervalues())))) ==
                set(tuple(tuple(expected_result.iterkeys()) +
                    tuple(itertools.chain.from_iterable(expected_result.itervalues())))))
    except AssertionError as ae:
        print 'test failed'
        raise ae
    except:
        print 'test process broken'
        raise
    else:
        print 'test passed'


_test_get_parent_keys()