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

Subject: Re: [boost] [Boost-users] [BGL] Stoer–Wagner min-cut algorithm
From: Barend Gehrels (barend_at_[hidden])
Date: 2010-06-24 11:05:58

>>>
>>> - 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.

/(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?

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

Thanks, Barend