[Boost-users] [graph] Crash in breadth_first_search

From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-02-19 13:36:02

Can someone help me with the following program? It crashes with Boost 
1.33.1 on gcc34 (GCC) 3.4.3 20050113 (Red Hat 3.4.3-16):

$ ./1
make_map_as_colormap entered
writing something to MapAsColorMap
Speicherzugriffsfehler

I have tracked down the crash to this line in 
<boost/graph/breadth_first_search.hpp>:

for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {

But I don't know what happens there ...

I'm quite sure the bug is NOT in my color map proxy ...

Thanks a lot in advance!

Cheers,

Jens



//
//=======================================================================
// Copyright 2007 University of Karlsruhe
//  Author: Jens Mueller
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
//
#ifndef BFS_DISTMAP_8737
#define BFS_DISTMAP_8737

/* Use distance map (or anything else which suits the following
   requirements) as a color map.

   Write operations are just ignored.

   Read operations work as follows: When the value in the underlying map
   equals a specified value, e.g. -1 in a distance  map, or the null pointer
   in a predecessor map, the 'White' value is returned, otherwise the
   'Black' value is returned.

   Note: This only is usable for application where there is no need to
   distinguish gray and black non-tree edge targets.
   
   Note: Setting the value in the underlying map so that it no longer
   corresponds to a 'White' value will have to be done by the visitor
   on the discover_vertex event.
*/

/* Template parameters:
   - ColorValue (default value used by helper function: default_color_type)
   - ReadablePropertyMap (underlying map)
*/

/* Runtime parameters:
   - ReadablePropertyMap pm
   - ReadablePropertyMap::value_type white
     (must be == comparable)
*/

#include <boost/property_map.hpp>
#include <iostream>

template<typename ReadablePropertyMap, typename ColorValue>
class MapAsColorMap
{
private:
  typename boost::property_traits<ReadablePropertyMap>::value_type white_;
  const ReadablePropertyMap& pm_;
  
public:
  typedef typename boost::property_traits<ReadablePropertyMap>::key_type key_type; 
  typedef ColorValue value_type;
  typedef ColorValue reference;
  typedef boost::read_write_property_map_tag category;
  ColorValue get(key_type key);
  MapAsColorMap(const ReadablePropertyMap& pm,
    typename boost::property_traits<ReadablePropertyMap>::value_type white):
   white_(white), pm_(pm) { /* nothing */ };
};

template<typename ReadablePropertyMap>
MapAsColorMap<ReadablePropertyMap, boost::default_color_type>
make_map_as_colormap(const ReadablePropertyMap& pm,
  typename boost::property_traits<ReadablePropertyMap>::value_type white)
{
  std::cout << "make_map_as_colormap entered" << std::endl;
  
  return MapAsColorMap<ReadablePropertyMap, boost::default_color_type>(pm, white);
}

template<typename ReadablePropertyMap, typename ColorValue>
ColorValue MapAsColorMap<ReadablePropertyMap, ColorValue>::get(key_type key)
{
  std::cout << "get entered" << std::endl;
  std::cout << key << " " << boost::get(pm_, key) << std::endl;
  return (boost::get(pm_, key)==white_) 
     ? boost::color_traits<ColorValue>::white()
     : boost::color_traits<ColorValue>::black();
}

template<typename ReadablePropertyMap, typename ColorValue>
ColorValue get(MapAsColorMap<ReadablePropertyMap, ColorValue> pmap,
  typename boost::property_traits<ReadablePropertyMap>::key_type key)
{
  return pmap.get(key);
}

template<typename ReadablePropertyMap, typename ColorValue>
void put(MapAsColorMap<ReadablePropertyMap, ColorValue> pmap,
  typename boost::property_traits<ReadablePropertyMap>::key_type key,
  typename boost::property_traits<ReadablePropertyMap>::value_type value)
{ std::cout << "writing something to MapAsColorMap" << std::endl;
/* nothing */ }

#endif