Link/Cut-Trees implementation

[yi-ji]

This PR implements Link/Cut-Trees data structure for Boost Graph Library. Since disjoint_sets algorithms has been moved into boost/graph (#169), this should also be the right place to put link_cut_trees algorithm.

This implementation of link_cut_trees supports following operations:

• make_tree(x): create a new link/cut-tree containing only root x
• link(x, y): make the tree rooted at x a subtree of y;
• cut(x): remove the edge connecting x to its parent;
• find_root(x): find the root of the tree containing x;
• lowest_common_ancestor(x, y): find the lowest common ancestor of such x and y that have same root.

All operations above are of amortized time complexity O(log n), except O(1) for make_tree.

This implementation refers to: Robert Endre Tarjan, Data Structures and Network Algorithms, Chapter 5

[jeremy-murphy]

I'm not sure that Boost.Graph really is the right place for disjoint_sets, but it definitely is the right place for link_cut_tree! I just have one question: how is the documentation going? :)

[yi-ji]

@jeremy-murphy comments resolved, checks passed :)

[yi-ji]

Hi @jeremy-murphy Thanks for reviewing! This PR has been ready for quite a while. Any concerns before merging it? Would appreciate someone with write access to have a look :) @jzmaddock

[jeremy-murphy]

Hey, sorry, I don't have much time for open-source projects now that I have a baby! I'll try to review again quickly.

[yi-ji]

@jeremy-murphy Thanks for helping review again :smile: I've replied or made changes accordingly. Enjoy parenting! :baby_bottle:

[yi-ji]

Hi @jeremy-murphy good sir, all comments resolved & checks passed, ready again :)

Hope this is not disturbing you @jzmaddock Would you mind having a look to help merge it? :))

[jeremy-murphy]

I can't merge it, sorry, I don't have that access. @jzmaddock is the only person I'm aware of with that access and is active at the moment.

[yi-ji]

This has been lying in backlog for quite a while. @jzmaddock would you mind having a look? :)

[xiuliren]

thanks for adding this! It seems that this data structure could not be serialized using Boost: Serialization?

[yi-ji]

@jingpengw I guess it depends on the template parameters? All I know is that boost serialization supports POD and STL containers, I think you can use them to instantiate link-cut trees.

[yi-ji]

@jzmaddock Could you please take a look at this MR when you've got time? It's ready for merge :) Thank you.

[xiuliren]

@jzmaddock did you get a chance to take a look? is it good to merge?

[jeremy-murphy]

I need to get the CI fixed and I'm going to prioritize merging some bug fixes, but then one day I'll get back to you! ;)

[xiuliren]

any chance to merge this?

[jeremy-murphy]

any chance to merge this?

Yes, there is a chance. :) I'll try to look over it again soon, but I can't guarantee anything.

[jeremy-murphy]

any chance to merge this?

Yes, there is a chance. :) I'll try to look over it again soon, but I can't guarantee anything.

Btw, what I meant is, I definitely want to merge it, it's just a matter of chance that I find time to do it. :)