Re: [Boost-users] Confused with BGL-- Six Degrees of Kevin Bacon example

Subject: Re: [Boost-users] Confused with BGL-- Six Degrees of Kevin Bacon example
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-05-29 14:17:06

On Wed, 29 May 2013, lizy10b wrote:

>  
> Hi there,
>   I am new to BGL library. 
>   I am walking through the online tutorial and just finished the "10.2. Six Degrees of Kevin Bacon".
>   
>   As it is said at the end of the example: "Note that vertex descriptor objects can not always be used as 
> indices into vectors or arrays such as bacon_number. This is valid with the 
> adjacency_list class with VertexList=vecS, but not with other variations of 
> adjacency_list. A more generic way to index based on vertices is to use the 
> ID property map (vertex_index_t) in coordination with the iterator_property_map.".
>   
>   So I turn to have a look at the iterator_property_map page and its sample. 
> First, this sample uses VertexList=vecS too. 
> Second, I know this sample is using iterator_property_map to build a property map, 
> but I think the property is still indexed by the edge descriptor objects.    
>  So what is the difference?

I'm not sure I fully understand what you are asking, but here is the 
general picture of iterator_property_map, vertex_index[_t], and 
edge_index[_t]:

The fastest-to-access property maps in BGL for data storage are the 
iterator property maps, which use a vector, array, or similar as 
underlying storage and allow it to be indexed by vertex or edge 
descriptors.  The "catch" with that is that vectors and such require 
integers to index into them, and a vertex or edge descriptor may not be an 
integer (or may not map one-to-one onto a contiguous sequence of numbers 
in the correct range).  Although many BGL graph types do have that 
property for vertex descriptors (such as the vecS case you mention), some 
don't (such as grid_graph) and most do not have it for edge descriptors. 
Thus, a separate property map is needed to map from descriptors to indexes 
into the underlying containers.  By default, the vertex_index and 
edge_index property maps of a graph are used for that.  In the vecS case, 
the vertex index map is an identity function, but generic code cannot rely 
on that.  For grid_graph, the mapping can be accessed but is not the 
identity function, and the same is true for edge descriptors in 
compressed_sparse_row_graph.

One problem you may see with this is how you would create an index map 
when it is not built into a graph: after all, iterator_property_map 
requires the index map to already exist.  There are two solutions for 
that, both involving the user creating the index numbers manually.  The 
first is to have a vertex_index_t or edge_index_t internal property as one 
of the user-defined properties added to the graph, and the other is to use 
something like an associative_property_map (assuming there are comparison 
operators on the descriptors in question).  For either type of storage, 
the user would need to loop over the vertices and edges, assign them 
sequential numbers, and put those into the map.

Does that start to answer your question, or did you intend to ask 
something else?

-- Jeremiah Willcock