Addition of Fibonaci Heap for usage in Bidirectional_Dijkstra

[a396f486-5fc5-40c2-a542-2e12efb37784]

Like Binomial Heap, Fibonacci Heap is a collection of trees with min-heap or max-heap property:- https://en.wikipedia.org/wiki/Fibonacci_heap. In Fibonacci Heap, trees can have any shape even all trees can be single nodes (This is unlike Binomial Heap where every tree has to be Binomial Tree). Currently, the Fibonacci heap isn't implemented in stl of c++, but Boost has an implementation of https://www.boost.org/doc/libs/1_50_0/doc/html/boost/heap/fibonacci_heap.html

As sage has an interface with Boost, we can have this heap instead of current python heap implemented in Bidirectional_dijkstra. Using Fibonacci Heap we can reduce time complexity of Decrease-Key, which has importance in Dijkstra and Prim algorithms. With Binary Heap, time complexity of these algorithms is O(VLogV + ELogV). If Fibonacci Heap is used, the time complexity is improved to O(VLogV + E).

CC: @dcoudert

Component: graph theory

Issue created by migration from https://trac.sagemath.org/ticket/27620

[dcoudert]

comment:1

Please check #27464. We are now using

from libcpp.queue cimport priority_queue
from libcpp.pair cimport pair

[a396f486-5fc5-40c2-a542-2e12efb37784]

comment:2

Priority queue in c++ implements Binomial heap which gives complexity of:

Algorithm      Average  Worst case
Space       O(n)            O(n)
Search      O(n)            O(n)
Insert      O(1)            O(log n)
Delete      O(log n)        O(log n)
Peek        O(1)            O(1)  

whereas Fibonacci Heap reduces complexity Insertion and Decrease key

Algorithm      Average  
Insert      Θ(1)    
Find-min    Θ(1)     
Delete-min  O(log n)     
Decrease-key    Θ(1)     
Merge       Θ(1)

[a396f486-5fc5-40c2-a542-2e12efb37784]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-Like Binomial Heap, Fibonacci Heap is a collection of trees with min-heap or max-heap property. In Fibonacci Heap, trees can have any shape even all trees can be single nodes (This is unlike Binomial Heap where every tree has to be Binomial Tree). Currently, the Fibonacci heap isn't implemented in stl of c++, but Boost has an implementation of [https://www.boost.org/doc/libs/1_50_0/doc/html/boost/heap/fibonacci_heap.html](https://www.boost.org/doc/libs/1_50_0/doc/html/boost/heap/fibonacci_heap.html) 
+Like Binomial Heap, Fibonacci Heap is a collection of trees with min-heap or max-heap property:- https://en.wikipedia.org/wiki/Fibonacci_heap. In Fibonacci Heap, trees can have any shape even all trees can be single nodes (This is unlike Binomial Heap where every tree has to be Binomial Tree). Currently, the Fibonacci heap isn't implemented in stl of c++, but Boost has an implementation of [https://www.boost.org/doc/libs/1_50_0/doc/html/boost/heap/fibonacci_heap.html](https://www.boost.org/doc/libs/1_50_0/doc/html/boost/heap/fibonacci_heap.html) 

 As sage has an interface with Boost, we can have this heap instead of current python heap implemented in Bidirectional_dijkstra.
 Using Fibonacci Heap we can reduce time complexity of Decrease-Key, which has importance in Dijkstra and Prim algorithms. With Binary Heap, time complexity of these algorithms is O(VLogV + ELogV). If Fibonacci Heap is used, the time complexity is improved to O(VLogV + E).  

[dcoudert]

comment:5

You can give it a try.

[embray]

comment:6

As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).