A nice consideration on value semantics and STL/boost algorithms:

In generic implementations of algorithms it is preferred to use value semantics: copying an object causes two identical objects to exist which are independent. This is crucial property when it is necessary to duplicate objects. Dynamic polymorphism doesn't immediately work with value semantics because for the use of dynamic polymorphism you need to deal with pointers or reference: when using values, the static type and the dynamic type of object coincide which doesn't allow dynamic polymorphism directly.

The only way to deal with dynamically polymorph objects in this case is to give them a value look and feel. Effectively, this means that you need to encapsulate the pointers to your objects into object which expose the required value interface (you can also encapsulate references if you insist but I never found that this works well). The Boost Graph library doesn't really care about how the various structures are internally represented as long as they have the required interface and implement the required semantics. From what you describe using a wrapper for your pointers to the polymorphic objects is the right way to go. Whether you maintain the object via one of the standard smart pointers or differently doesn't really matter although I'd guess that using something like boost::shared_ptr<T> or std::shared_ptr<T> removes a number of unnecessary complications.

All this said, I'd like to point out that I rarely find useful examples of dynamically polymorph objects combined with algorithms! Yes, there are some but most of the time use of dynamic polymorphism is contributing to the problem, not to the solution (despite what many people having only exposure to object-oriented technique say; however, if the only tool you know is a hammer, every problem looks like a nail).

[via @dietmar-kuhl]