Re: [boost] [review] Heaps: mutability

Subject: Re: [boost] [review] Heaps: mutability
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-03 12:33:20

> I'm trying to figure out how I can use a mutable queue to write
> something like Dijkstra's SP. Here's a skeleton with the relevant
> parts.
> 
> Queue<Vertex*, Comp> q;
> Map<Vertex*, Queue::handle_type> h;
> h[start] = q.push(start);
> 
>   v->distance += x;
>   q.update(h[v]);
> 
> Comp is an indirect comparison of vertex distances (u->distance <
> v->distance).
> 
> Does the mutable heap support this application (i.e., where I'm not
> directly updating the value type)? It's not clear from the examples
> supplied with the program. I suspect that it is, but it's not clear.

b.h supports two ways of updating nodes:

1: update(handle_type, value_type);
2: update(handle_type);

the second version assumes that you change the priority manually, while the 
`update' call just fixes the heap.

this is described in the `mutability' section, but i should probably improve the 
documentation. please note, that you *have* to call update before modifying any 
other node ...

cheers, tim