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

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

Hello,

I have a problem with the breadth_first_search. I read the documentation and examples an can't find a solution for my problem. In order breadth_first_search uses a bfs_discovery_visitor vis(&distanceSet[0]);. This distance vector storing all distances. So, now I need more then a vector. I want use a struct for storing the distances and later some other stuff e.g. probability of distances and cumulative probabilitys. I tried several code, but get every time errors from VC++ compiler. Can anybody tell me, how do I handle this vector.

You could use bundles properties in your graph: struct tVertex{ long distance; double probability; } Those can be used in the adjacency list like the follows: typedef adjacency_list < vecS, vecS, undirectedS, tVertex> tGraph; after that you get a property map from the graph: typedef property_map::type tDistanceMap; tDistanceMap distance_map = get(&tVertex::distance, g); if you use a visitor like that: template < typename DistanceMap > struct bfs_distance_visitor:public default_bfs_visitor { bfs_distance_visitor(DistanceMap dmap):m_distance_map(dmap) { } template < typename Edge, typename Graph > void discover_vdiscover_vertex(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; } DistanceMap m_distance_map; }; You can pass it the map and fire the search: bfs_distance_visitor< tDistanceMap >vis(distance_map); breadth_first_search(g, vertex(s, g), visitor(vis));

The second question is, can I abort the further evaluation of distances, if any theshold is reached? The graph has about 57000 vertices an every vertice has about 6 edges. I am interested only for the vertices in a given range (e.g. 100).

What I found from searching the archives is to throw an exception from inside the visitor if a certain distance is reached. HTH, Stephan