Skip to main content

Implements a topological sort algorithm.

Project description

Overview

Implements a topological sort algorithm.

From Wikipedia: 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 ValueError. Here 1 depends on 2, and 2 depends on 1:

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

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.

Change log

0.2 2014-02-10 Eric V. Smith

  • Modify setup.py to produce python-toposort for bdist_rpm.

0.1 2014-02-10 Eric V. Smith

  • Initial release.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

toposort-0.2.tar.gz (9.0 kB view details)

Uploaded Source

File details

Details for the file toposort-0.2.tar.gz.

File metadata

  • Download URL: toposort-0.2.tar.gz
  • Upload date:
  • Size: 9.0 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No

File hashes

Hashes for toposort-0.2.tar.gz
Algorithm Hash digest
SHA256 5ea7cfdf183e12b4cd4ffb4132b6f101fef04982be1a8b949d2fdb1b9007dd84
MD5 29d3335eb0da0d93c61fff710440f32c
BLAKE2b-256 1719b1c46beb8899b5dc5b6cde57f0e82fcaa45911c62ca71176de93b092bc36

See more details on using hashes here.

Provenance

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page