Git’s database internals II: commit history queries (GitHub blog)

The commit-graph file provides a location for adding new information to our commits that do not exist in the commit object format by default. The new information that we store is called a generation number. There are multiple ways to compute a generation number, but the most important property we need to guarantee is the following:

If the generation number of a commit A is less than the generation number of a commit B, then A cannot reach B.

$ man -k 'topological sort'
tsort (1)            - perform topological sort

$ dpkg --search /usr/bin/tsort
coreutils: /usr/bin/tsort

$ man tsort | egrep -A1 DESCRIPTION | tail -1
       Write totally ordered list consistent with the partial ordering in FILE.