[Olsr-dev] Improving SPF with binary heaps

[Saulo Queiroz]

Hi Henning,
I've supervised the work of Diogo.
Regarding you first question, response is no. Not all procedures are used.
Diogo just listed in .h all classical procedures of a binary heap but only
the ones required by Dijkstra are implemented. The other are there just
as a reminder, but he can clean .h,  No problem.

Regarding the second question:  heap_extract_min is the procedure you asked
about.
Note however that the idea is to replace AVL only for Dijkstra and keeping
AVL there
for other stuff.
ok?

best regard



On 10 July 2015 at 08:17, Henning Rogge <(spam-protected)> wrote:

> 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
>
> --
> Olsr-dev mailing list
> (spam-protected)
> https://lists.olsr.org/mailman/listinfo/olsr-dev
>



-- 
Saulo Jorge bq
-
"In theory, there is no difference between practice and theory, in practice
there is"
-- Someone
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20150710/29d78f4e/attachment.html>