Re: [Boost-users] bgl - add_vertex during breadth first

From: Abebaw Wubshet (a.wubshet_at_[hidden])
Date: 2005-09-06 07:33:29

Hi Jeremy,

Many thanks for the response. I was hoping I could add vertices inside
the algorithm visitor based on some conditions and these same conditions
will be applied when the newly added vertices are visited by calling the
algorithm only once (a kind of recursive effect). Now it seems that I
have to call the algorithm many times and introduce some sort of my own
implementation of colour or add a property to each vertex which flags
whether it is already expanded or not. Is there any better idea?

Cheers,
Abebaw

> Message: 5
> Date: Mon, 5 Sep 2005 17:19:21 -0500
> From: Jeremy Siek <jeremy.siek_at_[hidden]>
> Subject: Re: [Boost-users] bgl - add_vertex during breadth first
> 	search
> To: boost-users_at_[hidden]
> Message-ID: <BE018FBF-735B-4948-8B2A-66793695F214_at_[hidden]>
> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed
> 
> Hi Abebaw,
> 
> Adding vertices and edges is a dangerous thing to do inside an
> algorithm visitor. This is because doing that invalidates
> iterators that the algorithm is using.  Also, the algorithm
> creates a mapping from vertices to colors (to mark
> which vertices have been processed), and adding vertices
> will mess up that mapping. Can you just record that
> you want to add vertices and do it after the BFS?
> 
> Cheers,
> Jeremy
> 
> On Sep 4, 2005, at 7:43 AM, Abebaw Wubshet wrote:
> > Hi all,
> >
> > I have started using the boost graph library recently. I want to
> > add vertices
> > and edges to a graph through an algorithm visitor. I chose the
> > 'discover_vertex'
> > event and added some code to add a vertex/edge. But the compiler
> > could not
> > determine the apporpriate the matching add_vertex/add_edge
> > function. I tried
> > fully specifiying the template arguments with no success. (I am
> > using gcc 3.3.1
> > on SuSE Linux.)
> >
> > I tried another alternative which does not work either. I created a
> > pointer to a
> > graph object which points to my graph insided the
> > 'discover_vertex'. But then I
> > ended up having a run time error after the vertex is added.
> >
> > Many thanks,
> > Abebaw Wubshet
> >
> >
> > Here is a sample code
> > /
> >
**********************************************************************
> > **/
> > #include <boost/config.hpp>
> > #include <iostream>
> > #include <boost/graph/adjacency_list.hpp>
> > #include <boost/graph/breadth_first_search.hpp>
> > #include <boost/shared_ptr.hpp>
> >
> > using namespace boost;
> >
> > class VertexProperties
> > {
> >  public:
> >     std::string _name;
> >     VertexProperties () {}
> >     VertexProperties (std::string name) : _name(name) {}
> > };
> >
> > //OPTION ONE
> > class bfs_extend_graph1 : public default_bfs_visitor
> > {
> > public:
> >     template<typename Vertex, typename Graph>
> >     void discover_vertex (Vertex v, Graph& g)
> >         {
> >             std::cout<<"\ndiscover";
> >             Vertex v_new;
> >             //the compile gets confused here !!!!!
> >             v_new = add_vertex(VertexProperties("C"),g);
> >             add_edge(v,v_new,g);
> >         }
> > };
> >
> > //OPTION TWO
> > class bfs_extend_graph2 : public default_bfs_visitor
> > {
> > public:
> >     template<typename Vertex, typename Graph>
> >     void discover_vertex (Vertex v, Graph& g)
> >         {
> >             std::cout<<"\ndiscover";
> >             Vertex v_new;
> >             typedef adjacency_list< vecS, vecS, directedS,
> > VertexProperties>
> > graph_t;
> >             //a pointer to
> >             shared_ptr<graph_t> ptr_g;
> >             *ptr_g = g; //reference to the actual graph
> >             v_new = add_vertex(VertexProperties("C"),*ptr_g);
> >             add_edge(v,v_new,*ptr_g);
> >         }
> > };
> >
> >
> > int main()
> > {
> >     typedef adjacency_list< vecS, vecS, directedS,
> > VertexProperties> graph_t;
> >     typedef graph_traits<graph_t>::vertex_descriptor Vertex;
> >     typedef graph_traits<graph_t>::vertex_iterator vertex_iterator;
> >     typedef property_map<graph_t,std::string
> > VertexProperties::*>::type VP_map_t;
> >
> >     graph_t g;
> >     Vertex v1,v2;
> >
> >     v1 = add_vertex(VertexProperties("A"),g);
> >     v2 = add_vertex(VertexProperties("B"),g);
> >     add_edge(v1,v2,g);
> >
> >     //get the VP map
> >     VP_map_t VP_map = get(&VertexProperties::_name,g);
> >
> >     bfs_extend_graph1 bfs_e1;
> >     breadth_first_search(g,v1,visitor(bfs_e1));
> >
> >     bfs_extend_graph2 bfs_e2;
> >     breadth_first_search(g,v1,visitor(bfs_e2));
> >
> >     //check if everything is okay
> >     std::pair<vertex_iterator, vertex_iterator> vp;
> >     std::cout<<std::endl<<"vertices : ";
> >     for ( vp = vertices(g); vp.first != vp.second; ++vp.first)
> >     {
> >         VertexProperties vp1 = get(VP_map,*vp.first);
> >         std::cout<<"\t"<<vp1._name;
> >     }
> >
> >     return 0;
> > }
> >
> > /
> >
**********************************************************************
> > **/