Boost Users :

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
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
#4 0x0041b0cc in
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>
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