toposort

概述

实现拓扑排序算法。

来自 维基百科 <http://en.wikipedia.org/wiki/Topological_sorting>：在计算机科学中，拓扑排序（有时缩写为topsort或toposort）或有向图的拓扑排序是其顶点的线性排序，使得对于每条从顶点u到顶点v的有向边uv，u在排序中排在v之前。

输入数据描述

toposort函数的输入是一个字典，描述了输入节点之间的依赖关系。每个键是一个依赖节点，对应的值是包含依赖节点的集合。

请注意，toposort不关心输入节点值的意义：它只是比较它们是否相等。这里的示例通常使用整数，但它们可以是任何可哈希的类型。

典型用法

这里输入数据的解释是：如果2依赖于11；9依赖于11、8和10；10依赖于11和3（等等），那么我们应该以什么顺序处理这些项，以确保在处理任何依赖项之前先处理所有节点呢？

>>> from toposort import toposort, toposort_flatten
>>> list(toposort({2: {11},
...                9: {11, 8, 10},
...                10: {11, 3},
...                11: {7, 5},
...                8: {7, 3},
...               }))
[{3, 5, 7}, {8, 11}, {2, 10}, {9}]

答案是：首先处理3、5和7（顺序不限）；然后处理8和11；然后处理2和10；然后处理9。请注意，3、5和7首先返回，因为它们不依赖于任何东西。然后它们从考虑中删除，然后8和11不依赖于任何剩余的东西。这个过程一直持续到返回所有节点，或者检测到循环依赖。

循环依赖

循环依赖将引发一个CyclicDependencyError，它由ValueError派生。这里1依赖于2，而2依赖于1：

>>> list(toposort({1: {2},
...                2: {1},
...               }))
Traceback (most recent call last):
    ...
toposort.CircularDependencyError: Circular dependencies exist among these items: {1:{2}, 2:{1}}

此外，引发的 CyclicDependencyError 的 'data' 属性将包含一个字典，其中包含参与循环依赖的输入数据子集。

模块内容

toposort(data)

返回一个迭代器，描述输入数据中节点之间的依赖关系。每个返回的项目都将是一个集合。该集合的每个成员在这个集合中或之前返回的任何集合中都没有依赖关系。

toposort_flatten(data, sort=True)

类似于 toposort(data)，但它返回所有依赖值的列表，并按顺序排列。如果 sort 为真，则将结果中的节点在每个组内排序后再追加到结果中：

>>> toposort_flatten({2: {11},
...                   9: {11, 8, 10},
...                   10: {11, 3},
...                   11: {7, 5},
...                   8: {7, 3},
...                  })
[3, 5, 7, 8, 11, 2, 10, 9]

注意，这个结果与第一个示例相同：[{3, 5, 7}, {8, 11}, {2, 10}, {9}]，但结果是扁平化的，并且在每个集合内节点是排序的。

测试

要测试，请运行 'python setup.py test'。在 python >= 3.0 中，这也会运行 doctests。