[BGL] Remove all vertices from graph with zero degree
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
On 12/15/05, Dmitry Bufistov <dmitry@lsi.upc.edu> 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
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
participants (3)
-
Dmitry Bufistov -
Jeffrey Holle -
Johan Oudinet