COIN-OR::LEMON - Graph Library

Opened 3 years ago

Last modified 14 months ago

#646 new defect

Bug in binomial heap with ties

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


In the current implementation, it may happen that the top-priority item (i.e. _min) is not a root of the heap. This happens because when we merge the minimum-priority item (_min) tree with an other tree whose root has the same priority, we do not make sure that the new root will be _min. This causes a lot of problems, because we may try to pop a non-root item.

The following code snippet demonstrates the issue.

ListDigraph g;
ListDigraph::Node v0 = g.addNode();
ListDigraph::Node v1 = g.addNode();
ListDigraph::NodeMap<int> ref(g,-1);
lemon::BinomialHeap<int,ListDigraph::NodeMap<int> > h(ref);

Before the pops, the heap consists of a single tree with root v1 and its only child is v0. However, the top priority item in the current implementation is v0, which is not a root in the heap! This causes an infinite loop in BinomialHeap::unlace.

One possible fix of this issue is to replace line 177 of binomial_heap.h with


Attachments (1)

binomHeapFix.patch (1.3 KB) - added by Peter Madarasi 14 months ago.

Download all attachments as: .zip

Change History (3)

comment:1 Changed 3 years ago by Alpar Juttner

Thanks for the patch.

It would be nice to add a related test code to

Changed 14 months ago by Peter Madarasi

Attachment: binomHeapFix.patch added

comment:2 in reply to:  1 Changed 14 months ago by Peter Madarasi

Replying to Alpar Juttner:

Thanks for the patch.

It would be nice to add a related test code to

The revised patch adds a new test case to

Note: See TracTickets for help on using tickets.