首先，我们得到一个提交列表（如git rev-list），以及每个提交的父提交。
对于每次提交，则：

• 如果提交没有为它保留的列，则将它分配给一个空闲列。这就是分支头的启动方式。
• 根据列预定列表打印树图形，然后提交消息
• 用当前提交的第一个父项更新当前列/提交的保留列表条目，以便在同一列中打印父项。
• 其他家长可以得到一个新的免费专栏。
• 如果这是一个合并，下一行将尝试将第二个父对象链接到一个需要提交的列（这会导致循环和“≡桥”）

示例显示了aufs 2-util上git-forest得输出，其中包含一个额外得提交以具有多个分支）.

使用“前瞻”，可以预测合并点将向下移动多远，并挤压两列之间的木材，以给予更美观的结果。

我试着浏览了一下Git或hg的代码，但是很难理解，也很难大致了解到底发生了什么。
对于hg，您是否尝试在hg本身或graphlog中遵循代码？
因为graphlog的代码很短。你可以在hgext/graphlog.py中找到它，真正重要的部分是前200行，剩下的是扩展的引导和找到所选的修订图。代码生成函数是ascii，其最后一个参数是对asciiedge调用的结果（调用本身在generate的最后一行执行，该函数由graphlog提供给generate）

与一般的图形显示相比，这个问题并不困难，因为你想保持节点的提交顺序，所以问题变得简单得多。
另请注意，显示模型是基于网格的，行是提交，列是过去/未来的边缘。
虽然我没有读过git的源代码，但你可能只是遍历提交列表，从最新的开始，并维护一个开放边列表到过去。沿着边自然会导致拆分/合并列，最后你会得到git/hg树的显示。
当合并边时，您希望避免与其他边交叉，因此您必须尝试提前对列进行排序。这实际上是唯一可能不简单的部分。例如，可以执行两遍算法，在第一遍中为边建立列顺序，在第二遍中进行绘制。

注：Git 2.18（Q2 2018）现在会预先计算并将遍历祖先所需的信息存储在一个单独的文件中，以优化图遍历。

commits graph的概念确实改变了'git log --graph'的工作方式。

作为mentioned here：

git config --global core.commitGraph true
git config --global gc.writeCommitGraph true
cd /path/to/repo
git commit-graph write

请参见Derrick Stolee ( derrickstolee )的commit 7547b95、commit 3d5df01、commit 049d51a、commit 177722b、commit 4f2542b、commit 1b70dfd、commit 2a2e32b（2018年4月10日）和commit f237c8b、commit 08fd81c、commit 4ce58ee、commit ae30d7b、commit b84f767、commit cfe8321、commit f2af9f5（2018年4月2日）。
（由Junio C Hamano -- gitster --合并于commit b10edb2，2018年5月8日）
您现在可以使用命令git commit-graph：编写并验证Git提交图文件。
根据在包文件中找到的提交编写提交图文件。
包括现有提交图形文件中的所有提交。
design document声明：
Git遍历提交图有很多原因，包括：
1.列出和筛选提交历史记录。
1.正在计算合并基底。
随着提交计数的增加，这些操作可能会变慢。合并基础计算会显示在许多面向用户的命令中，如'merge-base'或'status'，并且可能需要几分钟的时间来计算，具体取决于历史记录形状。
这里有两个主要成本：
1.解压缩和解析提交。
1.遍历整个图以满足拓扑顺序约束。

提交图形文件是一种补充数据结构，可加快提交图形遍历。如果用户降级或禁用'core.commitGraph'配置设置，则现有ODB就足够了。

档案会以“commit-graph”储存在.git/objects/info目录或替代档案的info目录中。

提交图文件存储提交图结构沿着一些额外的元数据，以加快图遍历。

通过按字典顺序列出提交OID，我们可以为每个提交标识一个整数位置，并使用这些整数位置引用提交的父提交。
我们使用二分查找来查找初始提交，然后在遍历过程中使用整数位置进行快速查找。
您可以看到测试用例：

git log --oneline $BRANCH
git log --topo-order $BRANCH
git log --graph $COMPARE..$BRANCH
git branch -vv
git merge-base -a $BRANCH $COMPARE

这将改进git log performance。
在Git 2.39（Q4 2022）中，添加了“commit-graph file”和“reachability bitmap”的词汇表条目。
请参见Philip Oakley ( PhilipOakley )的commit 8fea12a、commit 4973726、commit fa8e8d5、commit 776ba91（2022年10月29日）。
（2022年11月8日由Taylor Blau -- ttaylorr --合并至commit 4b6302c）
第1011章：添加可达性位图描述
签署人：菲利普·奥克利
签署人：泰勒·布劳
描述可达性位图的用途。
glossary-content现在在其手册页中包括：

