As far as I know the Graph module is essentially a toy implementation intended for teaching Graph theory and programming to a novice programmers. Its fine and dandy for some simple experiements, and is a good venue for teaching complex concepts, but ultimately its just a toy. The ram requirements for a modest graph are prohibitive, and the speed of the implementation leaves much to be desired. Much better to find an alternate C implementation (or prolog) to do this type of stuff. A pure perl implementation just isnt a big enough hammer for the nut you want to crack.

Incidentally if you do happen to put in the effort to put a perl wrapper on a classy set of graph tools then I for one would welcome it greatly. Or if its already been done, a heads up for what to look at would be nice. :-)

HTH