I'd try to avoid weak references if at all possible.
Some remarks:
Calling DESTROY on an object to force it to destruct doesn't work at all as far as I know, but someone else might know more than I do.
I would suggest you take a look at Graph::Directed. It keeps the graph as a seperated object from the nodes and edges, which should remove the need for references in the nodes and edges themselves.
You can also try writing your own graph object that removes the references in the nodes/edges when it goes out of scope. That way you also don't need weak references.