Supercharging the Git Commit Graph III: Generations and Graph Algorithms

This post introduces the concept of 'generation numbers' for Git commits, defining it as one more than the maximum generation number of its parents. It explains how generation numbers can be computed using DFS and stored in the commit-graph file. The post details three applications of generation numbers: short-circuiting 'Can X Reach Y?' questions (like in `git push`), improving merge-base calculations for `git merge-base` and `git status`, and enabling more efficient topological sorting for `git log --graph` by using two concurrent walks. It also discusses why commit dates are unreliable for ordering and highlights that these advancements are being incorporated into future Git releases and are already used in Visual Studio Team Services (VSTS) for displaying commit history.