Deep copy interconnected objects with references to each other

Question

I have a graph data structure Overlay, which consists of instances that are interconnected by edges. Instances are represented by a set of Instance-objects and edges are represented by a set of Edge-objects. For convenience, each instance keeps track of the in- and outgoing edges by pointing to the corresponding existing Edge-objects. Similarly, each edge points to the source- and the destination-Instance-object.

For example, an overlay may consist of an instance i1 that is connected to another instance i2 via an edge e1. e1.source is a reference to i1 and e2.dest is a reference to i2. i1.edges_out contains a reference to e1, etc. Overall, there are just 2 Instance-objects and 1 Edge-object.

I want to deep copy an overlay, in order to modify it (its instances and edges) without affecting the other overlay(s). My problem is that I don't know how to preserve the structure of interconnecting references as described above.

I use new_overlay = copy.deepcopy(old_overlay) and override __deepcopy__ in Overlay, Instance, and Edge as follows:

In Overlay:

def __deepcopy__(self, memodict={}):
    new_overlay = Overlay(self.template, set(), set())  # new, empty overlay
    new_overlay.instances = copy.deepcopy(self.instances, memodict)
    new_overlay.edges = copy.deepcopy(self.edges, memodict)
    return new_overlay

In Instance:

def __deepcopy__(self, memodict={}):
    # new instance with same attributes
    new_instance = Instance(self.attributes)
    # edges_in, _out should contain references to the existing edges, not new objects
    new_instance.edges_in = copy.deepcopy(self.edges_in, memodict)
    new_instance.edges_out = copy.deepcopy(self.edges_out, memodict)
    return new_instance

In Edge:

def __deepcopy__(self, memodict={}):
    # new edge with same source and destination: these should be references to existing instances, not new objects
    new_edge = Edge(copy.deepcopy(self.source, memodict), copy.deepcopy(self.dest, memodict))
    new_instance.attribute = self.attribute  # no need to deep copy
    return new_edge

I was hoping for copy.deepcopy to take care of everything by using the memodict, but it doesn't work: When checking the object-id with the PyCharm debugger, the references in the copied overlay are sometimes incorrect. Instead of referencing existing objects, e.g., existing instances as source/destination of an edge, new instance objects are created.

How can I deep copy Overlay while preserving the structure of references? Both edges should have references to instances (source/destination) and instances should have references to edges (edges_in/edges_out).