Re: [boost] Boost.Graph - covering PropertyGraphConcept

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.

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

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