[boost] possible optimization to adjacency_list?

From: Vikram Shrowty (vikram_at_[hidden])
Date: 2005-03-17 20:49:40

Hullo boost gurus,

     The code at  detail/adjacency_list.hpp:1815 is currently like
this...

  remove_vertex_dispatch(Graph& g, vertex_descriptor u,
                             boost::bidirectional_tag)
      {
       //....
        g.m_vertices.erase(g.m_vertices.begin() + u);
       //...
        for (v = 0; v < V; ++v)
          reindex_edge_list(g.out_edge_list(v), u,
                            edge_parallel_category());
       //...

If I am understanding this correctly, after erasing a vertex we go
through all vertices in the graph and reindex their edges/ This is
because there may be edges to/from vertices after u. But this can be
avoided if u was the last vertex in the graph, right?

So this...  
    //....
        g.m_vertices.erase(g.m_vertices.begin() + u);
    //....
       if (u != num_vertices(g)) {
     //all the re-indexing code
    }

is a valid optimization isn't it?

My graph grows and shrinks a lot (but always at highest vertex number)
and this code change had a dramatic effect on runtime. 

-- 
Vikram Shrowty <vikram_at_[hidden]>