As my master thesis on the MFF UK I chose this implementation/experimental topic. My task was to implement two different approaches to build and maintain Top trees and then I have to compare them on difficult hard problems like 2-edge connectivity.
Top Trees are not so well known data structure which could be used to maintain information of some dynamically updated collection of trees. User of this data structure defines four basic operations, which are used internally when Top Trees structure is changing. When there occurs some cutting or joining on underlying trees the structure updates internally stored information using these user functions.
This data structure could be used for example to dynamically maintain diameter, center or median (minimizing weighted distance from all other vertices) of given tree in time O(log N) (where N denotes the number of vertices).
For more information (and pictures) see my Master thesis (included below).
I implemented two different drivers for the Top trees structure:
Both implementations were written in C++14. Then I implemented solution for 2-edge connectivity using Top trees drivers and finally I compared both drivers on the same inputs.
Detailed analyze and graphs are included in the thesis linked below. In short: both drivers are pretty fast, but the second one is slower in general situations. For the 2-edge connectivity problem, where the second driver could could turn-off expensive updates during some operations, the second one driver is much faster than the first one (is is better in general situation).