pydatastructs
pydatastructs copied to clipboard
codezonediitj
Lowest Common Ancestor for DAG
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
Can you please provide some references(research paper, wikipedia, or university lectures) for the algorithm you are suggesting?
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/
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
I would like to work on this issue. Please assign this to me as part of GSSoC'20
Hi, @Rukmini-Meda yes, go ahead but please remember to follow the plan of actions and please first discuss regarding your solution and approach.
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 !
Yes, I am working on it. Need little time. Will make a PR soon by tomorrow.
Is it assigned? I have implemented binary-lifting in C++ for SPOJ problems. Can try it in python as well if not assigned.
Please read https://github.com/codezonediitj/pydatastructs/wiki/Issue-Policy and then you may proceed.
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.
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.
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]