Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk