The solution with a graph object looks nice, but when you allow some graph operations, than subgraphs could be shared among many (new) graphs. So, another level of sharing. I can't find any better solution for this problem.