...

: :_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

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> > 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=...) ...