Boost logo

Boost Users :

Subject: [Boost-users] [Graph]remove_edge
From: Moritz Beber (moritz.beber_at_[hidden])
Date: 2008-11-27 10:47:26


Dear members,
using the graph concepts for a case where I frequently add or remove
edges I came across an inconsistency:
removing an edge may invalidate the edge counter because it does not
check whether the edge existed or not. This is the code from the header
file boost/graph/adjacency_matrix.hpp:

template <typename D, typename VP, typename EP, typename GP, typename A>
  void
  remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
u,
              typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
v,
              adjacency_matrix<D,VP,EP,GP,A>& g)
{
    --(g.m_num_edges);
    detail::set_edge_exists(g.get_edge(u,v), false, 0);
}

Whereas in the case of adding an edge the check is done:

template <typename D, typename VP, typename EP, typename GP, typename A>
  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor,
bool>
  add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
           typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
           const EP& ep,
           adjacency_matrix<D,VP,EP,GP,A>& g)
  {
    typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
      edge_descriptor;
    if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) {
      ++(g.m_num_edges);
      detail::set_property(g.get_edge(u,v), ep, 0);
      detail::set_edge_exists(g.get_edge(u,v), true, 0);
      return std::make_pair
        (edge_descriptor(true, u, v,
&detail::get_property(g.get_edge(u,v))),
         true);
    } else
      return std::make_pair
        (edge_descriptor(true, u, v,
&detail::get_property(g.get_edge(u,v))),
         false);
  }

I would suggest a similar check for "remove_edge" instead of blindly
counting down.
Regards,
Moritz


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net