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

From: Abebaw Wubshet (a.wubshet_at_[hidden])
Date: 2005-09-04 07:43:46

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;
}

/************************************************************************/