Boost logo

Boost Users :

Subject: [Boost-users] [BGL] remove all children of a given vertex in a directed graph
From: NsPx (nspx.roronoa_at_[hidden])
Date: 2012-05-11 10:36:27


Hi all,

I would like to delete a vertex and all its children vertices in a
directed graph. For example,

  0 <-- 1
  1 <-- 2
  1 <-- 3
  3 <-- 5
0 <-- 4

Removing 1 will remove 2, 3, 5 too.

I have read the doc which explains how to remove all vertices from a
graph but for my case it's a little more complicated and I can't find a
clean way to do it.

Thanks by advance for helping me.

Here is what I planned to do but it isn't working :

###

typedef adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
vertex_info> Graph;
typedef Graph::vertex_descriptor vertexGraph;

Graph* myGraph; //given graph
vertexGraph vpos; //given vertex

vector<vertexGraph> vertsLvl, allChildren;
vector<vertexGraph>::iterator it, ite;

vertsLvl.push_back(vpos);

while( !vertsLvl.empty() )
{
     vector<vertexGraph> tmp; // all children of the vertsLvl's vertices

     for( it=vertsLvl.begin(), ite=vertsLvl.end(); it!=ite; ++it)
     {
         vector<vertexGraph> children;
         this->getChildren(*it, children);

         allChildren.insert( allChildren.end(), children.begin(),
children.end());
         tmp.insert( tmp.end(), children.begin(), children.end());

         // remove edges between vertices from vertsLvl and their children
         clear_in_edges(*it, *myGraph);
     }

     vertsLvl = tmp;
}

// remove all children and the given vertex : doesn't work
for( it=allChildren.begin(), ite=allChildren.end(); it!=ite; ++it)
{
     remove_vertex(*it, *myGraph);
}

###



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