Is there work on creating a concept for a heap?
Yes -- look at <URL:http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/Buffer.html> for the basic queue concept. If you need updating, there does not appear to be a defined concept for that, but you should use the interface that dijkstra_shortest_paths() uses for its queue.
I was trying to figure out how I could pass in a priority queue to a utility function of my Stoer–Wagner implementation that would also give me access to the "distances" that are associated to values in the priority queue. In short, I don't think that this is currently possible. But, I only need one method: something like `keys() const` on an updatable priority queue could return a readable property map with the key type being the value type of the queue and the value type being a `key_type` that is the distance type. It seems like I got this backward, I know, but in the papers that I have been reading, the `pop` method of a priority queue returns the value with the highest key. In my utility function, I have: const vertex_descriptor u = pq.top(); // u = extractmax(PQ) w = get(distances, u); pq.pop(); What I would like is: const vertex_descriptor u = pq.top(); // u = extractmax(PQ) w = get(pq.keys(), u); pq.pop(); This way, I could pass in the heap without worrying about not having access to the distances map. Attached is a file containing concept definitions for `Buffer` and two, new concepts that I am proposing: `UpdatableQueue` and `KeyedUpdatableQueue`. Currently `boost::d_ary_heap_indirect` satisfies `UpdatableQueue` (I have checked this), and I need it to satisfy `KeyedUpdatableQueue`. The way that it could satisfy `KeyedUpdatableQueue` rather easily is `typedef` `typename boost::property_traits<DistanceMap>::value_type` as `key_type` and a new public member: DistanceMap keys() const { return distance; }