Feature-rich, easy to use and well-documented. Highly recommended as a general graph module for perl.
I also thank the author for being extremely responsive in fixing the two issues below that came up for me:
1) Like reviewer abe, I initially found some basic functions (predecessors and successors) could be slow with large graphs. This is now fixed and I don't think that Graph's performance is a problem in general.
2) I also had an issue with deep_copy this was fixed quickly too.