Re: [jgrapht-users] Bug report

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

Thanks Santiago, but someone else beat you to it and it was fixed in a 
subsequent release.

You can find more of the blow-by-blow here:

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

The latest code is here:

http://jgrapht.svn.sourceforge.net/viewvc/jgrapht/trunk/src/org/jgrapht/util/FibonacciHeap.java?revision=645&view=markup

Using 32 instead of the Math calls may be good enough, so if anyone 
notices excessive CPU usage from the Math calls showing up in a 
profiler, we could change it.

JVS

Santiago Gutierrez wrote:
> Dear Jgrapht team:
>  
>  
> My name is Santiago Gutierrez, I am from Colombia in South America. 
> While trying to solve a problem at ICPC I was in the need of a fibonnaci 
> heap. Browsing the internet I found the fibonacci heap from your project 
> and tried to use it in my problem. I then found that the fibonacci heap 
> was not as fast as it should be, making my algorithm O(n^2) and not 
> O(nlog(n)). After seeing the code I found that the problem was in this 
> function:
>  
>  
> Consolidates the trees in the heap by joining trees of equal degree 
> until there are no more trees of equal degree in the root list.
> Running time: O(log n) amortized
> 
>   protected void consolidate▾ <http://grepcode.com/file/repo1.maven.org$maven2@org.jgrapht$jgrapht-jdk1.5@0.7.3@org$jgrapht$util$FibonacciHeap.java#>()
> 435    {
> 436        int arraySize = nNodes + 1;
> 437        List <http://grepcode.com/file/repository.grepcode.com$java$root@jdk$openjdk@6-b14@java$util$List.java#List><FibonacciHeapNode <http://grepcode.com/file/repo1.maven.org$maven2@org.jgrapht$jgrapht-jdk1.5@0.7.3@org$jgrapht$util$FibonacciHeapNode.java#FibonacciHeapNode><T>> array =
> 438            new ArrayList <http://grepcode.com/file/repository.grepcode.com$java$root@jdk$openjdk@6-b14@java$util$ArrayList.java#ArrayList><FibonacciHeapNode <http://grepcode.com/file/repo1.maven.org$maven2@org.jgrapht$jgrapht-jdk1.5@0.7.3@org$jgrapht$util$FibonacciHeapNode.java#FibonacciHeapNode><T>>(arraySize);
> 439
> 440        // Initialize degree array
> 441        for (int i = 0; i < arraySize; i++) {
> 442            array.add <http://grepcode.com/file/repository.grepcode.com$java$root@jdk$openjdk@6-b14@java$util$List.java#List.add(org.jgrapht.util.FibonacciHeapNode)>(null);
> 443        }
> 
>  
> 
> I found through wikipedia that the fibonacci heap always mantain a degree of it's trees of 
> maximum log(n), thus the line:
> 
> int arraySize = nNodes + 1
> 
> 
> Can be safely change to:
> 
> int arraySize = 32
> 
> Effectively making the function the log(n) function that it should be. (And indeed my code acc).
> 
> Thanks a lot for all your hard effort,
> 
> Santiago Gutierrez A.
> 
> 
> ------------------------------------------------------------------------
> Connect to the next generation of MSN Messenger  Get it now! 
> <http://imagine-msn.com/messenger/launch80/default.aspx?locale=en-us&source=wlmailtagline>