[GSoC] Blog post on reachability queries
From: Abhishek Kumar <hidden>
Date: 2020-05-20 16:38:55
Greetings everyone! I am working on implementing Generation Number v2. I have written an article about reachability queries, which I feel is necessary background for understanding the project. Here's the summary of article:
Reachability refers to the ability to get from one vertex to another within a graph. Reachability queries are an interesting problem, improving performance for many graph operations. Better and more sophisticated solutions are being created as the size of working graphs keeps increasing. Reachability for the undirected graph can be found in linear preprocessing and constant query time with disjoint set unions. The answer isn't as evident for a directed graph because of differing performance on positive and negative queries, nature and size of graph and other factors. Topological Levels, Post Order DFS Intervals and Contraction Hierachies are some of the building blocks for such algorithms.
In a later article, I will talk about the specifics of generation number for Git. In particular, how Git uses reachability queries, the need for Generation Number v2 i.e., _Correted Commit Date With Strictly Monotonic Offset_ and other interesting tidbits I come across. You can find the article here: https://abhishekkumar2718.github.io/programming/2020/05/20/reachability-queries.html I appreciate any suggestions or feedback. Thanks Abhishek