我正在寻找现实世界的应用程序拓扑排序执行于大图 sizes.
我想象您可以找到此类实例的一些领域是生物信息学、依赖性解析、数据库、硬件设计、数据仓库......但我希望你们中的一些人可能遇到或听说过任何需要的特定算法/项目/应用程序/数据集顶排序。
即使数据/项目可能无法公开访问,任何提示(以及对潜在图形大小的数量级的估计)也可能会有所帮助。
以下是我迄今为止见过的一些拓扑排序示例:
在分布式系统中调度任务图时,通常是
需要对任务进行拓扑排序,然后将它们分配给
资源。我知道任务图包含超过 100,000 个
任务按拓扑顺序排序。看this http://lara.inist.fr/handle/2332/509在此背景下。
曾几何时,我正在开发文档管理系统。每个
该系统上的文档具有某种优先级约束
一组其他文件,例如它的内容类型或字段引用。
然后,系统应该能够生成订单文件
并保留拓扑顺序。据我记得,有
两年前大约有 5,000,000 份可用文档!!!
在社交网络领域,有一个著名的查询:
网络中最大的友谊距离。这个问题需要
通过 BFS 方法遍历图,等于
拓扑排序。考虑 Facebook 的成员并找到您的
回答。
如果您需要更多真实例子,请随时询问我。我参与过许多涉及大型图表的项目。
附:对于大型 DAG 数据集,您可以看看斯坦福大学大型网络数据集 http://snap.stanford.edu/data/ and 图形@伊利诺伊州 https://wiki.engr.illinois.edu/display/graphics/Graph+Dataset page.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)