COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 9 years ago

#301 closed task (done)

Port fourary, d-ary, pairing and binomial heaps

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

Dorian Batha implemented fourary, d-ary, pairing and binomial heaps in LEMON (for his BSc thesis). These structures should also be ported.

Attachments (6)

301-d1a9224f1e30-bdc7dfc8c054-bb3392fe91f2.bundle (14.9 KB) - added by Peter Kovacs 9 years ago.
Port + improvements
301-karyheap-param-7124b2581f72.patch (2.9 KB) - added by Peter Kovacs 9 years ago.
301-impl-impr-39a5b48bcace.patch (3.7 KB) - added by Peter Kovacs 9 years ago.
301-kary-bubbledown-9314d9339475.patch (3.8 KB) - added by Peter Kovacs 9 years ago.
301-binomial-faster-3887d6f994d7.patch (9.9 KB) - added by Peter Kovacs 9 years ago.
301-rename-65a0521e744e.patch (11.5 KB) - added by Peter Kovacs 9 years ago.

Download all attachments as: .zip

Change History (24)

Changed 9 years ago by Peter Kovacs

Port + improvements

comment:1 Changed 9 years ago by Peter Kovacs

Status: newassigned

The attached bundle file contains the port of these tools with improvements and unification for the doc and the member names. They seem to be clear enough to add to the main repository.

Changed 9 years ago by Peter Kovacs

Changed 9 years ago by Peter Kovacs

comment:2 Changed 9 years ago by Peter Kovacs

I attached two more changesets on the top of the bundle file: [7124b2581f72] and [39a5b48bcace].

comment:3 Changed 9 years ago by Peter Kovacs

Some questions about the name of the heaps:

  • The name KaryHeap seems to be strange for me. What about the followings: DaryHeap, KHeap, DHeap? Would any of them be better? Maybe "d-ary" is used more than "k-ary", but e.g. in LEDA it is called k_heap.
  • FouraryHeap: is this name suitable? Should we keep this structure at all?
  • Maybe BinomHeap is to close to BinHeap. What about BinomialHeap? (I think, short names should be used for the best known and/or most widely used ones, e.g. BinHeap, FibHeap)

Changed 9 years ago by Peter Kovacs

comment:4 Changed 9 years ago by Peter Kovacs

[9314d9339475] improves the bubbleDown() function of FouraryHeap and KaryHeap. It performs less comparison (like the current implementation of the binary heap). It proved to be slightly faster on average, but in case of FouraryHeap and -O3 optimization it could be 10-25 percent faster.

comment:5 Changed 9 years ago by Peter Kovacs

According to benchmark tests, the implementation of PairingHeap and RadixHeap could/should be improved (e.g. FibHeap usually outperforms PairingHeap), however they are rahter good.

On the other hand, BinomHeap is extremly slow when it is used as a Dijkstra heap, though it is good in heap sort. Thus I suppose that something is wrong in its implementation, probably in decrease(). Maybe this structure could be omitted until this problem is investigated.

Changed 9 years ago by Peter Kovacs

comment:6 in reply to:  5 Changed 9 years ago by Peter Kovacs

Replying to kpeter:

On the other hand, BinomHeap is extremly slow when it is used as a Dijkstra heap, though it is good in heap sort. Thus I suppose that something is wrong in its implementation, probably in decrease(). Maybe this structure could be omitted until this problem is investigated.

[3887d6f994d7] fixes this problem. It provides a much faster implementation for decrease() and also improves the performance of push() and pop(). With these improvements this class could also be merged into the main branch. It is still not so fast, but it is comparable with the other heaps.

comment:7 in reply to:  3 Changed 9 years ago by Peter Kovacs

All the changesets related to this ticket went to the main branch. Alpar, thank you.

However note that the doc of these heaps was written supposing that the changesets in #299 will also be applied (e.g. creating an own group for heaps).

The only questions left here are about the names of the heaps:

Some questions about the name of the heaps:

  • The name KaryHeap seems to be strange for me. What about the followings: DaryHeap, KHeap, DHeap? Would any of them be better? Maybe "d-ary" is used more than "k-ary", but e.g. in LEDA it is called k_heap.
  • FouraryHeap: is this name suitable? Should we keep this structure at all?
  • Maybe BinomHeap is to close to BinHeap. What about BinomialHeap? (I think, short names should be used for the best known and/or most widely used ones, e.g. BinHeap, FibHeap)

comment:8 Changed 9 years ago by Peter Kovacs

