[Olsr-dev] Improving SPF with binary heaps

[Henning Rogge]

On Thu, Jul 9, 2015 at 9:32 PM, Diogo Gonçalves
<(spam-protected)> wrote:
> Hi all,
>
> I've studied performance of olsrd's SPF under different priority queues.
> We find it quite surprising that in olsrd Dijkstra is based on AVL instead
> of binary heaps. Different from binary heaps, AVL is not originally
> intendend
> as a priority queue. To achieve O(log n) performance, AVL requires nodes
> with
> unique key values, which is not reasonable for a priority queues since
> different
> nodes can have the same priority. In fact, in the olsrd's SPF, nodes with
> same
> priority are put into a list. Then decrase-key procedure can be O(n) in some
> cases
> and Dijkstra becomes O(n*n) instead of O(n*logn). Binary heap is the most
> popular
> priority queue for Dijkstra, achieving O(n*logn) regardless nodes have the
> same priority.
> I put in my github an initial version of binary heaps (BH) for olsrd [1].
> With traces from a 200-node mesh [2], Dijkstra-BH behaved very similar to
> Dijkstra-AVL.
> However, from 800 nodes, Dijkstra-BH drammatically outperformed
> Dijkstra-AVL.
> Comments, improvements and bugfixes are welcome,

Hi,

I had a short look at "heap.h"... are all of these functions called
from the user of the heap, even things like "swap_left" and
"swap_right" ?

I am also quite unsure what I use "heap_decrease_key" and "heap_increase_key".

How do I remove things from a heap (I don't see a remove function) ?

Henning