Boost Graph: determining type of bundled property
Hi, I wrote some Boost Graph code that uses a custom pointer type as the vertex: adjacency_list<vecS, vecS, directedS, Foo*, property<edge_index_t, std::size_t> > I now need to expand the graph so that the Foo pointer is just one of several vertex properties. I assume bundled properties are the way to go: http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/bundles.html I also need my vertices to be of different types (but all as children of a base type), such that my vertex bundles look something like this: class BaseVertex { }; class EntryVertex : public BaseVertex { }; class ExitVertex : public BaseVertex { }; class FooVertex : public BaseVertex { Foo *foo; // ... other properties follow ... }; 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? Also, note that I've added an index property to my graph's edges, declared explicitly in the adjacency_list instantiation (as seen above). Would it make sense to convert this to a bundled property as well, or should I leave it as-is? (I don't think I'll ever need any edge properties other than the index.) Thanks, Trevor
On Wed, 7 Apr 2010, Trevor Harmon wrote:
Hi,
I wrote some Boost Graph code that uses a custom pointer type as the vertex:
adjacency_list<vecS, vecS, directedS, Foo*, property<edge_index_t, std::size_t> >
I now need to expand the graph so that the Foo pointer is just one of several vertex properties. I assume bundled properties are the way to go:
http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/bundles.html
I also need my vertices to be of different types (but all as children of a base type), such that my vertex bundles look something like this:
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.
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.
Also, note that I've added an index property to my graph's edges, declared explicitly in the adjacency_list instantiation (as seen above). Would it make sense to convert this to a bundled property as well, or should I leave it as-is? (I don't think I'll ever need any edge properties other than the index.)
No, there's no reason to change that. You can mix bundled and non-bundled properties, and having an edge_index property with that name will make some algorithms easier to call. -- Jeremiah Willcock
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 9, 2010, at 3:59 AM, Dmitry Bufistov wrote:
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 )
I don't see how this is any better than using the built-in typeid. (Assuming of course that enabling RTTI is not a problem.) Trevor
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
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
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
participants (3)
-
Dmitry Bufistov -
Jeremiah Willcock -
Trevor Harmon