KHeap or DHeap -- which one should we use instead of KaryHeap?

FouraryHeap -- alternatives could be: QuaternaryHeap, QuadHeap, QuatHeap, QuaHeap, QHeap, FourHeap, FHeap. Should we keep it at all?

What do you think?

Changed 9 years ago by Peter Kovacs

comment:9 Changed 9 years ago by Peter Kovacs

[65a0521e744e] renames three of the new heaps:

  • KaryHeap --> DHeap
  • FouraryHeap --> QuadHeap
  • BinomHeap --> BinomialHeap

What do you think? Are these names acceptable?

comment:10 Changed 9 years ago by Balazs Dezso

In my opinion, the binomial heap doesn't have to be merged to the trunk, because I think it does not provide any advantages comparing to the other implementations. In addition, the main advantage of the binomial heaps, i.e. they can be merged in logarithmic time, is not implemented, and the interface cannot be extended to provide this feature.

comment:11 in reply to:  10 ; Changed 9 years ago by Alpar Juttner

Replying to deba:

In my opinion, the binomial heap doesn't have to be merged to the trunk, because I think it does not provide any advantages comparing to the other implementations. In addition, the main advantage of the binomial heaps, i.e. they can be merged in logarithmic time, is not implemented, and the interface cannot be extended to provide this feature.

Could you please remind me of the use of logarithmic time merge?

comment:12 in reply to:  11 ; Changed 9 years ago by Peter Kovacs

Replying to alpar:

Could you please remind me of the use of logarithmic time merge?

See http://en.wikipedia.org/wiki/Binomial_heap#Merge.

comment:13 in reply to:  12 ; Changed 9 years ago by Alpar Juttner

Replying to kpeter:

Replying to alpar:

Could you please remind me of the use of logarithmic time merge?

See http://en.wikipedia.org/wiki/Binomial_heap#Merge.

It's only me who can't see anything about the _use_ of logarithmic time merge at this link?

comment:14 in reply to:  13 Changed 9 years ago by Peter Kovacs

Replying to alpar:

It's only me who can't see anything about the _use_ of logarithmic time merge at this link?

I'm sorry. I misread your sentence, I did not catch the word "use". Btw. I know nothing about the usage.

comment:15 Changed 9 years ago by Peter Kovacs

Two questions left here:

  1. Names of the heaps. What do yout think about these renamings?
    • KaryHeap --> DHeap
    • FouraryHeap --> QuadHeap
    • BinomHeap --> BinomialHeap

  1. Do we need BinomialHeap at all (supposing that we don't and won't have merge operation for that)? Should we keep it despite this lack of functionality or should we remove it? (It could be kept in e.g. a contribution project.)

comment:16 in reply to:  15 ; Changed 9 years ago by Alpar Juttner

Replying to kpeter:

Two questions left here:

  1. Names of the heaps. What do yout think about these renamings?
    • KaryHeap --> DHeap
    • FouraryHeap --> QuadHeap
    • BinomHeap --> BinomialHeap

I agree with them all.

  1. Do we need BinomialHeap at all (supposing that we don't and won't have merge operation for that)?

Could anyone elaborate why is this merge operation important?

Should we keep it despite this lack of functionality or should we remove it?

I see no problem with keeping it in the core, if the code is otherwise up to the usual standards.

comment:17 in reply to:  16 ; Changed 9 years ago by Peter Kovacs

Replying to alpar:

  1. Names of the heaps. What do yout think about these renamings?
    • KaryHeap --> DHeap
    • FouraryHeap --> QuadHeap
    • BinomHeap --> BinomialHeap

I agree with them all.

Okay. Then what about applying [65a0521e744] and close this ticket?

  1. Do we need BinomialHeap at all (supposing that we don't and won't have merge operation for that)?

Could anyone elaborate why is this merge operation important?

Maybe Balazs could answer this question. He was the supervisor of Dorian Batha, who developed this stucture and Balazs doubted whether we should keep this heap.

Should we keep it despite this lack of functionality or should we remove it?

I see no problem with keeping it in the core, if the code is otherwise up to the usual standards.

Both its interface and its implementation is clear, and its performance is relatively good (sine [3887d6f994d7]).

comment:18 in reply to:  17 Changed 9 years ago by Alpar Juttner

Resolution: done
Status: assignedclosed

Replying to kpeter:

Okay. Then what about applying [65a0521e744] and close this ticket?

Done.

Note: See TracTickets for help on using tickets.