COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes between Version 2 and Version 9 of Ticket #381


Ignore:
Timestamp:
05/30/13 23:21:18 (11 years ago)
Author:
Peter Kovacs
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #381

    • Property Milestone changed from LEMON 1.3 release to LEMON 1.4 release

  • Ticket #381 – Description

    v2 v9  
    11The 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.
    2 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.
     2However, simplified heaps could be implemented with a limited functionality (`push()`, `pop()`, `top()`, `prio()`, `size()`, `empty()`, `clear()`, etc.) without this cross reference map. For such heaps, the basic `push()` and `pop()` operations could be implemented more efficiently, but the duplications of items could not be avoided.
    33
    44A 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.
    55
    6 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.
     6It 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 require different implementation of the algorithms.