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>
|
