File: README.txt

package info (click to toggle)
toposort 1.5-3
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, sid
  • size: 120 kB
  • sloc: python: 213; sh: 20; makefile: 6
file content (100 lines) | stat: -rw-r--r-- 3,416 bytes parent folder | download | duplicates (3)
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.