c++ - DFS in boost::graph with changing the graphs content -

minimal example:

#include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/depth_first_search.hpp>  struct vertex {     int number; }; struct edge {};  typedef boost::adjacency_list<boost::lists, boost::vecs, boost::directeds, vertex, edge> graph_t; typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_t; typedef boost::graph_traits<graph_t>::edge_descriptor edge_t;  struct vertex_visitor : public boost::default_dfs_visitor {     void discover_vertex(vertex_t v, graph_t& g)     {         g[v].number = 42;     } };  int main() {     graph_t g;     vertex_t v1 = boost::add_vertex(g);     vertex_t v2 = boost::add_vertex(g);     boost::add_edge(v1, v2, g);      vertex_visitor vis;     boost::depth_first_search(g, boost::visitor(vis));      return 0; } 

it not work because graph needs referenced const in vertex_visitor::discover_vertex().

is there better method want writing own dfs algorithm (or using const_cast)? also, solution allow add/delete edges , vertices while discovering vertex?

have @ how boost implements connected_components. in order store component id following visitor used:

// visitor used both in connected_components algorithm // , in kosaraju strong components algorithm during // second dfs traversal. template <class componentsmap> class components_recorder : public dfs_visitor<> {   typedef typename property_traits<componentsmap>::value_type comp_type; public:   components_recorder(componentsmap c,                        comp_type& c_count)     : m_component(c), m_count(c_count) {}    template <class vertex, class graph>   void start_vertex(vertex, graph&) {     if (m_count == (std::numeric_limits<comp_type>::max)())       m_count = 0; // start counting components @ 0     else       ++m_count;   }   template <class vertex, class graph>   void discover_vertex(vertex u, graph&) {     put(m_component, u, m_count);   } protected:   componentsmap m_component;   comp_type& m_count; }; 

the idea property map passed constructor of visitor, , later used update data. relating example, vertex_visitor rewritten in following way:

template <class propertymap> struct vertex_visitor : public boost::dfs_visitor<> {   propertymap m_pmap;   vertex_visitor(propertymap pmap) : m_pmap(pmap) {}   template <class vertex, class graph>   void discover_vertex(vertex v, const graph& g)   {     boost::put(m_pmap, v, 42);   } }; 

instantiation of visitor bit convoluted because need specify property map type explicitly:

typedef boost::property_map<graph_t, int vertex::*>::type numbersproperty; vertex_visitor<numbersproperty> vis(boost::get(&vertex::number, g)); 

as per last part of question, mutation of graph structure (i.e. addition or deletion of vertices , edges) invalidates interators, break dfs algorithm. think precisely reason why graph passed const-reference.