可达性位图

可达性位图将所选提交集的可达性信息存储在包文件或多包索引（MIDX）中，以加快对象搜索速度。位图存储在“.bitmap“文件中。
一个存储库最多只能使用一个位图文件。
位图文件可能属于一个包，也可能属于存储库的多包索引（如果存在）。
还有：
第1011章：添加“提交图”描述
签署人：菲利普·奥克利
签署人：泰勒·布劳
Git有一个额外的“提交图”功能，它补充了普通提交对象的有向无环图（DAG）。
补充提交图文件是为提高访问速度而设计的。
从标准DAG视图和提交图文件的Angular 描述提交图。
此外，通过链接到ref术语表条目，与此提交图条目匹配，澄清分支ref和分支tip之间的链接。
commit-graph文件还通过其连字符进行区分。
后续提交会捕获commit-graph缺少连字符的少数情况。
glossary-content现在在其手册页中包括：

提交图概念、表示和用法

由对象数据库中的提交形成的DAG结构的同义词，由分支提示引用，使用它们的链接提交链。此结构是最终提交图。该图可以用其他方式表示，例如“commit-graph”文件。

提交图形文件

“commit-graph”（通常用连字符连接）文件是提交图的补充表示，用于加速提交图遍历。
“commit-graph”文件存储在.git/objects/info目录或备用对象数据库的info目录中。
Git 2.19（Q3 2018）将处理锁文件：
请参阅commit 33286dc（2018年5月10日）、第一次31年1月、第一次32年1月、第一次33年1月、第一次34年1月、第一次35年1月、第一次36年1月、第一次37年1月、第一次38年1月、第一次39年1月（2018年5月1日）和第一次40年1月、第一次41年1月（2018年4月25日）。
帮助者：Jeff King ( peff )。
（2018年6月25日，由Junio C Hamano -- gitster --在commit a856e7d中合并）

commit-graph：修复存在.lock文件时UX问题

我们使用锁文件API来避免多个Git进程写入.git/objects/info目录中的commit-graph文件。

在某些情况下，此目录可能不存在，因此我们检查它是否存在。
现有代码在获取锁时执行以下操作：
1.尝试获取锁。
1.如果失败，请尝试创建.git/object/info目录。
1.尝试获取锁，如有必要则失败。
问题是，如果锁定文件存在，则mkdir会失败，并给出一个对用户没有帮助的错误：

"fatal: cannot mkdir .git/objects/info: File exists"

虽然从技术上讲，这是对锁定文件的尊重，但对用户没有帮助。
请改为执行以下操作：
1.检查是否存在.git/objects/info;请根据需要创建。
1.尝试获取锁，如有必要则失败。
新输出如下所示：

fatal: Unable to create
'<dir>/.git/objects/info/commit-graph.lock': File exists.

Another git process seems to be running in this repository, e.g.
an editor opened by 'git commit'. 
Please make sure all processes are terminated then try again. 
If it still fails, a git process may have crashed in this repository earlier:
remove the file manually to continue.

注：当涉及到从未知类型提升到提交的内核对象时（例如，通过引用它的标签访问的提交），提交图工具不起作用，这一点已在Git 2.21（2019年2月）中得到纠正
参见SZEDER Gábor ( szeder )的commit 4468d44（2019年1月27日）。
（由Junio C Hamano -- gitster --合并于commit 2ed3de4，2019年2月5日）
该算法在Git 2.23（Q3 2019）中进行了重构。
请参见Derrick Stolee ( derrickstolee )的commit 238def5、commit f998d54、commit 014e344、commit b2c8306、commit 4c9efe8、commit ef5b83f、commit c9905be、commit 10bd0be、commit 5af8039、commit e103f72（2019年6月12日）和commit c794405（2019年5月9日）。
（由Junio C Hamano -- gitster --合并至commit e116894，2019年7月9日）
Commit 10bd0be解释范围的变更。
在Git 2.24（Q3 2109）中，在给定的提交对象名上写commit-graph的代码变得更健壮了。
参见SZEDER Gábor ( szeder )的commit 7c5c9b9、commit 39d8831、commit 9916073（2019年8月5日）。
（由Junio C Hamano -- gitster --合并至commit 6ba06b5，2019年8月22日）
而且，在Git 2.24（Q4 2019）中，解析和使用commit-graph文件的代码对损坏的输入更加健壮。
参见Taylor Blau ( ttaylorr )的commit 806278d、commit 16749b8、commit 23424ea（2019年9月5日）。
（由Junio C Hamano -- gitster --合并至commit 80693e3，2019年10月7日）

