C++ FAQ Celebrating Twenty-One Years of the C++ FAQ!!!
(Click here for a personal note from Marshall Cline.)
Section 36:
[36.11] How do I serialize objects that contain pointers to other objects, and those pointers form a graph that might have cycles or non-trivial joins?

Caveat: the word "graph" does not mean that the objects are stored in some sort of data structure. Your objects form a graph because they point to each other. They're not "inside" a graph; they are a graph. If that doesn't make sense, you really should read the lingo FAQ before continuing with this one.

Use this solution if the graph can contain cycles, or if it can contain more complicated kinds of joins than are allowed by the solution for trivial joins. This solution handles two core issues: it avoids infinite recursion and it writes/reads each node's identity in addition to its contents.

A node's identity doesn't normally have to be consistent between different output streams. For example, if a particular file uses the number 3 to represent node x, a different file can use the number 3 to represent a different node, y.

There are some clever ways to serialize the graph, but the simplest to describe is a two-pass algorithm that uses an object-ID map, e.g., std::map<Node*,unsigned> oidMap. The first pass populates our oidMap, that is, it builds a mapping from object pointer to the integer that represents the object's identity. It does this by recursively diving through the graph, at each node checking if the node is already in oidMap, and if not, adding the node and a unique integer to oidMap and recursively diving into the new node's children. The unique integer is often just the initial oidMap.size(), e.g., unsigned n = oidMap.size(); oidMap[nodePtr] = n. (Yes, we did that in two statements. You must also. Do not shorten it to a single statement. You have been warned.)

The second pass iterates through the nodes of oidMap, and at each, writes the node's identity (the associated integer) followed by its contents. When writing the contents of a node that contains pointers to other nodes, instead of diving into those "child" objects, it simply writes the identity (the associated integer) of the pointer to those nodes. For example, when your node contains Node* child, simply write the integer oidMap[child]. After the second pass, the oidMap can be discarded. In other words, the mapping from Node* to unsigned should not normally survive beyond the end of the serialization of any given graph.

There are also some clever ways to unserialize the graph, but here again the simplest to describe is a two-pass algorithm. The first pass populates a std::vector<Node*> v with objects of the right class, but any child pointers within those objects are all NULL. This means v[3] will point to the object whose oid is 3, but any child pointers inside that object will be NULL. The second pass populates the child pointers inside the objects, e.g., if v[3] has a child pointer called child that is supposed to point to the object whose oid is 5, the second pass changes changes v[3].child from NULL to v[5] (obviously encapsulation might prevent it from directly accessing v[3].child, but ultimately v[3].child gets changed to v[5]). After unserializing a given stream, the vector v can normally be discarded. In other words, the oids (3, 5, etc.) mean nothing when serializing or unserializing a different stream — those numbers are only meaningful within a given stream.

Note: if your objects contain polymorphic pointers, that is, base class pointers that might point at derived class objects, then use the technique described earlier. You'll also want to read some of the earlier techniques for handling NULL, writing version numbers, etc.

Note: you should seriously consider the Visitor pattern when recursively diving through the graph, since serialization is probably just one of many different reasons to make that recursive dive, and they'll all need to avoid infinite recursion.