Does Python GC deal with reference-cycles like this?

Python's standard reference counting mechanism cannot free cycles, so the structure in your example would leak.

The supplemental garbage collection facility, however, is enabled by default and should be able to free that structure, if none of its components are reachable from the outside anymore and they do not have __del__() methods.

If they do, the garbage collector will not free them because it cannot determine a safe order to run these __del__() methods.

To extend on Frédéric's answer a bit, the "reference counts" section of the docs explains the supplementary cycle detection nicely.

Since I find explaining things a good way to confirm I understand it, here are some examples... With these two classes:

class WithDel(object):
    def __del__(self):
        print "deleting %s object at %s" % (self.__class__.__name__, id(self))


class NoDel(object):
    pass

Creating an object and losing the reference from a triggers the __del__ method, thanks to the ref-counting:

>>> a = WithDel()
>>> a = None  # leaving the WithDel object with no references 
deleting WithDel object at 4299615184

If we make a reference loop between two objects with no __del__ method, all is still leak-free, this time thanks to the cycle detection. First, enable the garbage-collection debug output:

>>> import gc
>>> gc.set_debug(gc.DEBUG_COLLECTABLE | gc.DEBUG_UNCOLLECTABLE | gc.DEBUG_OBJECTS)

Then make a reference loop between the two objects:

>>> a = NoDel(); b = NoDel()
>>> a.other = b; b.other = a  # cyclical reference
>>> a = None; b = None # Leave only the reference-cycle
>>> gc.collect()
gc: collectable <NoDel 0x10046ed50>
gc: collectable <NoDel 0x10046ed90>
gc: collectable <dict 0x100376c20>
gc: collectable <dict 0x100376b00>
4
>>> gc.garbage
[]

(the dict is from the objects internal __dict__ attribute)

All is fine, until even one of the objects in the cycle contains a __del__ method:

>>> a = NoDel(); b = WithDel()
>>> a.other = b; b.other = a
>>> a = None; b = None
>>> gc.collect()
gc: uncollectable <WithDel 0x10046edd0>
gc: uncollectable <dict 0x100376b00>
gc: uncollectable <NoDel 0x10046ed90>
gc: uncollectable <dict 0x100376c20>
4
>>> gc.garbage
[<__main__.WithDel object at 0x10046edd0>]

As Paul mentioned, the loop can be broken with a weakref:

>>> import weakref
>>> a = NoDel(); b = WithDel()
>>> a.other = weakref.ref(b)
>>> b.other = a # could also be a weakref

Then when the b reference to the WithDel object is lost, it gets deleted, despite the cycle:

>>> b = None
deleting WithDel object at 4299656848
>>> a.other
<weakref at 0x10045b9f0; dead>

Oh, objgraph would have helpfully indicated the problematic __del__ method like this