Pythonic way to walk a self-referential dictionary

Question

I have a dictionary where entry values can reference another entry by key eventually ending with no entry for the current value or when "-" is encountered. The goal of this data structure is to find the parent for each entry and also transform "-" into None. For instance take:

d = {'1': '-', '0': '6', '3': '1', '2': '3', '4': '5', '6': '9'}

• '1' is a root that maps to '-' so it should result in None.
• '0' has a parent of '6', which has a parent of '9' so it should result in '9'.
• '3' has a parent of '1', which maps to '-' so it should result in None.
• '2' has a parent of '3',which has a parent of '1' which maps to '-' so it should result in None.
• '4' should remain with parent of '5'
• '6' should remain with parent of '9'

My verbose solution is as follows:

d = {'1': '-', '0': '6', '3': '1', '2': '3', '4': '5', '6': '9'}
print(d)
for dis, rep in d.items():
    if rep == "-":
        d[dis] = None
        continue

    while rep in d:
        rep = d[rep]
        if rep == "-":
            d[dis] = None
            break
    else:
        d[dis] = rep
print(d)

The output is:

{'1': '-', '0': '6', '3': '1', '2': '3', '4': '5', '6': '9'}
{'1': None, '0': '9', '3': None, '2': None, '4': '5', '6': '9'}

The result is correct. The "1" element has no parent and the "2"/"3" element point back to "1". They should also have no parent.

Is there a terser pythonic way to accomplish this using Python 3+?

Answer 1

To "walk" the dictionary, just do the lookups in a loop until there are no more:

>>> def walk(d, val):
        while val in d:
            val = d[val]
        return None if val == '-' else val

>>> d = {'1': '-', '0': '6', '3': '1', '2': '3', '4': '5', '6': '9'}
>>> print {k: walk(d, k) for k in d}
{'1': None, '0': '9', '3': None, '2': None, '4': '5', '6': '9'}

Answer 2

You can define a function like this

def recursive_get(d, k):
    v = d[k]
    if v == '-':
        v = d[k] = None
    elif v in d:
        v = d[k] = recursive_get(d, v)
    return v

When you use recursive_get to access a key it will modify the values as it traverses. This means you don't waste time packing up branches that are never needed

>>> d = {'1': '-', '3': '1', '2': '3'}
>>> recursive_get(d, '3')
>>> d
{'1': None, '3': None, '2': '3'}         # didn't need to visit '2'

>>> d = {'1': '-', '3': '1', '2': '3'}
>>> recursive_get(d, '2')
>>> d
{'1': None, '3': None, '2': None}

If you wish to just force d into it's final state, simply loop through all the keys

for k in d:
    recursive_get(d, k)