Boost::Graph looks to be fairly badly broken at the moment. The original author made three CPAN releases spread over a six month period in 2006. I would find it difficult to write Perl XS extension code coupling C++ with the Boost libraries, effectively debugged, with all the smoke test kinks worked out over the course of three releases in 2006. The condition of available tools to help in writing C++ extension code for Perl in 2006 was not too good. Looking at the CPAN testers matrix corroborates the theory that the module hasn't been adequately refined for as ambitious a project as it is.

On my own Windows and Linux systems (one with Boost installed, one without) I get the same failure points. And they seem significant: incorrect number of parameters being passed to functions, etc. Those sorts of things almost lead me to believe that perhaps the Boost libraries, or the way modern C++ compilers work has changed enough since 2006 that the C++ world has moved on leaving the CPAN Boost::Graph module behind. I would need to study the code thoroughly to really understand what is wrong with it... and I'm not interested enough to do so.

If you're committed to using Boost's graph classes with Perl you might have to do it yourself. Inline::CPP could be used to write your Perl compatible wrappers for the C++ library. Inline::CPP doesn't know how to pass parameters into template classes, so your wrappers would have to encapsulate the existing library such that templated classes aren't exposed directly to Perl. That precludes the use of Inline::CPP's "AUTOWRAP" functionality, so the work would be significant.

You didn't mention what graph implementation you're currently using. If you're not committed to Boost you could shop around for other implementations. The pure Perl implementations that I would most trust are those ones on CPAN with Jarkko Hietaniemi's name on them: Graph, and its siblings. They're well tested, well designed, and he even co-authored the book Mastering Algorithms with Perl, which devotes a lot of its pages to graphs. The book is a dozen years old, and still the best Perl resource for algorithm theory. ...and his Graph modules are still being maintained. This review of Boost::Graph seems to be an endorsement for Jarkko's Graph module, at least with respect to memory and computational efficiency.

Since I don't, on first search, find an XS module implementing graphs, if you really need the speed of C or C++, you're probably going to either have to use Inline::CPP to write your own Boost wrappers for the existing Boost graph library, or you are going to need to implement your own (possibly using Inline::C, or Inline::CPP, or some other XS helper). One strategy for implementation would be to profile Jarkko's Graph module, and rewrite only those portions where you find bottlenecks using Inline::C or Inline::CPP. That would minimize the amount of extension code you would have to write, and would probably be the easiest solution since your extension code could follow the existing Perlish implementation.

Update: As I look over Graph, I think that putting it to work at your specific use-case, and then profiling will probably shed some light on where you might need to focus optimization efforts. It's a big enough module (or set of modules) that you wouldn't want to take on the whole thing, but by profiling your particular application as it uses Graph, you can certainly narrow down the problem areas. With a little luck you will find yourself staring at one subroutine that could be re-implemented in C. That's probably optimistic.

The Inline::CPP approach may still be worth considering; Implement a C++ class that is composed of a Boost graph, and that exposes to Perl a minimal interface for your program to call upon.