[Boost-bugs] [Boost C++ Libraries] #13544: remove_vertex broken for adjacency_list

Subject: [Boost-bugs] [Boost C++ Libraries] #13544: remove_vertex broken for adjacency_list
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2018-04-27 12:59:47

#13544: remove_vertex broken for adjacency_list
-----------------------------------------------+---------------------------
 Reporter:  Rasmus Ahlberg <rasmus.ahlberg@…>  |      Owner:  Jeremiah
                                               |  Willcock
     Type:  Bugs                               |     Status:  new
Milestone:  To Be Determined                   |  Component:  graph
  Version:  Boost 1.66.0                       |   Severity:  Problem
 Keywords:                                     |
-----------------------------------------------+---------------------------
 Create a graph with three nodes, with the third node having an edge to the
 first node. Calling remove_vertex on the second node will then corrupt the
 m_property attribute of the edge of the third node.

 The graph template parameters are as follows. I'm not including the
 property classes' content.

 {{{#!c++
     typedef boost::adjacency_list<boost::setS, // Container type for edges
                                   boost::vecS, // Container type for
 vertices
                                   boost::directedS, // Param for
                                   // directed/undirected/bidirectional
                                   // graph
                                   Vertex, // Type for the vertices
                                   Edge    // Type for the edges
                                   > Graph_t;
 }}}

 The culprit is the following method, in your adjacency_list.hpp.

 {{{#!c++
       template <class EdgeList, class vertex_descriptor>
       inline void
       reindex_edge_list(EdgeList& el, vertex_descriptor u,
                         boost::disallow_parallel_edge_tag)
       {
         typename EdgeList::iterator ei = el.begin(), e_end = el.end();
         while (ei != e_end) {
           typename EdgeList::value_type ce = *ei;
           ++ei;
           if (ce.get_target() > u) {
             el.erase(ce);
             --ce.get_target();
             el.insert(ce);
           }
         }
       }
 }}}

 When initializing the variable ce, its m_property field, which is a
 unique_ptr, is stolen from *ei, setting ei's field to null. If get_target
 is not bigger than u, ce is not re-inserted in el, leaving the old copy
 with the null pointer.

 Below is a suggested and tested fix.

 {{{#!c++
       template <class EdgeList, class vertex_descriptor>
       inline void
       reindex_edge_list(EdgeList& el, vertex_descriptor u,
                         boost::disallow_parallel_edge_tag)
       {
         typename EdgeList::iterator ei = el.begin(), e_end = el.end();
         while (ei != e_end) {
           if (ei->get_target() > u) {
             typename EdgeList::value_type ce = *ei;
             ++ei;
             el.erase(ce);
             --ce.get_target();
             el.insert(ce);
           }
           else
           {
             ++ei;
           }
         }
       }
 }}}

-- 
Ticket URL: <https://svn.boost.org/trac10/ticket/13544>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.