On Mon, 5 Jul 2010, Daniel Trebbien wrote:
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.
Why do you need to get the "distances" (values) from the heap itself rather than from a separate distance map? The heap itself does not store distances, after all; it needs a separate data structure (or function) to get the distance to any given vertex. In fact, the fact that there is a distance map at all is a convenience/performance optimization in d_ary_heap; the Boost mutable_queue doesn't use a property map for distances at all (other than through indirect_cmp). What are you using the keys() map for? Maybe there is another way to do the same thing. -- Jeremiah Willcock