Re: [Boost-users] [BGL] Subgraphs: Name-to-Index Property Map.

Subject: Re: [Boost-users] [BGL] Subgraphs: Name-to-Index Property Map.
From: Cedric Ginestet (c.ginestet05_at_[hidden])
Date: 2011-05-25 12:23:01

> 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