Region graph

[xiuliren]

• reimplement the greedy mean affinity agglomeration with more efficient data structures
• the code is well organized with better readability.

[william-silversmith]

When I was working with dijkstra's algorithm, I made a similar experiment. I found that unless you are using the decrease_key/increase_key property of the fibbonacci heap, it's faster to use std::priority_queue and just keep adding new nodes and skip reoccurring labels. If you use the decrease_key property, Tarjan and Sleator also found the Pairing Heap to be faster in practice than the fib heap though the fib heap has a better theoretically proven bound (the pairing heap is harder to write proofs for).

Boost has a pairing heap implementation (and so do I): https://github.com/seung-lab/dijkstra3d/blob/master/pairing_heap.hpp It also has the virtue of being slightly more memory efficient.

[xiuliren]

@william-silversmith Your experiment and conclusion is super helpful. Your implementation of pair heap is also cool!