Boost logo

Boost :

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

  remove_vertex_dispatch(Graph& g, vertex_descriptor u,
        g.m_vertices.erase(g.m_vertices.begin() + u);
        for (v = 0; v < V; ++v)
          reindex_edge_list(g.out_edge_list(v), u,

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]>

Boost list run by bdawes at, gregod at, cpdaniel at, john at