Who do we have to bug to get improvements in the documentation and examples? :)
Apparently, me :)
Out of curiosity (keeping in mind I'm still wrapping my head around graph theory), algorithmically speaking; why would I need to provide an index map if iterating over vertices and in/out edges with iterators is good enough? Is it a question of base algorithm or of implementation optimizations (switching out iterators and distances with container-specific pointer or index arithmetic as an oversimplified example)?
It's all about labeling and efficiency. Most graph algorithms (e.g., from the Cormen book) associate various data with vertices and edges - like edge weight or flow/capacity, vertex color, etc. If your vertex or edge type does not explicitly declare member variables that can be used to satisfy these requirements, then you have to create an "exterior" label or property. The most efficient way to access this information is using a vector, and the only way to get data out of a vector is to use an index. And to get the index, you need a vertex index map.
Long story short, most algorithms in the BGL create exterior labels as vectors, hence requiring index maps. An alternative, and infrequently explored option is to create the exterior labels as unordered_maps, mapping descriptors to their label values.
Both 2007 and 2008 SoC projects address this issue in basically the same way.
Maintaining the indices can save you a significant amount of time if you have to keep creating new maps (and aren't removing vertices).
How so? Could you provide a brief example?
Iteration is just traversal. Labels (properties) require a form of associativity (edge descriptor to weight, for example).
Awesome! I'll definitely be checking that out, is the plan for it to eventually replace the current BGL implementation?
Hard to say. There aren't very many 20K+ LOC libraries submitted to Boost (I'm just projecting the size based on the current version). I would hope that my work does replace the BGL, but that's something to be addressed in the future. I'm also trying to target C++0x as the implementation language, including concepts so it won't even be generally compilable for quite some time (accounting for compiler bugs too).
This version is easily a couple years away from practical use.
Also, I recently came across the PBGL project; I haven't tested it, but is it not ready for use in a commercial application yet? My code will definitely need to be parallelized.
That's something you'd have to ask of the authors. I want to say "more or less", but I couldn't certainly be wrong.
I was also trying to build my version in a way that would make it easy to port PBGL to the new interfaces, but I have no idea if that will work or not. I'm thinking that better parallelization and distriibution support will appear in various Boost libraries in the near future, and that support will creep into the graph library.