RE: [boost] Graph: remove_edge(g, e)

From: jeremy siek (jsiek_at_[hidden])
Date: 2000-09-27 09:57:47

attached mail follows:

> For implementation reasons (and perhaps also for STL similarity
> reasons), it would be easier to create the function:
>
> remove_edge(graph, out_edge_iterator)

Hi Jeremy,

Thanks for looking into this for me.  I don't have a clear feeling of the
GGCL-internal implications of this choice, so the best I can do is provide
you some insight into where I need to use this call.

In my application, what I have is a graph with internal properties (one on
vertexes and one on edges) storing pointers to the application's own
objects.  I also have a pair of STL maps (members of my RelationGraph
wrapper class) to go the other way (with the pointer to my objects as the
key, and the edge/vertex descriptor as the data).

At the end of this message is my RemoveEdge member function as it stands
today.  It is called when the user or an algorithm needs to remove a
relation between two other objects (which is what the edge models). You can
see that I don't have an out_edge_iterator, though I could find it by
iterating over the out_edges of the source vertex.  I suspect that you'd
have to do the same thing internally given an edge.  So for me, it's really
a matter of whose function does the work.

The only thing I have to say from a library cleanliness point of view is
that the existing remove_vertex() call takes a vertex, not a vertex
iterator.  If you're going to provide remove_edge(graph, out_edge_iterator),
will users turn around and ask you for remove_vertex(graph, vertex_iterator)
(as well as remove_edge(graph, edge_iterator) and remove_edge(graph,
in_edge_iterator))?

I don't really have strong feelings either way; just let me know what you
decide.

Thanks,
-Doug

code follows

----------------

void RelationGraph::RemoveEdge(Relation *rel_ptr)
{
  // N.B. remove_edge() removes all edges from the source to target
vertices.
  // We must save off and restore the ones we don't want deleted!
  map<Relation *,Edge>::iterator i = edge_map.find(rel_ptr);
  if (i != edge_map.end()) {
    // Build list of relations between the two edges, excluding the one
    // we are removing
    Relation_list source_list = rel_ptr->get_source()->get_out_relations();
    Relation_list save_list;
    for (Relation_list::const_iterator j = source_list.begin(); 
         j != source_list.end(); j++) {
      Relation *r_ptr = *j;
      if (r_ptr != rel_ptr && r_ptr->get_target() == rel_ptr->get_target())
        save_list.push_back(r_ptr);
    }
    // Remove the edge (all edges between the two vertices--we have no
choice)
    Edge e = i->second;
    Vertex v1 = source(e, G);
    Vertex v2 = target(e, G);
    remove_edge(G, v1, v2);
    // Put back innocent bystanders
    for (Relation_list::const_iterator j = save_list.begin(); 
         j != save_list.end(); j++) {
      AddEdge(*j);
    }
    edge_map.erase(i);
  }
}