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

Subject: Re: [Boost-users] Boost Graph: determining type of bundled property
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-04-29 21:54:12

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

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