大型DAG的拓扑排序示例 [英] Examples for Topological Sorting on Large DAGs

问题描述

我正在寻找对大图大小执行拓扑排序的现实应用.

I am looking for real world applications where topological sorting is performed on large graph sizes.

我在其中成像的某些字段可能是生物信息学，依赖性解析，数据库，硬件设计，数据仓库...，但我希望你们中的某些人可能遇到或听说过任何特定的算法/项目/应用程序/需要topsort的数据集.

Some fields where I image you could find such instances would be bioinformatics, dependency resolution, databases, hardware design, data warehousing... but I hope some of you may have encountered or heard of any specific algorithms/projects/applications/datasets that require topsort.

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

Even if the data/project may not be publicly accessible any hints (and estimates on the order of magnitude of potential graph sizes) might be helpful.

推荐答案

以下是到目前为止我看到的一些有关拓扑排序的示例:

Here are some examples I've seen so far for Topological Sorting:

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

• While scheduling task graphs in a distributed system, it is usually needed to sort the tasks topologically and then assign them to resources. I am aware of task graphs containing more than 100,000 tasks to be sorted in a topological order. See this in this context.

从前，我正在使用文档管理系统.每个 该系统上的文档对某种文档具有某种优先权约束 一套其他文件，例如其内容类型或字段引用. 然后，系统应该能够生成文档的顺序 与保留的拓扑顺序.我记得，有 两年前有大约5,000,000个文档可用！！！

Once upon a time I was working on a Document Management System. Each document on this system has some kind of precedence constraint to a set of other documents, e.g. its content type or field referencing. Then, the system should be able to generate an order of the documents with the preserved topological order. As I can remember, there were around 5,000,000 documents available two years ago !!!

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

In the field of social networking, there is famous query to know the largest friendship distance in the network. This problem needs to traverse the graph by a BFS approach, equal to the cost of a topological sorting. Consider the members of Facebook and find your answer.

如果您需要更多真实的例子，请随时问我.我从事过很多处理大型图形的项目.

If you need more real examples, do not hesitate to ask me. I have worked in lots of projects working on on large graphs.

P.S.对于大型DAG数据集，您可以查看斯坦福大型网络数据集和

P.S. for large DAG datasets, you may take a look at Stanford Large Network Dataset Collection and Graphics@ Illinois page.

这篇关于大型DAG的拓扑排序示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！