在大型DAG上进行拓扑分类的示例

Question

我在寻找真实世界的应用，其中拓扑分类在大图大小上执行。

一些我可以找到这种实例的领域是生物信息学，依赖关系解析，数据库，硬件设计，数据仓库......但是我希望你们中的一些人可能遇到或听说过任何特定的算法/项目/应用程序/需要topsort的数据集。

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

Answer 1

下面是一些例子迄今拓扑排序我看到：

• 虽然在分布式系统调度的任务图，它通常是 需要的任务拓扑排序，然后将其分配给 资源。我知道任务图中包含超过100,000个要按拓扑顺序排序的 任务。在这方面请参阅this。

• 曾几何时，我一直致力于文档管理系统。该系统上的每个 文档对其他文档的一组文档具有某种优先约束，例如，其内容类型或字段引用。 然后，系统应该能够生成具有保留的拓扑顺序的文档 的顺序。据我记忆，两年前有大约5,000,000个文件可用 !!!

• 在社交网络领域，有着名的查询知道了网络中最大的友谊距离 。此问题需要 通过BFS方法遍历图形，等于拓扑排序的成本。考虑Facebook的成员，并找到你的答案 。

如果您需要更多的实例，请不要犹豫，问我。我曾在许多在大型图表上工作的项目工作过。

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

Answer 2

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

并非存储在基于图的数据库中的所有内容都适合于拓扑排序（在图的重要部分存在定向循环），但是存在子图，如基因本体论和分类标准，其中该排序可能具有感。

Answer 3

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

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

Answer 4

company where I work管理软件漏洞和补丁的（专有）数据库。修补程序通常由软件供应商（如Microsoft，Adobe等）定期发布，而“新的和改进的”修补程序“替代”较旧的修补程序，因为如果将新修补程序应用于主机，则旧补丁不再需要。

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

拓扑排序在此上下文中用于验证图形不包含循环 - 如果它们确实存在，则意味着在添加新的数据库记录时出现错误，或者由于错误的数据复制而引入损坏数据库实例之间。