remove_vertex broken for adjacency_list

[Rasmus Ahlberg <rasmus.ahlberg@…>]

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.

    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.

      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.

      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;
          }
        }
      }