[Olsr-dev] Improving SPF with binary heaps

[Saulo Queiroz]

On 11 July 2015 at 03:34, Henning Rogge <(spam-protected)> wrote:

> On Sat, Jul 11, 2015 at 12:43 AM, Saulo Queiroz <(spam-protected)>
> wrote:
> > 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.
>
> I would suggest moving everything that is "internal" to a static
> function... this makes it easier for new users of the API to
> understand what they need because they only have to look at the header
> file.
>
> OK.

> > 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?
>
> I would like to have this as a generic API, so I am looking which
> basic functions we have, we still need or we cannot get.
>
> Basics for both lists and AVL trees in OONF (which is the base of OLSRv2)
> is
> - init
> - insert
> - remove
> - get(key)
> - get_first
> - get_last
>
> and a good way to iterate over the elements of the tree/list (which
> would enable me to write iterator macros like the ones in
>
> http://olsr.org/git/?p=oonf.git;a=blob;f=src-api/common/list.h;h=a6146dcc9eb4d70ef1c2ae32b382df0460d948b0;hb=master#l315
> ).
>
> Can we have the same functions for a binary heap?

It is possible but i think few procedures don't sound reasonable because
binary heaps
are Priority Queues (PQs) by nature being different from the typical data
structures.
In general, one employs priority queues when all items are expected to
leave the structure until the end of the execution of a procedure (what is
very usual in the so-called "greedy algorithms" like Dijkstra). In "normal"
data structures, there is no problem if an item stay in the structure
"forever". In PQs the earlier an item leaves the structure, the better (to
it) because this means it will be served first (in case of Dijkstra this
means the shortest path computation ends for the extracted item).
In this context, functions like get(key) doesn't sound important because
focus goes to the priority assigned to the items not to the key values.
Perhaps we should start discussing an API for PQs since other can be
implemented like Fibonacci, Binomial, etc.

If yes, it makes sense to disallow AVL trees with overlapping keys
> (which is a parameter in avl_init at the moment) and tell the
> developers "use a binary heap instead for this case".
>
Wherever AVL has been used as a priority queue (as I just explained) it can
be replaced by binary heaps. Other scenarios need to be analyzed.

> The heap (because its different than AVL) might of course have a few
> more functions, like the "modify key later" functions you have. Its
> just about the same "basic set".
>
> Henning
>



-- 
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/20150711/71348f58/attachment.html>