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

Hi Daniel, 2006/9/20, boost@daniel-gohlke.de :

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' being compiled H:\daten\Programme\Matrizen\dreiDmatrix.h(78) : see reference to class template instantiation 'boost::property_map,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 #include #include #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::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::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; }