[boost] Priority Queues

From: Jens Maurer (jmaurer_at_[hidden])
Date: 1999-07-26 15:35:02

Dear boost,

I tried to implement Dijkstra's single-source shortest path
algorithm for graphs using some of Dietmar Kuehl's priority
queues.

I tested my implementation on a real network with about 1000
nodes and 2000 edges.  While fibonacci_heap<> and splay_heap<>
seem to work, d_heap crashes.  I will investigate further.

While implementing Dijkstra's algorithm in a generic form,
I encountered a few problems with the common interface of
the priority queues:

 - push() returns a "pointer" which can be used in the
change() and remove() methods to refer to existing heap
elements.  Unfortunately, there is no method to read a heap
element referred to by a "pointer".  For example, in my
implementation of Dijkstra's algorithm, path weight sums
are stored in the priority queue. Before updating a weight
sum, I must verify that the new weight sum is indeed smaller
than the one previously in the priority queue.

I therefore propose adding a method
        const T & access(pointer) const;
to all heap implementations.

 - In the literature, priority queues are often described as
returning the smallest element in the top() operation.
Dijkstra's algorithm makes natural use of that.  However,
Dietmar Kuehl's implementations return the largest element.
By reversing the comparison function, this can easily be
catered for, but the increase() and decrease() operations
of the priority queue are counter-intuitive that way.

 - My implementation of Dijkstra's algorithm requires that
"pointer" heap references be stored for later referral.
Since the "pointer" type is documented as an opaque object
type, it is difficult to hand "pointer"s to clients for
storage.

Jens Maurer