[Boost-users] [BGL] Segmentation fault in clear_vertex

Subject: [Boost-users] [BGL] Segmentation fault in clear_vertex
From: Daniel Trebbien (dtrebbien_at_[hidden])
Date: 2010-08-29 15:08:52

I am attempting to modify my implementation of the Stoer–Wagner min-cut
algorithm to modify the input graph. In the code sample below, t and s are
vertex_descriptors that were calculated by a call to
boost::detail::stoer_wagner_phase:

        boost::tie(s, t, w) = boost::detail::stoer_wagner_phase(g,
assignments, weights, pq);
        assert(s != t);

         // ...

        std::multimap<vertex_descriptor, edge_descriptor> sOutEdges;
        BGL_FORALL_OUTEDGES_T(s, e, g, UndirectedGraph) {
          const vertex_descriptor u = target(e, g);
          if (t != u) {
            sOutEdges.insert(std::make_pair(u, e));
          }
        }
        BGL_FORALL_OUTEDGES_T(t, e, g, UndirectedGraph) {
          const vertex_descriptor u = target(e, g);
          const weight_type eWeight = get(weights, e);
          typename std::multimap<vertex_descriptor,
edge_descriptor>::iterator sOutEdgesIt, sOutEdgesEnd;
          boost::tie(sOutEdgesIt, sOutEdgesEnd) = sOutEdges.equal_range(u);
          if (sOutEdgesIt != sOutEdgesEnd) {
            for(; sOutEdgesIt != sOutEdgesEnd; ++sOutEdgesIt) {
              put(weights, sOutEdgesIt->second, get(weights,
sOutEdgesIt->second) + eWeight);
            }
          }
          else if (t != u) {
            // need to update e to set the source to s
            edge_descriptor ePrime;
            boost::tie(ePrime, boost::tuples::ignore) = add_edge(s, u, g);
            put(weights, ePrime, eWeight);
          }
        }

         clear_vertex(t, g);

The segmentation fault occurs in the call to clear_vertex, but does not
occur if I comment out the line that adds an edge to the graph g. The type
of g, by the way, is:  boost::adjacency_list<boost::listS, boost::vecS,
boost::undirectedS, boost::no_property,
boost::property<boost::edge_weight_t, int> >

Why does adding an edge between vertices s and target(e, g), both of which
are not equal to t, cause a segmentation fault? For reference, gdb says that
the fault occurs on line 999 of boost/graph/detail/adjacency_list.hpp:

    // O(E/V * E/V)
    template <class Config>
    inline void
    clear_vertex(typename Config::vertex_descriptor u,
                 undirected_graph_helper<Config>& g_)
    {
      typedef typename Config::global_edgelist_selector EdgeListS;
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

      typedef typename Config::graph_type graph_type;
      typedef typename Config::edge_parallel_category Cat;
      graph_type& g = static_cast<graph_type&>(g_);
      typename Config::OutEdgeList& el = g.out_edge_list(u);
      typename Config::OutEdgeList::iterator
        ei = el.begin(), ei_end = el.end();
      for (; ei != ei_end; ++ei) {
        detail::erase_from_incidence_list
          (g.out_edge_list((*ei).get_target()), u, Cat());
        g.m_edges.erase((*ei).get_iter()); *// line 999*
      }
      g.out_edge_list(u).clear();
    }

Program received signal SIGSEGV, Segmentation fault.
std::_List_node_base::unhook (this=0x3d7a38)
    at ../../../../gcc-4.4.0/libstdc++-v3/src/list.cc:134
134     ../../../../gcc-4.4.0/libstdc++-v3/src/list.cc: No such file or
director
y.
        in ../../../../gcc-4.4.0/libstdc++-v3/src/list.cc
(gdb) bt
#0  std::_List_node_base::unhook (this=0x3d7a38)
    at ../../../../gcc-4.4.0/libstdc++-v3/src/list.cc:134
#1  0x0045fa26 in std::list<boost::list_edge<unsigned int,
boost::property<boost
::edge_weight_t, int, boost::no_property> >,
std::allocator<boost::list_edge<uns
igned int, boost::property<boost::edge_weight_t, int, boost::no_property> >
> >:
:_M_erase (this=0x22fa9c, __position=...)
    at
c:/mingw/bin/../lib/gcc/mingw32/4.4.0/include/c++/bits/stl_list.h:1424
#2  0x0045fa0c in std::list<boost::list_edge<unsigned int,
boost::property<boost
::edge_weight_t, int, boost::no_property> >,
std::allocator<boost::list_edge<uns
igned int, boost::property<boost::edge_weight_t, int, boost::no_property> >
> >:
:erase (this=0x22fa9c, __position=...)
    at c:/mingw/bin/../lib/gcc/mingw32/4.4.0/include/c++/bits/list.tcc:111
#3  0x00413ec9 in
boost::clear_vertex<boost::detail::adj_list_gen<boost::adjacen
cy_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property,
boost
::property<boost::edge_weight_t, int, boost::no_property>,
boost::no_property, b
oost::listS>, boost::vecS, boost::listS, boost::undirectedS,
boost::no_property,
 boost::property<boost::edge_weight_t, int, boost::no_property>,
boost::no_prope
rty, boost::listS>::config> (u=5, g_=...)
    at
c:/mingw/bin/../lib/gcc/mingw32/4.4.0/../../../../include/boost/graph/det
ail/adjacency_list.hpp:999
#4  0x0041b0cc in
boost::detail::stoer_wagner_min_cut<boost::adjacency_list<boos
t::listS, boost::vecS, boost::undirectedS, boost::no_property,
boost::property<b
oost::edge_weight_t, int, boost::no_property>, boost::no_property,
boost::listS>
, boost::adj_list_edge_property_map<boost::undirected_tag, int, int&,
unsigned i
nt, boost::property<boost::edge_weight_t, int, boost::no_property>,
boost::edge_
weight_t>, boost::associative_property_map<std::map<int, bool,
std::less<int>, s
td::allocator<std::pair<int const, bool> > > >,
boost::shared_array_property_map
<unsigned int, boost::vec_adj_list_vertex_id_map<boost::no_property,
unsigned in
t> >, boost::d_ary_heap_indirect<unsigned int, 4u,
boost::shared_array_property_
map<unsigned int, boost::vec_adj_list_vertex_id_map<boost::no_property,
unsigned
 int> >, boost::shared_array_property_map<int,
boost::vec_adj_list_vertex_id_map
<boost::no_property, unsigned int> >, std::greater<int>,
std::vector<unsigned in
t, std::allocator<unsigned int> > > > (g=..., weights=...,
    parities=..., assignments=..., pq=...)
...