t/t5318：引入失败“git commit-graph write”测试

当在损坏的仓库中调用'git commit-graph'时，如果祖先提交以某种方式损坏，可能会导致segfault。
这是由于“commit-graph.c”代码中的两个函数调用可能返回NULL，但在取消引用之前没有检查是否为NULL。
因此：

commit-graph.c：处理提交解析错误

为了写入提交图块，'write_graph_chunk_data()'获取要写入的提交列表，并在写入必要的数据之前解析每个提交，然后继续列表中的下一个提交。
由于这些提交中的大多数都没有提前解析（列表中的 last 提交是个例外，它在'copy_oids_to_commits'中提前解析），因此对它们调用'parse_commit_no_graph()'可能会返回一个错误。
如果在取消引用后面的调用之前未能捕捉到这些错误，可能会导致未定义的内存访问和SIGSEGV。²一个这样的例子是'get_commit_tree_oid()'，它期望一个解析的对象作为它的输入（在这种情况下，commit-graph代码传递'*list'）。
如果“*list”导致分析错误，则后续调用将失败。
通过检查'parse_commit_no_graph（）'的返回值来避免将未解析的对象传递给期望解析对象的函数，从而防止出现segfault，从而防止出现此类问题。
在Git 2.26（Q1 2020）中，计算commit-graph的代码被教导使用一种更健壮的方式来判断两个对象目录是否引用同一个对象。
请参见Taylor Blau ( ttaylorr )的commit a7df60c、commit ad2dd5b、commit 13c2499（2020年2月3日）、commit 0bd52e2（2020年2月4日）和commit 1793280（2020年1月30日）。
（2020年2月14日，由Junio C Hamano -- gitster --在commit 53c3be2中合并）
第1001章：在“struct write_commit_graph_context”中存储odb
签署人：泰勒·布劳
在commit-graph.h中有很多地方，函数要么拥有（或几乎拥有）一个完整的struct object_directory * , accesses-〉path '，然后丢弃结构体的其余部分。
这在跨替换比较对象目录的位置时（例如，在决定是否可以合并两个提交图层的情况下）会引起麻烦。
这些路径使用normalize_path_copy()标准化，这缓解了一些比较问题，但不是所有的1。
将struct object_directory*储存在write_commit_graph_context结构中，以odb->path取代char *object_dir的用法。
这是摆脱“commit-graph.c”中所有路径规范化的中间步骤。
解析用户提供的'--object-dir'参数现在需要我们将其与已知的替代项进行比较以确定是否相等。

在此修补程序之前，未知的'--object-dir'参数将以零状态自动退出。

这显然会导致意外的行为，例如验证不在仓库自己的对象存储（或其替代对象之一）中的提交图，或者导致打字错误掩盖合法的提交图验证失败。
当给定的“--object-dir”与任何已知的备用对象存储区都不匹配时，通过“die()”-ing使此错误成为非静默错误。
Git 2.28（2020年第三季度）优化了commit-graph write --stdin-commits。
请参见Taylor Blau ( ttaylorr )的commit 2f00c35、commit 1f1304d、commit 0ec2d0f、commit 5b6653e、commit 630cd51、commit d335ce8（2020年5月13日）、commit fa8953c（2020年5月18日）和commit 1fe1084（2020年5月5日）。
（由Junio C Hamano -- gitster --合并于commit dc57a9b，2020年6月9日）

commit-graph：删除COMMIT_GRAPH_WRITE_CHECK_OIDS标志

帮助人：Jeff King
签署人：泰勒·布劳
由于7c5c9b9c57（“commit-graph：在'write --stdin-commits'中出现无效提交OID错误"，2019-08-05，Git v2.24.0-rc 0--merge列在batch #1中），提交图内置在接收非提交OID作为'--stdin-commits'的输入时死亡。

如果调用者不想自己剔除未提交，这种行为可能会很麻烦，比如说，在将'git for-each-ref'连接到'git commit-graph write --stdin-commits'的情况下。在这种情况下，如果'git commit-graph write'写入包含与提交有关的输入的图，并默默忽略其余的输入，这将是理想的。
已经提出了一些选项来实现“--[no-]check-oids”，这将允许调用者让commit-graph内置来实现这一点。
经过一番讨论，很难想象调用者会不想传递'--no-check-oids'，这表明我们应该完全摆脱抱怨未提交输入的行为。
如果调用方确实希望保留此行为，他们可以通过执行以下操作轻松地解决此更改：

