我是GitX的作者。GitX 的功能之一是分支的可视化，可以在这里看到。
这种可视化当前是通过读取从 git 以正确顺序发出的提交来完成的。对于每个提交，父母都是已知的，因此以正确的方式建立通道相当容易。
我想通过使用我自己的提交池并自己线性化提交来加快这个过程。这允许我重用现有的已加载提交并允许 git 更快地发出提交，因为它不必以正确的顺序发出它们。
但是，我不确定使用什么算法来实现这一点。重要的是构建是增量的，因为提交的加载可能需要很长时间（100,000 次提交超过 5 秒，应该全部显示）。
Gitk 也是如此，这里有一个补丁说明了它是如何实现的，但是我的 TCL 技能很弱，而且补丁的注释不是很彻底，而且有点难以理解。
我还希望这个算法高效，因为它必须处理数十万次提交。它还必须显示在表格中，因此快速访问特定行很重要。
我将描述到目前为止的输入、我想要的输出和一些观察结果。
输入：
- 我有一个哈希表形式的当前提交池，将提交 ID 映射到提交对象。此池不必是完整的（具有所有必要的提交）
- 我在 git 的新提交中加载了一个单独的线程，每次加载新提交时都可以调用一个回调。没有保证提交的顺序，但在大多数情况下，下一个提交是前一个提交的父级。
- 一个提交对象有自己的修订 id 和所有其父对象的修订 id
- 我有一个应该列出的分支负责人列表。也就是说，没有应该显示的 DAG 的单个“顶部”。也不必有单个图根。
输出：
- 我需要按拓扑顺序线性化这些提交。也就是说，一个提交在其父项被列出之后不能被列出。
- 我还需要可以在上面的屏幕截图中看到的“分支线”。这些可能需要预先计算，因为它们中的大多数依赖于他们的孩子。
几点说明：
- 有必要重新定位提交列表。例如，我们可能必须提交不相关的提交（分支头），直到出现使一个头成为另一个头的祖先的提交。
- 必须显示多个分支提示
- 重要的是这个过程是增量的，以便在数据仍在加载时至少有部分视图可用。这意味着必须在中途插入新数据并且必须重新调整分支线。