COIN-OR::LEMON - Graph Library

Opened 8 years ago

Last modified 7 weeks ago

#381 new enhancement

Simplified heaps without priority update — at Version 2

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

Description (last modified by Peter Kovacs)

The existing heap implementations in LEMON cointain an Item->int map to indicate the current location of each item. It is required to implement increase(), decrease(), erase(), etc. functions. However, simplified heaps could be implemented with a limited functionality (push(), pop(), top(), prio(), size(), empty(), clear(), etc.) without this corss reference map. For such heaps, the basic push() and pop() operations could implemented more efficiently, but the duplications of items could not be avoided.

A Dijkstra or Prim algorithm could be implemented with such heaps, but it would require slight modifications. A node should be pushed each time its distance label is updated (i.e. more than once in some cases), and the duplicate nodes should be skipped after each pop() operation.

It would be nice to introduce such implementations in LEMON. I think, they would lead to better performance in many practical cases, because not too many duplications would be expected on typical graphs. However, there are some problems with this proposal. First, such heaps would not conform to the current heap concept. Second, using them would reqiure different implementation of the algorithms.

Change History (2)

comment:1 Changed 8 years ago by Peter Kovacs

We could introduce a SimplifiedHeap concept. The main question is whether we could generalize the Dijkstra and Prim implementations to accept both types of heaps or not. I would really dislike duplicate algorithm classes.

comment:2 Changed 8 years ago by Peter Kovacs

Description: modified (diff)
Note: See TracTickets for help on using tickets.