[GSoC] Blog post on reachability queries

From: Abhishek Kumar <abhishekkumar8222@gmail.com>
To: git@vger.kernel.org
Cc: stolee@gmail.com, jnareb@gmail.com
Subject: [GSoC] Blog post on reachability queries
Date: Wed, 20 May 2020 22:07:22 +0530	[thread overview]
Message-ID: <20200520163653.GA76552@Abhishek-Arch> (raw)

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