[boost] [Boost-bugs] [ boost-Bugs-1166401 ] remove_edge fails with gcc 3.4.3, likely due to libstdc++

From: SourceForge.net (noreply_at_[hidden])
Date: 2005-03-19 00:50:53

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_at_[hidden]
https://lists.sourceforge.net/lists/listinfo/boost-bugs