Boost logo

Boost Users :

Subject: [Boost-users] [BGL] Subgraphs: Name-to-Index Property Map.
From: Cedric Ginestet (c.ginestet05_at_[hidden])
Date: 2011-05-25 04:54:07


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,

-- 
Cedric Ginestet
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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net