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.