Re: [boost] [BGL] Stoer–Wagner min-cut algorithm

Subject: Re: [boost] [BGL] Stoer–Wagner min-cut algorithm
From: Daniel Trebbien (dtrebbien_at_[hidden])
Date: 2010-07-05 19:27:33

>> 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; }