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.

Package profile

toposort

Releases

Release table

PyPI Downloads

Dependencies

Details

Project URLs

Dependencies

Package description