Lowest Common Ancestor for DAG

[jyoti246]

Description of the problem

Using a naive approach we can find LCA between two nodes in a non cyclic graph in O(n) time. But when there are O(n) queries i.e we need to get LCA of O(n) different pairs of nodes, the time complexity becomes O(n^2).
But by doing some pre processing we can reduce the complexity to O(nlogn).
There are mainly two approaches:
Binary lifting
using Segment tree and Eulars tour

Both of these can be implemented in pydatastructs/graphs/algorithms.py as classes

[czgdp1807]

Can you please provide some references(research paper, wikipedia, or university lectures) for the algorithm you are suggesting?

[jyoti246]

Here are they
For Binary Lifting:
https://cp-algorithms.com/graph/lca_binary_lifting.html
For Eulars Tour , Range Minimum query
https://www.geeksforgeeks.org/find-lca-in-binary-tree-using-rmq/

[czgdp1807]

Let G be a tree

Quoting from [1]. This says that the graph should be a tree/DAG. The algorithm for binary trees is already available here, please see if any improvements can be made to it.

Is [2] relevant to the algorithm you are taking about?

References

.. [1] https://cp-algorithms.com/graph/lca_binary_lifting.html
.. [2] https://uhra.herts.ac.uk/bitstream/handle/2299/12152/906535.pdf;jsessionid=C46932A27B417CF192F2A9026D68706D?sequence=2

[czgdp1807]

Please follow the plan of action available here.

[robotjellyzone]

Hi @jyoti246 any update? are you still working on this ?

[Aakansha99]

Can I work on this issue?

[czgdp1807]

Read the stuff above and work accordingly.

[Rukmini-Meda]

I would like to work on this issue. Please assign this to me as part of GSSoC'20