[GSoC] Blog post on reachability queries

From: Abhishek Kumar <abhishekkumar8222@gmail.com>
Date: May 20, 2020, 16:37 UTC
Message-ID: <20200520163653.GA76552@Abhishek-Arch>

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:

Show 14 quoted lines

> 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