Dear Cedric L.,

Yes, you're right. It is true that the use of the filtered_graph seems to be very appropriate. However, since I would still need to copy the new graph, it is not clear whether this would save much computational time.

Thank you very much for your suggestion about using vertex_descriptor instead of int. I already encountered some problems when switching from vecS to listS, and couldn't understand where the error was located. I will definitely follow your advice in the future.

Regarding my use of int in vertex_name_t, instead of std::string. This was indeed intended. My vertices are labelled with integers. Would you still recommend that I use std::string to specify the names of these vertices, even though they are integers?

Your final suggestion made me realize that I already have the look-up table that you mentioned. In fact, in my application, the names of the vertices in the subgraph correspond to the indices of the vertices in the main graph. It is therefore completely trivial to clear and remove the vertices in the main graph, by using the names of the ones in the subgraph!

Thanks a lot, that was very useful. Cedric G.

Dear BGL users, > > I am trying to produce a simple routine to extract the subgraph of a > graph, by using the vertex names of the subgraphs. That is, for two > graphs G and H, I want to define the following operator: > G -= H; > Here, the resulting subgraph of G should have all the vertices that H > doesn't have. During this process, the incident edges of the removed > vertices are also removed. I have checked the subgraph class in BGL, but > this refers to a substantially different concept. I have tried the > following code, which works, but is extremely slow for the type of > application that I had in mind: > > ////////////////////////////////////////////////// > class Graph > { > public: > typedef adjacency_list<vecS, vecS, undirectedS, > property<vertex_name_t,int> > UndirectedGraph; > Graph(); > ~Graph(); > int Nv(); // Return number of vertices > Rcpp::IntegerVector V(); // Return vector of NAMES of vertices as > integers. > Graph& operator-= (Graph& H); > private: > UndirectedGraph G; > }; > > ///////////////////////////////////////////////////////////////////////// > // Overloaded Operators. > Graph& Graph::operator-= (Graph& H){ > typedef graph_traits<UndirectedGraph>::vertex_descriptor Vdescriptor; > typedef property_map<UndirectedGraph,vertex_name_t>::type > VertexNameMap; typedef iterator_property_map<int*, identity_property_map> > name_to_vertex_map; > > Rcpp::IntegerVector vec = H.V(); > VertexNameMap NameIndex; > for(ivIter t=vec.begin(); t!=vec.end(); ++t){ > > // Create/Update Iterator map (LValuePropertyMap). > int x[this->Nv()]; NameIndex = get(vertex_name,G); > for(int i=0; i< this->Nv(); ++i) x[NameIndex[i]]=i; > name_to_vertex_map NVmap(x); > > // Remove vertex from name of *t in H. > Vdescriptor u=NVmap[*t]; > clear_vertex(u,G); remove_vertex(u,G); > }//t > return *this; > }//-> ////////////////////////////////////////////////// > > The problem seems to be that I re-create an iterator map (from vertex > NAMES to vertex INDICES) every time I remove a single vertex. This seems > counter-efficient. I would need to be able to create a reference to a > similar map that is automatically updated every time I remove a vertex. > However, since vertices in BGL are indexed from 0 to Nv-1, I don't see a > way to produce a LValuePropertyMap from vertex's names to vertex's indices. > > Any help/opinion would be greatly appreciated,

Maybe a soution would be to use filtered_graph and as the predicate the vertices (or directly names) of H (in the form of a set?!). However, this would require to copy the filtered_graph again into an adjacency_list, which might be costly, depending on your situation. Besides this, I would suggest you to use vertex_descriptor instead of int, as vertex_descriptor is more general and your code will then most likely also work if you decide to change vecS into listS (in case this plays a role). Concerning your code, I am wondering if it is intended that vertex_name_t is of type int and not std::string? The more, when you want to compare each vertex from one graph with each vertex of the other (which you basically have to do for completeness), I would assume this takes quadratic running time and hence will be fairly costly. Unless you have maps that allow a faster lookup, but you will then need to create a map NAMES to INDICES(vertex_descriptor) for one graph and then do something like: name_to_vertex_map_H[getName(vertex_of_G)] and in case this key exists, you can remove vertex_of_G from G, as you have found a vertex with an equivalent name in H. It would then also be nonrelevant if your graph (for simplicity I take G) would have vertices with the same name, as they would all be "mapped" by the name_to_vertex_map_H and thus could be adequately handled. I actually don't see the need to update the map then, because the deleted vertices will not show up again (your iterator went to the next vertex) and if there are different nodes with the same name, they will be taken care of. One thing that comes into my mind when writing you this is that you also should have a look at iterator-invalidation due to the clear_vertex() and remove_vertex(). I am right now not sure if this is critical for vecS or not.

Hope that these thoughts are handy in some way. If not, please let me know.

Best,

Cedric

-- Cedric Ginestet, PhD Centre for Neuroimaging Sciences (L3.04) NIHR Biomedical Research Centre Department of Neuroimaging Institute of Psychiatry, Box P089 King's College London De Crespigny Park London SE5 8AF http://arxiv.org/find/q-bio/1/au:+Ginestet_C/0/1/0/all/0/1