Because I don't have enough to do... I decided to start trying to implement the graph500 benchmark in the boost graph library and then the parallel boost graph library. I've got a very simply implementation working using an adjacency_list and a BFS visitor but I'm sure I can do much better. On my box: seq-csr at scale 20 is ~3.5e+07 TEPS adjacency-list at scale 20 is ~5.0e+07 TEPS (TEPS: traversed edges per second) I'll work on this one a bit more and then try a compressed sparse row graph.