Feature Request: lowest common ancestor algorithms for trees

[AlexandruValeanu]

I have noticed that Tarjan's algorithm is implemented but that is not very efficient if you run the queries one by one. There are some nice algorithms for solving the lca problem for trees that provide O(log n) or even O(1) per query.

I was thinking about implementing some and I was curious if this is something that would be interesting to have.

[d-michail]

Definitely! We are also missing some cleanup and unification work (interface design, etc) regarding LCA algorithms.

[AlexandruValeanu]

Great! I'll start working on that.

Yes, I've seen that there is no LcaAlgorithm interface but adding one is not hard.
The problem is that all LCA algorithms should be in some package (in my opinion). But this would mean that Naive and Tarjan have to move which is a major problem. Do you have any suggestions on how to structure all LCA-related stuff?

[rahul6789sharma]

HI
Recently i have started using this great library in my project. LCA algorithm is good to have. and even it is better can we have some algorithm to find all the leaf nodes of given vertex.
i am not sure if it is already available

[d-michail]

@AlexandruValeanu We are slowly moving stuff into their respective packages. If you contribute more LCA algorithms, it would definitely make sense to have a separate lca package.

Note that we use a strict 2 releases deprecation policy. We first deprecate a class in one release, and then remove it in the next. If you want to move a class, you deprecate the class and add a new class at the other location. After the next release, we will remove the deprecated class.

[LightnessOfBeing]

Hi @d-michail. I'm interested to resolve that issue. I wanted to ask: what methods except findLca(V a, V b) and findAllLcas(V a, V b) should be presented in the LCA interface?

About additional LCA algorithms: I want to implement Binary Lifting algorithm with O(nlogn) on preprocessing and O(logn) on query. Are you interested in it? Or it would be better to implement Farach-Bender first (because it's faster <O(n), O(1))?

[AlexandruValeanu]

Hi Kirill, I am writing to let you know that I have already started working on that idea and I'll soon be sending a comprehensive proposal to explain my ideas on that topic. Best regards, Alexandru Văleanu On Tuesday, February 13, 2018, 5:55:33 PM GMT, Kirill Vishnyakov <notifications@github.com> wrote: Hi @d-michail. I'm interested to resolve that issue. I wanted to ask: what methods except findLca(V a, V b) and findAllLcas(V a, V b) should be presented in the LCA interface? About additional LCA algorithms: I want to implement Binary Lifting algorithm with O(nlogn) on preprocessing and O(logn) on query. Are you interested in it? Or it would be better to implement Farach-Bender first (because it's faster <O(n), O(1))? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.