大型 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 个的任务图任务按拓扑顺序排序.在这种情况下，请参阅 this.

曾几何时，我正在研究一个文档管理系统.每个该系统上的文档对一组其他文件，例如它的内容类型或字段引用.然后，系统应该能够生成一个订单的文件具有保留的拓扑顺序.我记得，有两年前大约有 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.

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

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

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