1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

========
toposort
========
Overview
========
Implements a topological sort algorithm.
From `Wikipedia <http://en.wikipedia.org/wiki/Topological_sorting>`_:
In computer science, a topological sort (sometimes abbreviated topsort
or toposort) or topological ordering of a directed graph is a linear
ordering of its vertices such that for every directed edge uv from
vertex u to vertex v, u comes before v in the ordering.
Input data description
======================
The input to the toposort function is a dict describing the
dependencies among the input nodes. Each key is a dependent node, the
corresponding value is a set containing the dependent nodes.
Note that toposort does not care what the input node values mean: it
just compares them for equality. The examples here usually use
integers, but they could be any hashable type.
Typical usage
=============
The interpretation of the input data here is: If 2 depends on 11; 9
depends on 11, 8 and 10; 10 depends on 11 and 3 (and so on), then in what
order should we process the items such that all nodes are processed
before any of their dependencies?::
>>> 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}]
And the answer is: process 3, 5, and 7 (in any order); then process 8
and 11; then process 2 and 10; then process 9. Note that 3, 5, and 7
are returned first because they do not depend on anything. They are
then removed from consideration, and then 8 and 11 don't depend on
anything remaining. This process continues until all nodes are
returned, or a circular dependency is detected.
Circular dependencies
=====================
A circular dependency will raise a CyclicDependencyError, which is
derived from ValueError. Here 1 depends on 2, and 2 depends on 1::
>>> list(toposort({1: {2},
... 2: {1},
... }))
Traceback (most recent call last):
...
toposort.CircularDependencyError: Circular dependencies exist among these items: {1:{2}, 2:{1}}
In addition, the 'data' attribute of the raised CyclicDependencyError
will contain a dict containing the subset of the input data involved
in the circular dependency.
Module contents
===============
``toposort(data)``
Returns an iterator describing the dependencies among nodes in the
input data. Each returned item will be a set. Each member of this set
has no dependencies in this set, or in any set previously returned.
``toposort_flatten(data, sort=True)``
Like toposort(data), except that it returns a list of all of the
depend values, in order. If sort is true, the returned nodes are sorted within
each group before they are appended to the result::
>>> 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]
Note that this result is the same as the first example: ``[{3, 5, 7}, {8, 11}, {2, 10}, {9}]``,
except that the result is flattened, and within each set the nodes
are sorted.
Testing
=======
To test, run 'python setup.py test'. On python >= 3.0, this also runs the doctests.
