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

From: Jeffrey Holle (jeffreyholle_at_[hidden])
Date: 2005-12-15 18:49:58

The way that I had to implement a template function to erase a graph was like:
template<typename T1> inline void
WorkFlow_Datum::EraseGraph(T1& g)
{
   typedef typename std::vector<typename 
boost::graph_traits<T1>::vertex_descriptor> Vertices;
   Vertices vertices;
   typename boost::graph_traits<T1>::vertex_iterator vi,vi_end;
   for (boost::tie(vi,vi_end)=boost::vertices(g);vi!=vi_end;++vi)
     vertices.push_back(*vi);
   for (typename Vertices::reverse_iterator 
iter=vertices.rbegin();iter!=vertices.rend();++iter) {
     boost::clear_vertex(*iter,g);
     boost::remove_vertex(*iter,g);
   }
}

My graph uses vectors, so I suspect that you need to use something similiar to 
avoid iterator instability and vertice descriptor instability.  The later is way 
a reverse iterator was needed.

Dmitry Bufistov 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
> 
> Many thanks in advance,
> 
> regards,
> --dima