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

[robotjellyzone]

Hi, @Rukmini-Meda yes, go ahead but please remember to follow the plan of actions and please first discuss regarding your solution and approach.

[Rukmini-Meda]

Can you please assign this issue to me to avoid any confusion?

[robotjellyzone]

No we can't as there is no such rule of assigning here ! You can just straight away work on it without being assigned and if in case others also provide solution for this issue then the most appropriate and suitable solution will be merged !

[Rukmini-Meda]

Okay.

[robotjellyzone]

Any update @Rukmini-Meda? Are you still working on it!

[Rukmini-Meda]

Yes, I am working on it. Need little time. Will make a PR soon by tomorrow.

[robotjellyzone]

Hi @Rukmini-Meda are you still on it ?

[Rukmini-Meda]

I am sorry that I am not.

[Mintuagarwal]

Is it assigned? I have implemented binary-lifting in C++ for SPOJ problems. Can try it in python as well if not assigned.

[prshnt19]

Please read https://github.com/codezonediitj/pydatastructs/wiki/Issue-Policy and then you may proceed.

[subhangi2731]

can you please assign this issue to me @prshnt19

[Smit-create]

IMHO, since LCA requires sparse table/segment tree for finding the minimum in a segment(Sparse table is prefered due to O(1) time for range min.queries), we should firstly focus on sparse table and segment tree additions and after that it only remains an implementation of LCA.

[czgdp1807]

we should firstly focus on sparse table and segment tree additions and after that it only remains an implementation of LCA.

Sparse table can be added after discussion. I don't know if an issue is already open for it.

Segment Tree is already there as far as I remember.

[Smit-create]

Sparse table can be added after discussion.

https://github.com/codezonediitj/pydatastructs/issues/25 : Issue for Sparse Table. We should try adding this initially

Segment Tree is already there as far as I remember.

Yes, But can we make it customized for such operations: https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-7, which uses custom (merge function taken from user in form of lambda function) and builds on the given array of size n?. Specifically I am talking about something :

>>> merge = lambda x, y: math.gcd(x, y)
>>> segTree = ODST(array, merge, dummy_variable) # array, custom merge function, dummy_variable (used while merging unwanted segment with required segment)
>>> segTree.build()
>>> segTree.query(1, 5) # Return gcd of elements array[1:6]