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