Jgrapht: Other Heaps?

[simlu]

In Kolmogorov's Blossom V implementation @Toptachamann found that the PairingHeap and the CostlessMeldPairingHeap which @d-michail implemented in jheaps, perform significantly better than the currently implemented FibonacciHeap (for that specific use case). However they are likely to outperform the FibonacciHeap generally.

Would it be ok to port the implementation @d-michail wrote into this library? What's the general consense here?

[d-michail]

I am not really fond of "porting" which essentially means copy-pasting someone's implementation. In case of a different programming language, it might make sense, assuming of course that all the copyright and author notes are retained and licenses respected.

Since jheaps is written in Java, we can use the heaps using a maven dependency.

@jsichi, @jkinable What is your opinion on this? There are two benefits in using jheaps:

• There is a nice interface for the heap, which means that you can swap them easily. This means that we can also allow the user of an algorithm to swap the implementation.
• It also contains monotone heaps (radix heaps for double keys for example) which should speed up Dijkstra significantly.

[jsichi]

I'm fine with adding the dependency, especially given the authorship :) I think that means we can eliminate our GenericFibonacciHeap, and eventually our FibonacciHeap after performance-testing as suggested by @simlu

[simlu]

Thank you for the quick replies! Makes perfect sense to me!

I would really like this to happen before https://github.com/jgrapht/jgrapht/pull/595 get's merged. What would be required here (I'm not that familiar with maven)? Do we just list is as a dependency?

[jsichi]

Someone would need to submit a PR to add the dependency in jgrapht-core's pom.xml and replace at least one existing use of GenericFibonacciHeap to exercise the dependency. There are also some other doc and packaging files that need to be updated to document the new dependency.

[d-michail]

I will either do it for the maximum weight bipartite matching algorithm, or let @Toptachamann do it directly in #595.

[Toptachamann]

I've added this dependency to the jgrapht-core pom and used Pairing heaps. Should I modify the maximum weight bipartite matching algorithm?

[jsichi]

It would be best to do it in its own PR so we can merge that by itself, and then @Toptachamann can rebase against that.

[simlu]

@jsichi is that really necessary? The change seems very minor and is tested in the blossom pr already. Considering its the reason we're adding the dependency.

It really depends on how much work it is to replace fib with pair. If it's a lot of work then I'm against a new pr. Otherwise sure

[jsichi]

It's cleaner to keep addition of dependencies from getting entangled with giant PR's, in case one or the other needs to be reverted later for any reason.

[Toptachamann]

Don't see any problem with rebasing after PR for dependency addition is merged, especially because in min-cost flow algorithm I use a Fibonacci heap for Dijkstra algorithm and I'd like to replace it with Pairing heap.

[jsichi]

@d-michail you are probably the best person to add the dependency, so please go ahead with that

[jsichi]

@simlu we can close this one now right? (#652 has been merged.) Some followup work is needed for remaining uses of FibonacciHeap (I think we can delete GenericFbionacciHeap already since all uses of that are gone now).

[simlu]

@jsichi Do we create a separate ticket for that? If so this can be closed for sure!

Thanks for the hard work everyone!

[jsichi]

Opening #666 for the followup. :metal: :smiling_imp: