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
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
> <http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/property_map.html> 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
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