-
Notifications
You must be signed in to change notification settings - Fork 819
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Other Heaps? #645
Comments
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 @jsichi, @jkinable What is your opinion on this? There are two benefits in using jheaps:
|
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 |
Thank you for the quick replies! Makes perfect sense to me! I would really like this to happen before #595 get's merged. What would be required here (I'm not that familiar with maven)? Do we just list is as a dependency? |
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. |
I will either do it for the maximum weight bipartite matching algorithm, or let @Toptachamann do it directly in #595. |
I've added this dependency to the jgrapht-core pom and used Pairing heaps. Should I modify the maximum weight bipartite matching algorithm? |
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. |
@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 |
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. |
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. |
@d-michail you are probably the best person to add the dependency, so please go ahead with that |
@jsichi Do we create a separate ticket for that? If so this can be closed for sure! Thanks for the hard work everyone! |
Opening #666 for the followup. 🤘 😈 |
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?
The text was updated successfully, but these errors were encountered: