remove_edge fails with gcc 3.4.3, likely due to libstdc++

[nobody]

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. 

[nobody]

Logged In: NO 

Actually, as I was trying to come up with an list<int>
example for this 
I realized the obvious, i.e. that the whole equal_range
approach only makes
sense when we have  a list that has been populated in the order 
implied by the comparison operator used on line 3810 in 
stl_algo.h  (see above).  
So,  I suspect the boost edge lists are not populated in
that order 
and consequently  it does not make sense to call equal_range 
for an unordered list  (notice that in my example code  I
use listS, 
not vecS).   
I haven't really verified this, but  now it seems to make
sense. 

[Douglas Gregor]

Logged In: YES 
user_id=249098

Fixed in 1.33.0.