[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
Keyboard shortcuts
hback out one level
jnext message in thread
kprevious message in thread
ldrill in
Escclose help / fold thread tree
?toggle this help