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

5 Sep 2005

      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;
}
/ 
********************************************************************** 
**/
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

Jeremy Siek