12

我正在寻找在大图尺寸上执行拓扑排序的现实世界应用程序。

我认为您可以找到此类实例的一些领域是生物信息学、依赖关系解析、数据库、硬件设计、数据仓库……但我希望你们中的一些人可能已经遇到或听说过任何需要的特定算法/项目/应用程序/数据集顶级排序。

即使数据/项目可能无法公开访问，任何提示（以及对潜在图形大小数量级的估计）也可能会有所帮助。

4

4 回答 4

11

以下是我迄今为止看到的一些拓扑排序示例：

  • 在分布式系统中调度任务图时，通常需要对任务进行拓扑排序，然后将它们分配给资源。我知道包含超过 100,000 个任务的任务图按拓扑顺序排序。在这种情况下看到这个。

  • 曾几何时，我正在研究文档管理系统。这个系统上的每个文档对一组其他文档都有某种优先约束，例如它的内容类型或字段引用。然后，系统应该能够生成具有保留拓扑顺序的文档的顺序。我记得，两年前有大约 5,000,000 份文件可用！！！

  • 在社交网络领域，有著名的查询知道网络中最大的友谊距离。这个问题需要通过 BFS 的方式来遍历图，等于一次拓扑排序的代价。考虑 Facebook 的成员并找到您的答案。

如果您需要更多真实示例，请随时问我。我曾在许多处理大型图表的项目中工作过。

PS 对于大型 DAG 数据集，您可以查看Stanford Large Network Dataset Collection and Graphics@ Illinois页面。

于 2011-09-09T17:39:41.063 回答
3

我不确定这是否符合您的要求，但您知道Bio4j项目吗？

并非所有存储在基于图形的数据库中的内容都足以进行拓扑排序（图形的重要部分存在有向循环），但是有像基因本体和分类这样的子图，这种排序可能有意义。

于 2011-09-03T18:04:14.677 回答
1

TopoR是一种商业拓扑 PCB 路由器，它首先将 PCB 作为拓扑问题进行布线，然后将拓扑转换为物理空间。它们最多支持 32 个电层，因此它应该能够进行数千个连接（比如 10^4）。

我怀疑集成电路可能会使用类似的方法。

于 2011-09-08T14:08:08.593 回答
1

我工作的公司管理着一个（专有）软件漏洞和补丁数据库。补丁程序通常由软件供应商（如 Microsoft、Adobe 等）定期发布，并且“新的和改进的”补丁程序会“取代”旧的补丁程序，因为如果您将较新的补丁程序应用于主机然后旧的补丁程序不再需要补丁。

这产生了一个 DAG，其中每个软件补丁都是一个节点，弧指向每个“取代”补丁的节点。图表中目前有接近 10K 的节点，并且每周都会添加新补丁。

在这种情况下，拓扑排序可用于验证图形是否不包含循环 - 如果确实出现循环，则意味着添加新数据库记录时出错，或者数据库实例之间的数据复制不完善导致了损坏。

于 2011-09-09T01:06:46.777 回答