Re: [boost] [Boost-users] [BGL] Stoer–Wagner min-cut algorithm

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

> /(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 
> <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 
> 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 
storage.

> 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