Re: [Boost-users] [BGL] Using a default-constructed property map for storing temporary vertex properties

Subject: Re: [Boost-users] [BGL] Using a default-constructed property map for storing temporary vertex properties
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-06-18 10:07:38

On Thu, 17 Jun 2010, Daniel Trebbien wrote:

> Hello all,
>
> I am currently working on a generic implementation of the Stoer–Wagner
> min-cut algorithm using BGL. Crucial to the algorithm is the merging
> of a vertex s into a vertex t after each phase, creating a new view of
> the input graph, the merged graph, denoted G/{s, t}. Rather than
> create a new graph that represents the merged graph, I figured that I
> could use a vertex property that would be the vertex that each vertex
> is assigned to at the start of each phase.
>
> One of the template parameters of my implementation is the property
> map type of the "assignment" property map. It is the last template
> parameter, as it's not as important to the algorithm as others, but I
> wanted the user to be able to provide the assignment property map type
> if s/he wanted, otherwise, the implementation would use a "default"
> property map type and default-constructed instance of the default
> assignment property map type.
>
> I tried `boost::associative_property_map<std::map<vertex_descriptor,
> vertex_descriptor> >`, which can be default-constructed, but the first
> time that I call `boost::get` or `boost::put` on the property map
> object, I get a SEGFAULT. Apparently, the default construction of
> `boost::associative_property_map<std::map<vertex_descriptor,
> vertex_descriptor> >` did not default-construct a
> `std::map<vertex_descriptor, vertex_descriptor>` object for use in
> storing the vertex property values.
>
> Is there some other property map type that I can use for this purpose?

The usual idiom for that in BGL algorithms is to use an 
iterator_property_map on the graph's vertices, built using a vector and 
indexed by the vertex_index property map of the graph.  You can also use a 
shared_array_property_map, which manages its storage internally.  If you 
are doing a generic algorithm, the logic to manage these maps correctly is 
somewhat difficult.  One place to look for a template of what to do is the 
distance map handling at the bottom of 
<boost/graph/dijkstra_shortest_paths.hpp>, particularly 
dijkstra_shortest_paths() and detail::dijkstra_dispatch1().  The basic 
logic is to look at the named parameter structure that the user passes is 
and see if there is an assignment map there.  If so, use it; otherwise, 
look for a vertex_index map in the named parameter structure, defaulting 
to get(vertex_index, g), then use the found vertex_index map to create an 
iterator_property_map or shared_array_property_map.  Now that compilers 
are more compliant, there are probably simpler ways to implement the logic 
than to use multiple dispatch functions, but the approach in 
dijkstra_shortest_paths.hpp is known to work.

When you get this algorithm done, you may want to contribute it to BGL to 
be added to Boost.  We are always interested in new algorithms.

-- Jeremiah Willcock