Re: [Boost-users] [graph] breadth_first_search with a structure

From: Stephan Diederich (stephan.diederich_at_[hidden])
Date: 2006-09-20 08:08:41

Hi Daniel,

2006/9/20, boost_at_[hidden] <boost_at_[hidden]>:
> Hello Stephan,
>
> with your example I get the same errors like before.
> H:\daten\Programme\boost/pending/property.hpp(40) : error C2039: 'kind'
> : is not a member of '`global namespace''
>       H:\daten\Programme\boost/graph/properties.hpp(198) : see
> reference to class template instantiation 'boost::property_kind<long
> dreiDmatrix::Vertex::*>' being compiled
>       H:\daten\Programme\Matrizen\dreiDmatrix.h(78) : see reference to
> class template instantiation 'boost::property_map<class
> boost::adjacency_list<struct boost::vecS,struct boost::vecS,struct
> boost::undirectedS,struct dreiDmatrix::Vertex,struct
> boost::no_property,struct boost::no_property,struct boost::listS>,long
> dreiDmatrix::Vertex::*>' being compiled
>
> The compiler is Visual C++ 6.0 and the version number ob boost is
> (probably) 1.33.1.

IIRC, bundled properties won't work with VC6.0 because of the missing
abilitity of partial template specializations. Sorry.
I think you have to stick on your old version without bundles. If you
nevertheless want to keep your data together, have a look at the
Internal Properties for the adjacency list:
http://tinyurl.com/r7gv6
You may want to specify your own tags and attach those to your
vertices. AFAIK, this should work with VC6.0.

Does anyone else want to comment on this?

Cheers,
Stephan

> > #include <boost/graph/adjacency_list.hpp>
> > #include <boost/graph/breadth_first_search.hpp>
> > #include <boost/pending/integer_range.hpp>
> > #include <iostream>
> >
> > using namespace boost;
> >
> > //tag for throwing inside bfs_distance_visitor
> > struct max_distance_reached{};
> > template < typename DistanceMap >
> > class bfs_distance_visitor:public default_bfs_visitor {
> >   typedef typename property_traits < DistanceMap >::value_type T;
> >
> > public:
> >   bfs_distance_visitor(DistanceMap dmap, T
> > max_distance):m_distance_map(dmap),m_max_distance(max_distance){ }
> >   template < typename Edge, typename Graph >
> >       void tree_edge(Edge e, const Graph & g) const
> >   {
> >     typename graph_traits < Graph >::vertex_descriptor
> >     s = source(e, g), t = target(e, g);
> >     m_distance_map[t] = m_distance_map[s] + 1;
> >     if (m_distance_map[t] >= m_max_distance)
> >       throw max_distance_reached();
> >   }
> >   DistanceMap m_distance_map;
> >   T m_max_distance;
> > };
> >
> > //own vertex, bundles properties style
> > struct Vertex{
> >   long distance;
> >   double probability;
> > };
> >
> > int
> > main()
> > {
> >   // Select the graph type we wish to use
> >   typedef adjacency_list < vecS, vecS, undirectedS, Vertex> graph_t;
> >   // Set up the vertex IDs and names
> >   enum { r, s, t, u, v, w, x, y, N };
> >   // Specify the edges in the graph
> >   typedef std::pair < int, int >E;
> >   E edge_array[] = { E(r, s), E(r, v), E(s, w), E(w, r), E(w, t),
> >     E(w, x), E(x, t), E(t, u), E(x, y), E(u, y)
> >   };
> >
> >   // Create the graph object
> >   const int n_edges = sizeof(edge_array) / sizeof(E);
> >   typedef graph_traits<graph_t>::vertices_size_type v_size_t;
> >   graph_t g(edge_array, edge_array + n_edges, v_size_t(N));
> >
> >   // Typedefs
> >   typedef graph_traits < graph_t >::vertex_descriptor
> vertex_descriptor ;
> >   typedef graph_traits < graph_t >::vertices_size_type
> vertices_size_type;
> >
> >   // get the distance property map from the graph
> >   typedef property_map<graph_t, long Vertex::*>::type tDistanceMap;
> >   tDistanceMap distance_map = get(&Vertex::distance, g);
> >
> >   //create a bfs visitor which calculates all distances smaller than 3
> >   bfs_distance_visitor<tDistanceMap> vis(distance_map, 3);
> >   try{
> >     breadth_first_search(g, vertex(s, g), visitor(vis));
> >   } catch(max_distance_reached& ){}
> >   return EXIT_SUCCESS;
> > }