Jeremiah Willcock wrote:

On Wed, 7 Apr 2010, Trevor Harmon wrote:

...

Hi,

[snip].

...

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 I feel that I'm missing something, but what if you store the type of the vertex in the base class: ? class BaseVertex { int m_type; public: BaseVertex() : m_type(0) {} }; struct EntryVertex : public BaseVertex { EtntryVertex() : m_type(1) {} }; Then, you can determine the type of the vertex at run time )

[snip] Dmitry

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

On Apr 29, 2010, at 6:54 PM, Jeremiah Willcock wrote:

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?

The vertex descriptors are the map values, not the map keys. The keys are the properties themselves. (I don't see how it would work otherwise.) It's just like the kevin-bacon example: typedef adjacency_list < vecS, vecS, undirectedS, property < vertex_name_t, std::string >, property < edge_name_t, std::string > > Graph; ... typedef graph_traits < Graph >::vertex_descriptor Vertex; typedef std::map < std::string, Vertex > NameVertexMap; NameVertexMap actors; But I just realized I'm actually still using Foo pointers for my vertex map's keys. Despite switching to shared_ptr for the vertex property, the map's functionality doesn't change, due to the way I'm modeling the data. So there's no need for me to use shared_ptr<BaseVertex> as the key. In other words, as long as the efficiency of std::map is as good with pointers as it is with integers, I've got no worries.

Look at dynamic_pointer_cast<FooVertex>(vertex).

Seems to work perfectly; thanks! Trevor