I think I would just put all the nodes into a Vec and use indices instead of references. This results in every node having the same lifetime, like you wanted. It is what the specialized graph libraries like petgraph are doing, and it is memory safe due to bound checks.