From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-02-15 08:43:08
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.
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
> 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:
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:
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk