Bugs item #1166401, was opened at 2005-03-18 21:50 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1166401&group_id=7586 Category: graph Group: None Status: Open Resolution: None Priority: 5 Submitted By: Nobody/Anonymous (nobody) Assigned to: Jeremy Siek (jsiek) Summary: remove_edge fails with gcc 3.4.3, likely due to libstdc++ Initial Comment: In certain situations a call to remove_edge fails to accomplish the removal. I believe this is dues to a problem with std::equal_range in libstdc++ in gcc 3.4.3 but until this is fixed a workaround in boost that does not use equal_range could fix this problem. The attached test program shows the problem. On line 68 removing p24 is ok but removing p12 silently fails, that is after completion the output shows 3 vertices and 3 edges remaining in the graph while it should have only 3 vertices and 2 edges left. The point of failure is the following call stack: (gdb) where #0 std::equal_range<std::_List_iterator<boost::detail::sei_<void*, std::_List_iterator<boost::list_edge<void*, boost::property<BoostEdgeContentType, int*, boost::no_property> > >, boost::property<BoostEdgeContentType, int*, boost::no_property> > >, boost::detail::sei_<void*, std::_List_iterator<boost::list_edge<void*, boost::property<BoostEdgeContentType, int*, boost::no_property> > >, boost::property<BoostEdgeContentType, int*, boost::no_property> > > (__first= {_M_node = 0x804f098}, __last={_M_node = 0x804f098}, __val=@0xbfffecc0) at /apps/utkej_projects/Argonne/gcc-3.4.3_inst/lib/gcc/i686-pc-linux-gnu/3.4.3/../../../../include/c++/3.4.3/bits/stl_algo.h:3814 #1 0x0804a8e9 in boost::edge_range<boost::detail::adj_list_gen<boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, boost::property<BoostVertexContentType, int*, boost::no_property>, boost::property<BoostEdgeContentType, int*, boost::no_property>, boost::no_property, boost::listS>, boost::listS, boost::listS, boost::bidirectionalS, boost::property<BoostVertexContentType, int*, boost::no_property>, boost::property<BoostEdgeContentType, int*, boost::no_property>, boost::no_property, boost::listS>::config, boost::bidirectional_graph_helper_with_property<boost::detail::adj_list_gen<boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, boost::property<BoostVertexContentType, int*, boost::no_property>, boost::property<BoostEdgeContentType, int*, boost::no_property>, boost::no_property, boost::listS>, boost::listS, boost::listS, boost::bidirectionalS, boost::property<BoostVertexContentType, int*, boost::no_property>, boost::property<BoostEdgeContentType, int*, boost::no_property>, boost::no_property, boost::listS>::config> > (u=0x804f098, v=0x804f068, g_=@0xbfffeea0) at /apps/utkej_projects/Argonne/boost_1_32_0/boost/graph/detail/adjacency_list.hpp:1485 #2 0x08049d8e in boost::bidirectional_graph_helper_with_property<boost::detail::adj_list_gen<boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, boost::property<BoostVertexContentType, int*, boost::no_property>, boost::property<BoostEdgeContentType, int*, boost::no_property>, boost::no_property, boost::listS>, boost::listS, boost::listS, boost::bidirectionalS, boost::property<BoostVertexContentType, int*, boost::no_property>, boost::property<BoostEdgeContentType, int*, boost::no_property>, boost::no_property, boost::listS>::config>::remove_edge (this=0xbfffeea0, e= {<boost::detail::edge_base<boost::bidirectional_tag,void*>> = {m_source = 0x804f098, m_target = 0x804f068}, m_eproperty = 0x804f0d8}) at /apps/utkej_projects/Argonne/boost_1_32_0/boost/graph/detail/adjacency_list.hpp:1067 #3 0x080495aa in boost::remove_edge<boost::detail::edge_desc_impl<boost::bidirectional_tag, void*>, boost::detail::adj_list_gen<boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, boost::property<BoostVertexContentType, int*, boost::no_property>, boost::property<BoostEdgeContentType, int*, boost::no_property>, boost::no_property, boost::listS>, boost::listS, boost::listS, boost::bidirectionalS, boost::property<BoostVertexContentType, int*, boost::no_property>, boost::property<BoostEdgeContentType, int*, boost::no_property>, boost::no_property, boost::listS>::config> (e= {<boost::detail::edge_base<boost::bidirectional_tag,void*>> = {m_source = 0x804f098, m_target = 0x804f068}, m_eproperty = 0x804f0d8}, g_=@0xbfffeea0) at /apps/utkej_projects/Argonne/boost_1_32_0/boost/graph/detail/adjacency_list.hpp:1110 #4 0x0804906a in main () at gv2.cpp:70 (gdb) Basically the problem is in stl_algo,h when __len on 3801 is initally 2 and __val in our case equals the second element and the condition on 3810 holds true. Note that for this to happen the vertices and edges in the graph need to be created in a certain order. In any case, under the above conditions we compute at 3814 __len to be 0 and __first becomes equal to __last. I.e. we don't ever look at the second element in the list which is the one we SHOULD find. 3784 template<typename _ForwardIterator, typename _Tp> 3785 pair<_ForwardIterator, _ForwardIterator> 3786 equal_range(_ForwardIterator __first, _ForwardIterator __last, 3787 const _Tp& __val) 3788 { 3789 typedef typename iterator_traits<_ForwardIterator>::value_type 3790 _ValueType; 3791 typedef typename iterator_traits<_ForwardIterator>::difference_type 3792 _DistanceType; 3793 3794 // concept requirements 3795 // See comments on lower_bound. 3796 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3797 __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>) 3798 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 3799 __glibcxx_requires_partitioned(__first, __last, __val); 3800 3801 _DistanceType __len = std::distance(__first, __last); 3802 _DistanceType __half; 3803 _ForwardIterator __middle, __left, __right; 3804 3805 while (__len > 0) 3806 { 3807 __half = __len >> 1; 3808 __middle = __first; 3809 std::advance(__middle, __half); 3810 if (*__middle < __val) 3811 { 3812 __first = __middle; 3813 ++__first; 3814 __len = __len - __half - 1; 3815 } 3816 else if (__val < *__middle) Subsequently the rng returns the end/end and the edge in question never gets deleted because of edge_range(source(e, g), target(e, g), g); rng.first = std::find(rng.first, rng.second, e); if (rng.first != rng.second) remove_edge(rng.first); } in graph/detail/adjacency_list.hpp unfortunately without warning. Temporarily not using equal_range should fix it. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1166401&group_id=7586 ------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_id=6595&alloc_id=14396&op=click _______________________________________________ Boost-bugs mailing list Boost-bugs@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs