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