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

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