[BGL] bundled properties and their restrictions (particularly default constructibility).
Hi, my graph uses bundled properties for both vertices and edges. Both bundled properties have containers that must be of a certain size when they're actually used. For testing purposes these containers were of fixed size (underlying container is currently a boost::array<..>. However the real world dictates that the size of these containers pretty much must be determined at run-time as opposed to compile-time because the graph is built using an external source such as a file or database for example. I know the documentation requires that bundled properties be all of default constructible, assignable and copy constructible[1][2] because of how the containers (as specified by selectors) store them. I'm unsure as to whether or how this may effect algorithms provided by the BGL, so far the only ones I've used are dijkstra_shortest_path and dag_shortest_path. Given that a custom container selector may be created and push/erase must be overloaded for the given custom container (for my purposes, this would be to specify a custom allocator as in the example)[3], how safe would it be to say that the container selector entirely dictates the restrictions in question? If the answer is "very", presuming we weren't to change these restrictions for existing provided selectors would it be possible for an explicit exception to be made for custom containers and their selectors (created using boost::container_gen<>)? This exception might say that the restrictions in question are then dictated by the custom container. I figure this shouldn't affect existing user code since the current restrictions are already at their most strict. Thanks very much, Geoff [1] http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/using_adjacency_list.htm... [2] Doug Gregor 23/03/2005, this list. [3] http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/using_adjacency_list.htm...
Geoff Hilton wrote:
Hi, my graph uses bundled properties for both vertices and edges. Both bundled properties have containers that must be of a certain size when they're actually used. For testing purposes these containers were of fixed size (underlying container is currently a boost::array<..>.
However the real world dictates that the size of these containers pretty much must be determined at run-time as opposed to compile-time because the graph is built using an external source such as a file or database for example.
I know the documentation requires that bundled properties be all of default constructible, assignable and copy constructible[1][2] because of how the containers (as specified by selectors) store them. I'm unsure as to whether or how this may effect algorithms provided by the BGL, so far the only ones I've used are dijkstra_shortest_path and dag_shortest_path.
Given that a custom container selector may be created and push/erase must be overloaded for the given custom container (for my purposes, this would be to specify a custom allocator as in the example)[3], how safe would it be to say that the container selector entirely dictates the restrictions in question?
If the answer is "very", presuming we weren't to change these restrictions for existing provided selectors would it be possible for an explicit exception to be made for custom containers and their selectors (created using boost::container_gen<>)? This exception might say that the restrictions in question are then dictated by the custom container. I figure this shouldn't affect existing user code since the current restrictions are already at their most strict.
Thanks very much, Geoff
[1] http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/using_adjacency_list.htm...
[2] Doug Gregor 23/03/2005, this list. [3] http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/using_adjacency_list.htm...
This is just a bump of sorts, I'm still very much in need of a reply. Note, in [2], I meant the boost.user list, not boost.devel. Thanks, Geoff
This is just a bump of sorts, I'm still very much in need of a reply. Note, in [2], I meant the boost.user list, not boost.devel.
Geoff, Sorry I missed this, my mail filter didn't pick up the BGL subject... Given that a custom container selector may be created and push/erase must be
overloaded for the given custom container (for my purposes, this would be to specify a custom allocator as in the example)[3], how safe would it be to say that the container selector entirely dictates the restrictions in question?
If the answer is "very", presuming we weren't to change these restrictions for existing provided selectors would it be possible for an explicit exception to be made for custom containers and their selectors (created using boost::container_gen<>)? This exception might say that the restrictions in question are then dictated by the custom container. I figure this shouldn't affect existing user code since the current restrictions are already at their most strict.
Thanks very much, Geoff
I'm not entirely sure what restrictions you're referring to with regard to the selectors... that the containers within your bundled properties are grown at run time (as with a list or vector) or fixed at compile time (as with array)? In general, the selectors have a little to do with vertex/edge properties (including bundles) as possible, so the impact on generic algorithms is probably negligible - unless you're doing something interesting like parallel or distributed graphs. My feeling is that if you're considering building your own selector, then you may be over-thinking the problem. Of course, I could also be completely misunderstanding the point of your question. Is there any way to give an example of what you're trying to do? Andrew Sutton andrew.n.sutton@gmail.com
Andrew Sutton wrote:
This is just a bump of sorts, I'm still very much in need of a reply. Note, in [2], I meant the boost.user list, not boost.devel.
Geoff,
Sorry I missed this, my mail filter didn't pick up the BGL subject...
overloaded for the given custom container (for my purposes, this would be to specify a custom allocator as in the example)[3], how safe would it be to say that the container selector entirely dictates the restrictions in question?
If the answer is "very", presuming we weren't to change these restrictions for existing provided selectors would it be possible for an explicit exception to be made for custom containers and their selectors (created using boost::container_gen<>)? This exception might say that the restrictions in question are then dictated by the custom container. I figure this shouldn't affect existing user code since the current restrictions are already at their most strict.
Thanks very much, Geoff
I'm not entirely sure what restrictions you're referring to with regard to
Given that a custom container selector may be created and push/erase must be the selectors... that the containers within your bundled properties are grown at run time (as with a list or vector) or fixed at compile time (as with array)?
By restrictions I was referring to the requirements of bundled properties as mentioned in my previous e-mails:
I know the documentation requires that bundled properties be all of default > constructible, assignable and copy constructible[1][2] because of how the containers (as specified by selectors) store them.
I realize now that using the word "restrictions" is probably what confused you, sorry about that. When I said "as specified by selectors" I was merely stating the fact that the containers that the boost::adjacency_list uses are specified using the selectors. The requirements imposed on the bundled properties exist because of requirements imposed by the containers represented by the respective selectors (vecS for std::vector, listS for std::list, etc) in the boost::adjacency_list type parameters OutEdgeList, VertexList, and EdgeList (see footnote 2 of previous e-mails). My wanting to create a custom selector (an somewhat unrelated issue which I was mentioning as a side note) for the purposes of specifying a custom allocator are because the graphs can and will get quite large (read: several gigabytes of RAM in size for relatively medium-sized graphs), the custom allocator will help ease performance bottlenecks through preallocation of large blocks of memory.
In general, the selectors have a little to do with vertex/edge properties (including bundles) as possible, so the impact on generic algorithms is probably negligible - unless you're doing something interesting like parallel or distributed graphs. My feeling is that if you're considering building your own selector, then you may be over-thinking the problem. Of course, I could also be completely misunderstanding the point of your question. Is there any way to give an example of what you're trying to do?
Andrew Sutton andrew.n.sutton@gmail.com
A simple example of how it is currently: template<size_t Count> struct EdgeProperty { boost::array<int,Count + 1> Weights; }; This approach respects all bundled property requirements, however the number of weights must be known at compilation. struct EdgeProperty { EdgeProperty(size_t weightCount):Weights(weightCount + 1){} std::vector<int> Weights; }; This approach respects copy constructible and assignable, but not default constructible. However the parameter passed in will never change once it has been determined upon reading the graph information from the file or database. I don't know why I didn't think of this sooner, but something similar to this should work for me: struct EdgeProperty { EdgeProperty():Weights(_count){} std::vector<int> Weights; static void SetInitialCount(size_t count) { _count = count; } private: static size_t _count; }; This is rather hacky in that our code would only work as long as SetInitialCount is called once before the first EdgeProperty instance is created but oh well, whatever works! I think that renders my question/request moot, so never mind and thanks for listening to my rambling thought process. :)
Geoff Hilton wrote:
Andrew Sutton wrote:
This is just a bump of sorts, I'm still very much in need of a reply. Note, in [2], I meant the boost.user list, not boost.devel.
Geoff,
Sorry I missed this, my mail filter didn't pick up the BGL subject...
overloaded for the given custom container (for my purposes, this would be to specify a custom allocator as in the example)[3], how safe would it be to say that the container selector entirely dictates the restrictions in question?
If the answer is "very", presuming we weren't to change these restrictions for existing provided selectors would it be possible for an explicit exception to be made for custom containers and their selectors (created using boost::container_gen<>)? This exception might say that the restrictions in question are then dictated by the custom container. I figure this shouldn't affect existing user code since the current restrictions are already at their most strict.
Thanks very much, Geoff
I'm not entirely sure what restrictions you're referring to with regard to
Given that a custom container selector may be created and push/erase must be the selectors... that the containers within your bundled properties are grown at run time (as with a list or vector) or fixed at compile time (as with array)?
By restrictions I was referring to the requirements of bundled properties as mentioned in my previous e-mails:
I know the documentation requires that bundled properties be all of default > constructible, assignable and copy constructible[1][2] because of how the containers (as specified by selectors) store them.
I realize now that using the word "restrictions" is probably what confused you, sorry about that. When I said "as specified by selectors" I was merely stating the fact that the containers that the boost::adjacency_list uses are specified using the selectors.
The requirements imposed on the bundled properties exist because of requirements imposed by the containers represented by the respective selectors (vecS for std::vector, listS for std::list, etc) in the boost::adjacency_list type parameters OutEdgeList, VertexList, and EdgeList (see footnote 2 of previous e-mails).
My wanting to create a custom selector (an somewhat unrelated issue which I was mentioning as a side note) for the purposes of specifying a custom allocator are because the graphs can and will get quite large (read: several gigabytes of RAM in size for relatively medium-sized graphs), the custom allocator will help ease performance bottlenecks through preallocation of large blocks of memory.
In general, the selectors have a little to do with vertex/edge properties (including bundles) as possible, so the impact on generic algorithms is probably negligible - unless you're doing something interesting like parallel or distributed graphs. My feeling is that if you're considering building your own selector, then you may be over-thinking the problem. Of course, I could also be completely misunderstanding the point of your question. Is there any way to give an example of what you're trying to do?
Andrew Sutton andrew.n.sutton@gmail.com
A simple example of how it is currently:
template<size_t Count> struct EdgeProperty { boost::array<int,Count + 1> Weights; };
This approach respects all bundled property requirements, however the number of weights must be known at compilation.
struct EdgeProperty { EdgeProperty(size_t weightCount):Weights(weightCount + 1){}
std::vector<int> Weights; };
This approach respects copy constructible and assignable, but not default constructible. However the parameter passed in will never change once it has been determined upon reading the graph information from the file or database.
I don't know why I didn't think of this sooner, but something similar to this should work for me:
struct EdgeProperty { EdgeProperty():Weights(_count){} std::vector<int> Weights; static void SetInitialCount(size_t count) { _count = count; } private: static size_t _count; };
This is rather hacky in that our code would only work as long as SetInitialCount is called once before the first EdgeProperty instance is created but oh well, whatever works!
I think that renders my question/request moot, so never mind and thanks for listening to my rambling thought process. :)
Oh, a further explanation on this bit:
The requirements imposed on the bundled properties exist because of requirements imposed by the containers represented by the respective selectors (vecS for std::vector, listS for std::list, etc) in the boost::adjacency_list type parameters OutEdgeList, VertexList, and EdgeList (see footnote 2 of previous e-mails).
Prior to thinking of the simple static function, the only thing I could think of to make sure that the container (called "Weights" in my examples) was the proper size was through the use of the first (current) implementation using boost::array. Since I have something akin to the following defined: template<size_t Count> struct edge_prop_gen { typedef boost::property_map<Graph, boost::array<int, Count> EdgeProp::*>::type edge_prop_t; }; (where EdgeProp is the EdgeProperty struct, and Graph is the boost::adjacency_list<..>) This meant that the arrays contained in the DistanceMap (among other things?) are properly sized automatically. Please correct me if I'm wrong, but if I understand correctly, is this what renders the bundled property subject to the requirements?
participants (2)
-
Andrew Sutton -
Geoff Hilton