git for-each-ref --format='%(objectname) %(objecttype) %(*objecttype)' |
awk '
  !/commit/ { print "not-a-commit:"$1 }
   /commit/ { print $1 }
' |
git commit-graph write --stdin-commits

要使引用不存在对象的有效OID在放松错误处理后确实是一个错误，请执行额外的查找，以确保在将对象发送到提交图内部之前该对象确实存在。
这是用Git 2.28（2020年第三季度）测试的。
参见commit 94fbd91（2020年6月1日）和commit 6334c5f（2020年6月3日），作者为Taylor Blau ( ttaylorr )。
（由Junio C Hamano -- gitster --合并至commit abacefe，2020年6月18日）
第1111章：测试'--stdin-commits'是否遵守'--[no-]progress'
签署人：泰勒·布劳
确认人：Derrick Stolee
以下代码行在最近的Git代码行覆盖率测试中未被覆盖：

builtin/commit-graph.c
5b6653e5 244) progress = start_delayed_progress(
5b6653e5 268) stop_progress(&progress);

当'--stdin-commits'和'--progress'都通过时，就会执行这些陈述式。请引入三个测试，执行这些选项的各种组合，以确保涵盖这些行。
更重要的是，这是在练习“--stdin-commits”的一个（在某种程度上）以前被忽略的特性，即它尊重“--progress”。
在此之前的版本（“5b6653e523”）：取消引用内置标签”，2020-05-13，Git v2.28.0 --merge列在batch #2中），取消引用'--stdin-commits'的输入是在commit-graph.c中完成的。
既然可以从commit-graph.c的外部生成一个额外的进度表，那么就添加一个相应的测试来确保它也遵守“--[no]-progress”。
生成进度表输出的另一个位置（从d335ce8f24（“[ commit-graph.c ](https显示查找可到达提交的进度”，2020-05-13，Git v2.28.0 --batch #2中列出的merge））已经被任何通过'--reachable'的测试所覆盖。
在Git 2.29（2020年第4季度）中，in_merge_bases_many（）是一种查看提交是否可从一组提交中的任何一个提交到达的方法，在使用提交图功能时被完全破坏，这一点已经得到纠正。
参见Derrick Stolee ( derrickstolee )的commit 8791bf1（2020年10月2日）。
（由Junio C Hamano -- gitster --合并至commit c01b041，2020年10月5日）
我的天啊！修复in_merge_bases_many错误
报告人：斯里尼迪·考希克
协助人：约翰内斯·辛德林
签署人：井架吊杆
在过去的一段时间里，我一直在想：使用in_merge_bases()的世代号“，2018-05-01，Git v2.19.0-rc 0--merge列在batch #1中），使用启发式来简化in_merge_bases()遍历。
只要调用者只检查两个提交，这种方法就能正常工作，但是当有多个提交时，这种启发式方法就有可能 * 非常错误 *。
一些代码在commit-reach.c中将此方法更改为repo_in_merge_bases_many()。启发式算法计算“reference”列表的最小生成数，然后将此数与“commit”的生成数进行比较。
在最近的一个主题中，添加了一个测试，使用in_merge_bases_many()来测试一个提交是否可以从一个reflog中提取的多个提交中获得。如果任何参考提交具有比给定提交小的世代号，则如果存在具有更高世代号的一些提交，则跳过走查。
这个启发式是错误的！它必须检查引用提交的最大生成数，而不是最小生成数。
修复程序本身是将min_generation与repo_in_merge_bases_many()中的max_generation交换。
希望在Git 2.32之前（2021年第一季度），当仓库中使用的某些特性（例如移植）与commit-graph的使用不兼容时，我们会默认关闭commit-graph;我们现在告诉用户我们正在做什么。
参见Johannes Schindelin ( dscho )的commit c85eec7（2021年2月11日）。
（由Junio C Hamano -- gitster --合并至commit 726b11d，2021年2月17日）
这将显示Git 2.31的设计意图，但it has been reverted，因为它目前的形式有点过于热心。
我的天啊！当与图形不兼容时，请说明原因
签署人：约翰内斯·申德林
确认人：Derrick Stolee
当gc.writeCommitGraph = true时，有可能commit-graph * 仍然 * 未写入：替换对象、移植和浅层存储库与提交图功能不兼容。

在这种情况下，我们需要向用户指出为什么没有写commit-graph，而不是对此保持沉默。
警告包括：

repository contains replace objects; skipping commit-graph
repository contains (deprecated) grafts; skipping commit-graph
repository is shallow; skipping commit-graph