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