How do i check for Cycles/back edges in dictionaries? {...}

Question

How can I detect whether a dictionary contains a back-edge aka back-reference that might end up in an infinite loop or cause a maximum recursion depth exception.

x = {'a':1}           
x['b'] = x            #referencing same dict, creating back edge
print(x)
>{'a': 1, 'b': {...}}

So apparently python is smart enough to figure out back-edges and marks them by printing them as {...}. Is there a way to access this information, so it can be skipped, without checking all the elements against each other for their id's?

Answer 1

The dict.__repr__ implementation calls Py_ReprEnter, a C API analogue of reprlib.recursive_repr, which records the fact that the current thread is computing the dict's repr. If dict.__repr__ is entered again for that dict without an intervening Py_ReprLeave, Python knows that it's in a recursive repr call, and it uses '{...}' instead of going through the usual logic.

You can apply a similar technique in your own code. In whatever recursive traversal you want to write, record what objects the current thread is currently processing, and use that information to detect when you hit a cycle. Depending on what you're trying to do and the structure of your input, there may be other useful techniques.