Re: [Boost-users] [BGL] Remove all vertices from graph with zero degree

From: Johan Oudinet (johan.oudinet_at_[hidden])
Date: 2005-12-15 16:28:41

On 12/15/05, Dmitry Bufistov <dmitry_at_[hidden]> wrote:
> Hi all again!
>
> I would really appreciate any ideas how to implement (subject)
> efficiently with bearing in mind "Iterator" stability. Graph
> representation is the following:
>
> typedef adjacency_list<
>   listS, ///<Store out-edges of each vertex in a std::list
>   vecS, ///<Store vertex set in  std::vector
>   bidirectionalS, ///<Graph is directed but with access to in & out edges
>   VertexProperties, EdgeProperties,
>   GraphProperties
>   > Graph;
>
> filtered_graph seems isn't what I need. I would like to right as follow
>
> Graph g;
> remove_empty_vertices(g);
> //Now g doesn't contain zero degree vertices

Do you need a vector to store your vertex ? With a vector, you can't
remove (or add) vertices without invalidated all your vertex
iterators.

I suggest you to use a listS or setS for your vertex set. Thus, you
can write your remove_empty_vertices function like this:

template < class Graph >
void remove_empty_vertices(Graph& g)
{
  BGL_FORALL_VERTICES(v, g, Graph)
  {
    if (degree (v, g) == 0)
      remove_vertex (v, g);
  }
}

else, I don't see an efficient way to do it. (I think you have to
restart the loop when you remove a vertex)

>
> Many thanks in advance,
>
> regards,

There may be a better solution... but choose your vertex set container
carefully:
<quote=http://www.boost.org/libs/graph/doc/adjacency_list.html>
In general, if you want your vertex and edge descriptors to be stable
(never invalidated) then use listS or setS for the VertexList and
OutEdgeList template parameters of adjacency_list. If you are not as
concerned about descriptor and iterator stability, and are more
concerned about memory consumption and graph traversal speed, use vecS
for the VertexList and/or OutEdgeList template parameters.
</quote>
--
Johan