Boost Graph Library Polymorphic Bundled Properties

Question

So I'm using a boost graph of the following type:

typedef boost::adjacency_list<boost::listS, boost::vecS, boost:directedS, VertexT, EdgeT> GraphT

VertexT and EdgeT are both classes to keep many of the properties I need. These are bundled properties. I'm not sure if some of the ways I want to use bgl are possible so if you are familiar with them help would be much appreciated.

VertexT and EdgeT are suppose to be polymorphic base classes. My understanding is bgl is not meant to use for pointers to these properties. How does one work with polymorphic vertex and edge properties with BGL? I thought of using shared pointers but I'd prefer to manage the memory myself. Additionally this seems to prevent a problem when using boost::get to generate the position map for boost layouts.

Right now I've hacked my way around this by just having vertex contain another pointer to the true polymorphic class. But that seems too complex. Any suggestions?

Answer 1

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).

Answer 2

I think you are basically solving the same problem as this question:

• C++ and generic graph distance algorithm

only for (bundled) properties. I'd suggest you can do the polymorphism by invoking free-standing function templates.

---

For real high-power machinery:

See also this paper: On the Tension Between Object-Oriented and Generic Programming in C++; that paper describes type erasure which is kind of the end-all 'solution' to decouple/bridge your runtime/static polymorphism needs. (_Note that libraries such as Boost Variant, Boost Any are much more convenient if you need to implement type erasure).