Memory management for graph datastructures
===

I have, on several occasions and for several employers, had reason to implement my own graph datastructure. For full flexibility of access I have often need to implement this using two classes, a `Node` class and an `Edge` class.

A node will then have a set of outgoing edges (and perhaps incoming edges) and an edge will have a source and a sink (both being managed pointers to Nodes). Frequently these graphs have cycles.

My question is: what is the best way to manage memory in such graph datastructures, in particular when you are transforming and mutating the graph? Because of the presence of cycles, they don't lend themselves to reference counting (even if you try to use weak pointers, it is often not clear where the cycles are and hence where to place the weak links).

In my various implementations, I have often kept track of all allocated nodes and edges, separate from the graph as well as a list of entry points to the graph. I have then implemented what is in effect a simple garbage collector. At regular intervals, having applied various graph transformations (including unlinking some nodes/edges) I run the gc, which involves:

1. Starting at the entry point nodes and marking all nodes and edges reachable from there through the graph as active (via BFS/DFS).
2. Iterating over all nodes and edges in the complete set and deleting any not marked in the previous step.

This works well (and is a simple implementation of mark/sweep). But it always ends up seeming a little clumsy. Does anyone have any insights into this issue, or better alternative solutions?