Re: [Boost-Users] Re: breadth_first_searchable graph, without invalidable vertex descriptors

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-11-21 08:59:36

On Wed, 21 Nov 2001 cristipp_at_[hidden] wrote:
cristi> Thanks. I added the vertex_color property to my graph and it works
cristi> just fine.

Great!

cristi> As a BGL (and not BCG :-)) novice I would like to
cristi> understand why the breadth_first_search compiles for
cristi> boost::adjacency_list with VertexType vecS, but not for
cristi> boost::adjacency_list with VertexType listS (unless the
cristi> colormap is passed as a parameter). Is there any piece of
cristi> documentation I should have read and I did not? Or could
cristi> anybody explain this for us, the big herd of users?

Sure.

Take a look at the docs in breadth_first_search.html, specifically the
color_map named parameter. As with most named parameters, you can
either pass in an argument, or use the default. The default in
this case is:
  "Default: an  iterator_property_map created from a std::vector of
  default_color_type of size num_vertices(g) and using the i_map for the
  index map."

where i_map is the vertex index map given as another named paremeter:

 "IN: vertex_index_map(VertexIndexMap i_map)
   This maps each vertex to an integer in the range [0, num_vertices(g)).
   This parameter is only necessary when the default color property map is
   used. The type VertexIndexMap must be a model of Readable Property Map.
   The value type of the map must be an integer type. The vertex
   descriptor type of the graph needs to be usable as the key type of the map.
   Default: get(vertex_index, g)"

Now, an adjacency_list only has a builtin vertex index map if it
has VertexList=vecS:

>From adjacency_list.html:
  "If the VertexList of the graph is vecS, then the graph has a builtin
  vertex indices accessed via the property map for the vertex_index_t
  property."

Alternatively, you could add a vertex index map to an adjacency_list with
VertexList=listS using a property<vertex_index_t, std::size_t> but you
would need to remember to initialize the indices yourself and make sure
that the vertices are numbered in the range [0,num_vertices(g))  (which is
a needed by the BFS algorithm and others).

cristi> Keep up the good work!
cristi> Cristi

Thanks!
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------