Jgrapht: deprecate FibonacciHeap

[jsichi]

We've already replaced all references to GenericFibonacciHeap with jheaps, and deprecated that.

It would be nice to do the same for our non-generic FibonacciHeap class as well, especially since a monotone heap implementation would be better optimized for usages such as Djikstra/ClosestFirstIterator.

However, as part of doing this, we should perf-test cases where we are currently relying on the intrusiveness optimization (and native double) to make sure there is no performance regression.

[Toptachamann]

I’d like to do the performance comparison

[Toptachamann]

I've done the performance comparison, here are the results
Fibonacci heap native

|Test type | Dijkstra, us/op | Closest first iterator, us/op |
|---------------------|-------------------|-------------------------------|
| complete 100 | 165 | 165 |
| complete 300 | 1903 | 1920 |
| complete 500 | 9799 | 9526 |
| complete 1000 | 54701 | 54474 |
| triang. 1000 | 507 | 510 |
| triang. 3000 | 1702 | 1695 |
| triang. 5000 | 3399 | 3329 |
| triang. 10000 | 7420 | 7386 |
| triang. 20000 | 17138 | 16867 |
| triang. 40000 | 38579 | 38707 |

JHeaps Fibonacci heap

|Test type | Dijkstra, us/op | Closest first iterator, us/op |
|---------------------|-------------------|-------------------------------|
| complete 100 | 172 | 173 |
| complete 300 | 2013 | 1984 |
| complete 500 | 11371 | 10108 |
| complete 1000 | 56411 | 56650 |
| triang. 1000 | 455 | 464 |
| triang. 3000 | 1534 | 1595 |
| triang. 5000 | 2927 | 3100 |
| triang. 10000 | 6985 | 6892 |
| triang. 20000 | 15904 | 16159 |
| triang. 40000 | 35970 | 36313 |

JHeaps Pairing heap

|Test type | Dijkstra, us/op | Closest first iterator, us/op |
|---------------------|---------------------|-------------------------------|
| complete 100 | 166 | 165 |
| complete 300 | 2017 | 2163 |
| complete 500 | 12015 | 11453 |
| complete 1000 | 61985 | 63824 |
| triang. 1000 | 373 | 375 |
| triang. 3000 | 1224 | 1227 |
| triang. 5000 | 2637 | 2895 |
| triang. 10000 | 5840 | 5941 |
| triang. 20000 | 15251 | 15217 |
| triang. 40000 | 30799 | 33975 |

The performance difference is not that big.

I currently can't run the tests with double monotone radix heap. The reason is that it throws an exception. This happens when we firstly insert start vertex with distance 0 (currentMin = 0), then remove it (now currentMin in the heap is null), then insert a node with some distance k (currentMin becomes k) and then insert a node with distance m < k (exception is thrown because of k < m). In the Wikipedia it is stated than "A necessary and sufficient condition on a monotone priority queue is that one never attempts to add an element with lower priority than the most recently extracted one". I think the value currentMin shouldn't become null after we remove vertex with distance 0 but in the code, it is commented as a special case, so I'm not sure whether this is right.

[d-michail]

The radix heap is implemented slightly different such that you cannot insert an element with lower key than the current minimum.

If you rewrite Dijkstra a bit, it should work. I think you need to first call findMin(), then relax edges and finally delMin().

Moreover, before running Dijkstra you should iterate over all edges and compute the bound n C where C is the largest edge weight and n is the number of nodes. This bound should then be used when initializing the radix heap.

[d-michail]

@Toptachamann I will try and change the radix heap to distribute the elements based on the last deleted key and not the current minimum. That way it will work out of the box.

[d-michail]

@Toptachamann I changed the implementation and it should work now out of the box. I did not release, so you will have to test against version 0.9-SNAPSHOT after installing locally using maven install.

[Toptachamann]

@d-michail Now it doesn't work as well. After the start vertex is deleted, its bucket index becomes -1, but it stays the currentMin. After we relax all outgoing edges and try to delete another minimum element, the java.lang.ArrayIndexOutOfBoundsException: -1 is thrown.

[d-michail]

@Toptachamann Sorry, there was a small bug. Thanks for testing. I also did some tests and now the current minimum updates correctly.

[Toptachamann]

Here are the results for the double monotone heap:

|Test type | Dijkstra | Closest first iterator |
|--------------------------------|----------------|------------------------|
| complete 100 up. b. 10 | 172 | 172 |
| complete 300 up. b. 10 | 2458 | 2408 |
| complete 500 up. b. 10 | 11104 | 10052 |
| complete 1000 up. b. 10 | 57028 | 56944 |
| complete 100 up. b. 100 | 185 | 175 |
| complete 300 up. b. 100 | 2381 | 2464 |
| complete 500 up. b. 100 | 11320 | 11313 |
| complete 1000 up. b. 100 | 64749 | 61865 |
| complete 100 up. b. 1000 | 190 | 180 |
| complete 300 up. b. 1000 | 2315 | 2303 |
| complete 500 up. b. 1000 | 11034 | 11792 |
| complete 1000 up. b. 1000 | 65407 | 68292 |
| complete 100 up. b. 10000 | 186 | 193 |
| complete 300 up. b. 10000 | 2390 | 2359 |
| complete 500 up. b. 10000 | 12667 | 14156 |
| complete 1000 up. b. 10000 | 72096 | 71001 |
| triang. 1000 | 418 | 418 |
| triang. 3000 | 1347 | 1349 |
| triang. 5000 | 2426 | 2486 |
| triang. 10000 | 6798 | 6559 |
| triang. 20000 | 16375 | 16257 |
| triang. 40000 | 36574 | 36203 |

I've used different edge weight upper bounds to see how they change the running time. Also, there is some speedup, the best result for complete graphs is the same as the result with the Fibonacci heap. Currently, Pairing heaps outperform other heaps on sparse graphs.

[jsichi]

@Toptachamann do you have a branch published I can take a look at?

[Toptachamann]

@jsichi I pushed the benchmark branch to my fork. There I only benchmarked the Dijkstra's algorithm. Should I do the deprecation?

[jsichi]

Yes, I think we should go ahead with the deprecation. How will we choose the optimal heap implementation (or allow the user to select it, as we do in MaximumWeightBipartiteMatching)?

[Toptachamann]

I would say, that it's better to have a default heap for Dijkstra's algorithm and let the user supply another heap if needed. This approach is more flexible in two ways: 1. it gives the user an ability to do own benchmarks and select a heap based on the results. 2. If the heaps in jheaps are reimplemented or changed somehow, it's more convenient to change the default heap implementation in Dijkstra's algorithm with this approach.

P.s. Pairing heaps seem to be a reasonable default value since most of the time the upper bound on the edge weights won't be low and monotone heaps won't have their advantage. But I'll make a note in the comments that it's good to consider using monotone heaps for Dijkstra's algorithm in the case the range of the weights isn't big.