User Friendly Graphs and Their Measures

I am using this place to publish thoughts and updates about the design and implementation of this project. If you happen to be reading this and have some comments about the content, ideas, or questions, please leave them here - I'd like to read them.

New Graph Classes

This is a discussion of the [un]directed_graph classes.

New Algorithms

This is a discussion of the several new algorithms (mostly just property computations) of graphs.

Documentation, Etc.

This is a discussion of other (mostly documentary) aspects of the Boost Graph Library.

Notes

This is basically something to take the place of a developer's Journal.

Vertex and Edge Indices

Since switching the default storage selectors from vecS to listS, I've noticed exactly how few examples there are that actually use this. What's actually troubling about this is the fact that vecS secretly provides a vertex_index property which, as far as I can tell is used by nearly every algorithm in the library. Not surprisingly, listS does not. This can cause a number of misconceptions, namely this ​using vertex_descriptor as a 0-based index post on the Boost wiki.

(Jeremy: yes, this is a serious problem that should be addressed in the new graph classes.)

Anyhow, the problem is not that using listS as a storage selector really breaks a lot of code (it can), but that its hard to figure out how to create vertex and edge index maps for them. The Dijkstra example has a listS example, but it uses property maps instead of bundled properties. Apparently, the solution is to manually initialize the index map. This is both good and bad. First, it's bad because new user's won't really understand why they have to write the same chunk of code over and over. Maybe it would be nice to provide a default index_vertices() function and an index_edges() functions that do that work for us. On the other hand, It's good because it highlights the instability of indices over descriptors.

(Jeremy: I'd suggest going even further, and have the graph class automatically create and maintain indices for the vertices and edges.)

I think the real I'm having with this is that so much of the documentation and so many of the examples operate on the notion that a vertex_descriptor is its own index - which it is most definitely not.

(Jeremy: yes, that is correct.)