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