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

Subject: Re: [Boost-users] Boost Graph: determining type of bundled property
From: Trevor Harmon (Trevor.W.Harmon_at_[hidden])
Date: 2010-04-29 21:15:35

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

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

Trevor