| Name | toposort JSON |
| Version |
1.9
JSON |
| download |
| home_page | |
| Summary | Implements a topological sort algorithm. |
| upload_time | 2023-01-11 12:22:33 |
| maintainer | |
| docs_url | None |
| author | |
| requires_python | |
| license | Apache License Version 2.0 |
| keywords |
|
| VCS |
|
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
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.
Raw data
{
"_id": null,
"home_page": "",
"name": "toposort",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "",
"author": "",
"author_email": "\"Eric V. Smith\" <eric@trueblade.com>",
"download_url": "https://files.pythonhosted.org/packages/8d/c3/44e51b42160145e4ebeb7d86ab93bd933fa9498f94e183ef8a47c6de8b2f/toposort-1.9.tar.gz",
"platform": null,
"description": "toposort\n========\n\nOverview\n========\n\nImplements a topological sort algorithm.\n\nFrom `Wikipedia <http://en.wikipedia.org/wiki/Topological_sorting>`_:\nIn computer science, a topological sort (sometimes abbreviated topsort\nor toposort) or topological ordering of a directed graph is a linear\nordering of its vertices such that for every directed edge uv from\nvertex u to vertex v, u comes before v in the ordering.\n\nInput data description\n======================\n\nThe input to the toposort function is a dict describing the\ndependencies among the input nodes. Each key is a dependent node, the\ncorresponding value is a set containing the dependent nodes.\n\nNote that toposort does not care what the input node values mean: it\njust compares them for equality. The examples here usually use\nintegers, but they could be any hashable type.\n\nTypical usage\n=============\n\nThe interpretation of the input data here is: If 2 depends on 11; 9\ndepends on 11, 8 and 10; 10 depends on 11 and 3 (and so on), then in what\norder should we process the items such that all nodes are processed\nbefore any of their dependencies?::\n\n >>> from toposort import toposort, toposort_flatten\n >>> list(toposort({2: {11},\n ... 9: {11, 8, 10},\n ... 10: {11, 3},\n ... 11: {7, 5},\n ... 8: {7, 3},\n ... }))\n [{3, 5, 7}, {8, 11}, {2, 10}, {9}]\n\nAnd the answer is: process 3, 5, and 7 (in any order); then process 8\nand 11; then process 2 and 10; then process 9. Note that 3, 5, and 7\nare returned first because they do not depend on anything. They are\nthen removed from consideration, and then 8 and 11 don't depend on\nanything remaining. This process continues until all nodes are\nreturned, or a circular dependency is detected.\n\nCircular dependencies\n=====================\n\nA circular dependency will raise a CyclicDependencyError, which is\nderived from ValueError. Here 1 depends on 2, and 2 depends on 1::\n\n >>> list(toposort({1: {2},\n ... 2: {1},\n ... }))\n Traceback (most recent call last):\n ...\n toposort.CircularDependencyError: Circular dependencies exist among these items: {1:{2}, 2:{1}}\n\nIn addition, the 'data' attribute of the raised CyclicDependencyError\nwill contain a dict containing the subset of the input data involved\nin the circular dependency.\n\n\nModule contents\n===============\n\n``toposort(data)``\n\nReturns an iterator describing the dependencies among nodes in the\ninput data. Each returned item will be a set. Each member of this set\nhas no dependencies in this set, or in any set previously returned.\n\n``toposort_flatten(data, sort=True)``\n\nLike toposort(data), except that it returns a list of all of the\ndepend values, in order. If sort is true, the returned nodes are sorted within\neach group before they are appended to the result::\n\n >>> toposort_flatten({2: {11},\n ... 9: {11, 8, 10},\n ... 10: {11, 3},\n ... 11: {7, 5},\n ... 8: {7, 3},\n ... })\n [3, 5, 7, 8, 11, 2, 10, 9]\n\nNote that this result is the same as the first example: ``[{3, 5, 7}, {8, 11}, {2, 10}, {9}]``,\nexcept that the result is flattened, and within each set the nodes\nare sorted.\n\n\nTesting\n=======\n\nTo test, run 'python setup.py test'. On python >= 3.0, this also runs the doctests.\n",
"bugtrack_url": null,
"license": "Apache License Version 2.0",
"summary": "Implements a topological sort algorithm.",
"version": "1.9",
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "bad8494820a2dc0c03ea8594011b9dac352125c0bd26d5d9db5852fb1663d4b1",
"md5": "f2a494588290b06e9e3307612672fa3d",
"sha256": "9f434c815e1bd2f9ad05152b6b0071b1f56e288c107869708f2463ec932e2637"
},
"downloads": -1,
"filename": "toposort-1.9-py3-none-any.whl",
"has_sig": false,
"md5_digest": "f2a494588290b06e9e3307612672fa3d",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 8371,
"upload_time": "2023-01-11T12:22:32",
"upload_time_iso_8601": "2023-01-11T12:22:32.555577Z",
"url": "https://files.pythonhosted.org/packages/ba/d8/494820a2dc0c03ea8594011b9dac352125c0bd26d5d9db5852fb1663d4b1/toposort-1.9-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "8dc344e51b42160145e4ebeb7d86ab93bd933fa9498f94e183ef8a47c6de8b2f",
"md5": "41d51c2388c3554a2c71e736723db583",
"sha256": "f41a34490d44934b533a7bdaff979ee8a47203fd2d8a746db83f2d5ab12458b9"
},
"downloads": -1,
"filename": "toposort-1.9.tar.gz",
"has_sig": false,
"md5_digest": "41d51c2388c3554a2c71e736723db583",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 10878,
"upload_time": "2023-01-11T12:22:33",
"upload_time_iso_8601": "2023-01-11T12:22:33.812467Z",
"url": "https://files.pythonhosted.org/packages/8d/c3/44e51b42160145e4ebeb7d86ab93bd933fa9498f94e183ef8a47c6de8b2f/toposort-1.9.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-01-11 12:22:33",
"github": false,
"gitlab": false,
"bitbucket": false,
"lcname": "toposort"
}
