Boost logo

Boost :

Subject: Re: [boost] [Boost-users] [BGL] Stoer–Wagner min-cut algorithm
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-06-24 11:26:57

On Thu, 24 Jun 2010, Barend Gehrels wrote:

>>>> - Property maps are passed by copy; they are intended to be lightweight
>>>> and using copies allows temporary property maps to be passed in.
>>> I don't understand this. If I have a graph of one million vertices and
>>> even more edges, the property map (e.g. defining something for each
>>> vertex) is certainly not lightweight. Or do you mean other property maps?
>> The property map is not intended to own the data; thus, copying a property
>> map is only a shallow copy and thus cheap. That is why classes such as
>> iterator_property_map require a separate object for the actual data
>> storage; that object is not copied when the property map is copied.
> OK, I didn't know this and it is AFAIS not written in the property map
> documentation.

It is, but it's hard to find. It's the last sentence of

> /(e.g.: Implementing your own exterior property maps is not very difficult.
> You simply need to overload the functions required by the property map
> concept
> <> that
> you want your class to model. At most, this means overloading the put() and
> get() functions and implementing operator[]. Also, your property map class
> will need to have nested typedefs for all the types defined in
> property_traits, or you can create a specialization of property_traits for
> your new property map type. )
> /A shallow copy of non-owned data will be lightweight indeed.
> What about maps using std::map (e.g. using
> boost::make_assoc_property_map(component)), are they implemented inefficient
> then?

The associative_property_map class works just like iterator_property_map
in that it just has a reference to the std::map or other underlying

> I'm interested in these details because I'm using BGL and implementing a
> graph algorithm on it (where I currently use std::map).

You might want to use iterator_property_map or shared_array_property_map
since those are faster for graphs with fixed sets of vertices.

-- Jeremiah Willcock

Boost list run by bdawes at, gregod at, cpdaniel at, john at