Re: [jgrapht-users] jgrapht fibonacci

[John V. S. <js...@gm...>]

Johan Henriksson wrote:
> Hello,

Hi Johan, thanks for writing.

> I am converting a C++ levelsets code and I am getting wrong results. the 
> question is then where the bug is; my conversion, the C++ code or the 
> fibonacci heap from jgrapht. I have rather high confidence in my 
> conversion, hence I wonder how well tested you consider the fibonacci 
> code? is it actively in use? (then I would consider it well tested). I 
> rely heavily on changing keys, hence fibonacci.

The fib code originally came from Nathan Fiedler.  It has been modified 
a few times since then based on other work (such as the addition of 
generics to JGraphT) and performance suggestions.

Nathan's code has undergone changes since then as well:

http://cafenate.blogspot.com/2008/05/analysis-of-java-implementations-of.html

I haven't followed up on everything in that post, but I'm not aware of 
any correctness issues.  The implementation is used by JGraphT's 
DijkstraShortestPath/ClosestFirstIterator, so it gets used heavily by a 
number of applications.  But you never know...there could certainly be a 
bug.  If you can isolate a unit test demonstrating incorrect behavior, 
that would be very valuable.

> also, why does the fibonacci node take a key, while insert() also takes 
> a key, and the node key cannot be changed? the design is very confusing. 
> I would expect a single location where the key can be set, either 
> insert() or new FibNode, not both.

Good question :)  I'll clean it up.

JVS