Boost logo

Boost :

Subject: Re: [boost] [BGL] Stoer–Wagner min-cut algorithm
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-07-06 18:49:35


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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk