Question: Given the MySQL primary key of a particular element in a paginated result set, is there a function to get the page number that element is in?

If not, what is some pseudocode that can help me get there? Note that primary keys can be deleted and there will be 'gaps' in the sequence so simple arithmetic alone might not work...

Answer: 
I finally switched to [Lemon graph library](http://lemon.cs.elte.hu/trac/lemon) which is not as hacky as BGL
I do not see reasons why map cannot be used as data structure to store outgoing edges. Map has iterators that work in the similar way to say `std::vector`, etc. To handle incoming edges you will need 2 maps on each vertex. AFAIK BGL supports both lists on vertexes.

I would recommend you to modify (hack) BGL and see what will happen. The change might be not small. You will have to provide adjacency\_list specializations for your new type of container. Most likely this will work.