Brook Milligan wrote:
I am trying to write a new type that covers some of the Graph concepts. I seem to be able to get most of the concepts covered except the PropertyGraph concept. I am having trouble figuring out the various types that are required (e.g., for property_map, etc.).
Are there any straightforward examples of types that cover PropertyGraph and allow arbitrary (i.e., templated) types to be the vertex and edge properties?
Thanks for your help.
Hi Brook, I'm not sure I understand the exact scope of your question/problem. The concept is explained at http://www.boost.org/libs/graph/doc/PropertyGraph.html. As far as I understand it, the concept is kind of parameterized with a tag type. So if a class Graph models the PropertyGraph<PropertyTag> concept, boost::property_map<G, PropertyTag>::type must exist (same for const_type), and the other expressions mentioned there must be defined, and have the specified meanings. As the page mentions, adjacency_list with VertexProperty=property<vertex_distance_t,int,property<vertex_in_degree_t,int>
is a model of PropertyGraph<vertex_distance_t> and PropertyGraph<vertex_in_degree_t>. However, I think the implementation is not completely straightforward. Without looking at the code, I think with recursive template instantion there is built a "multi-level" datastructure (like a struct with the first property as one member, and a struct for the rest of the properties as the other member - recursion ends then with an empty struct for no_property); this ultimately results in "flat" layout without unnecessary indirections - for accesses such stuff is done again - expensive at compile time, eficient at run-time.
For docs see here: http://www.boost.org/libs/graph/doc/using_adjacency_list.html#sec:adjacency-... Furthermore, I have some problems with the sentence "The object p is only used to carry the type." -- this, as far as I understand it, excludes bundled properties, because there, the "tag" type isn't really a tag, but "pointer to member of the struct given as property parameter for [edge/vertex/graph]". So here, the value is also important, because there might be several members with the same type (e.g., int), and they won't have different tags. IMO, this sentence is an unnecessary restriction. It should be replaced by an explanation covering both internal and bundled properties. For bundled properties, in each vertex/edge there is stored a struct of the type given as template parameter, and a property map basically consists of a pointer to the graph and a member pointer to the relevant field in the struct. I think this might be a bit more straightforward. Docs for bundled properties are here: http://www.boost.org/libs/graph/doc/bundles.html I'm just a user myself, but please feel free to ask any further questions. Please reply on the list, there are too few discussions on usage of BGL anyway, IMO. Cheers, Jens