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

From: Stephan Diederich (stephan.diederich_at_[hidden])
Date: 2006-09-12 06:42:01

Hi Daniel,

2006/9/11, boost_at_[hidden] <boost_at_[hidden]>:
> 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<unsigned int * >
> 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<struct *>.

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<graph_t, long tVertex::*>::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