Re: [Boost-users] Boost Graph: determining type of bundled property

On Thu, 29 Apr 2010, Trevor Harmon wrote:

On Apr 7, 2010, at 7:04 PM, Jeremiah Willcock wrote:

...

...

class BaseVertex { }; class EntryVertex : public BaseVertex { }; class ExitVertex : public BaseVertex { }; class FooVertex : public BaseVertex { Foo *foo; // ... other properties follow ... };

If you need that, you'll need to keep a (smart) pointer to the base class rather than a copy. I would recommend using boost::shared_ptr<BaseVertex> as the property type.

I rewrote my graph code to use shared_ptr<BaseVertex>, and it seems to be working as expected (including the polymorphism when derived classes are inserted). Thanks for the suggestion.

However, I'm a little confused about efficiency issues. In the Java world, which I'm more familiar with, many collection classes (e.g., tree maps, tree sets) require the contained object to conform to a "comparable" interface. This allows the collection to derive the natural ordering of objects, which in turn allows the container to employ an efficient underlying implementation such as a red-black tree.

But the Boost world is different. For example, my original graph implementation contained Foo pointers, and Foo didn't define any comparison operations. (But I suppose since it's a pointer, the comparison can be done on the pointer value itself, since it's just a number...?) On the other hand, my graph now consists of shared_ptr instances, not pointers. So how can, say, a std::map (like the NameVertexMap in the kevin-bacon example) derive the ordering of the instances? Is there some defined protocol for that? (Perhaps this is more of a C++ question than a Boost question...)

You wouldn't be ordering your properties themselves (or pointers to them), just the vertex indices. Those are usually integers and so are easy to compare. Or am I misunderstanding what you're keeping maps of?

...

...

My goal is to be able to iterate through the vertices and perform different actions depending on the type of vertex. (e.g., if vertex type is EntryVertex do this, if vertex type is ExitVertex do that, etc.) However, I don't know how to determine a vertex's type. The bundles document mentions something about vertex_bundle_type<Graph>::type, but I have no idea how to use this. I couldn't find any code in the Boost examples that use it, either. Any tips to get me started?

That won't help you -- you need the dynamic type of the property, not the static type that would come from vertex_bundle_type. You need to just have a virtual member function (and/or a virtual destructor most likely) in BaseVertex then use typeid or dynamic_cast to find out the subclass stored in any given pointer.

Thanks, but unfortunately I'm still unsure how to solve this problem. For example, I want to do this:

typedef graph_traits<Graph>::vertex_descriptor VertexDescriptor; typedef graph_traits<Graph>::vertex_iterator VertexIterator; ... std::pair vp; for (vp = vertices(graph); vp.first != vp.second; ++vp.first) { VertexDescriptor descriptor = *vp.first; shared_ptr<BaseVertex> vertex = graph[descriptor];

if (vertex is of type shared_ptr<FooVertex>) { <--- pseudocode

Look at dynamic_pointer_cast<FooVertex>(vertex).

doSomething(); } }

Considering that "vertex" is an object instance, not a pointer or reference, I think I'm unable to use dynamic_cast to determine its type. Is there an alternative? (Sorry for what again seems to be a general C++ question...)

"vertex" is a shared pointer, and you care about the dynamic type of what it points to, so dynamic_cast (or dynamic_pointer_cast, the shared_ptr equivalent) will work just fine. -- Jeremiah Willcock