Script 'mail_helper' called by obssrc
Hello community,
here is the log from the commit of package python-toposort for openSUSE:Factory
checked in at 2021-10-23 23:14:06
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Comparing /work/SRC/openSUSE:Factory/python-toposort (Old)
and /work/SRC/openSUSE:Factory/.python-toposort.new.1890 (New)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "python-toposort"
Sat Oct 23 23:14:06 2021 rev:2 rq:927092 version:1.7
Changes:
--------
--- /work/SRC/openSUSE:Factory/python-toposort/python-toposort.changes
2020-09-15 16:26:36.050499748 +0200
+++
/work/SRC/openSUSE:Factory/.python-toposort.new.1890/python-toposort.changes
2021-10-23 23:14:16.704989956 +0200
@@ -1,0 +2,8 @@
+Fri Oct 22 20:19:36 UTC 2021 - Ben Greiner <c...@bnavigator.de>
+
+- Update to version 1.7
+ * Changed to use setup.cfg and pyproject.toml. Deleted setup.py.
+ * GH issue #1: No longer modify input data structures. Thanks
+ Lenz Furrer.
+
+-------------------------------------------------------------------
Old:
----
toposort-1.5.tar.gz
New:
----
toposort-1.7.tar.gz
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Other differences:
------------------
++++++ python-toposort.spec ++++++
--- /var/tmp/diff_new_pack.Zstrw4/_old 2021-10-23 23:14:17.108990153 +0200
+++ /var/tmp/diff_new_pack.Zstrw4/_new 2021-10-23 23:14:17.108990153 +0200
@@ -1,7 +1,7 @@
#
# spec file for package python-toposort
#
-# Copyright (c) 2020 SUSE LLC
+# Copyright (c) 2021 SUSE LLC
#
# All modifications and additions to the file contributed by third parties
# remain the property of their copyright owners, unless otherwise agreed
@@ -18,14 +18,16 @@
%{?!python_module:%define python_module() python-%{**} python3-%{**}}
Name: python-toposort
-Version: 1.5
+Version: 1.7
Release: 0
Summary: Implements a topological sort algorithm
License: Apache-2.0
Group: Development/Languages/Python
-URL: https://bitbucket.org/ericvsmith/toposort
+URL: https://gitlab.com/ericvsmith/toposort
Source:
https://files.pythonhosted.org/packages/source/t/toposort/toposort-%{version}.tar.gz
+BuildRequires: %{python_module pip}
BuildRequires: %{python_module setuptools}
+BuildRequires: %{python_module wheel}
BuildRequires: fdupes
BuildRequires: python-rpm-macros
BuildArch: noarch
@@ -37,20 +39,24 @@
%prep
%setup -q -n toposort-%{version}
chmod a-x *.txt
+# can't discover and execute at the same time
+sed -i '/unittest.main/d' test/test_toposort.py
%build
-%python_build
+%pyproject_wheel
%install
-%python_install
+%pyproject_install
%python_expand %fdupes %{buildroot}%{$python_sitelib}
%check
-%python_exec setup.py test
+%pyunittest -v
%files %{python_files}
%doc CHANGES.txt README.txt
%license LICENSE.txt
-%{python_sitelib}/*
+%{python_sitelib}/toposort.py*
+%pycache_only %{python_sitelib}/__pycache__/toposort*
+%{python_sitelib}/toposort-%{version}*-info
%changelog
++++++ toposort-1.5.tar.gz -> toposort-1.7.tar.gz ++++++
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/CHANGES.txt new/toposort-1.7/CHANGES.txt
--- old/toposort-1.5/CHANGES.txt 2016-10-25 03:03:14.000000000 +0200
+++ new/toposort-1.7/CHANGES.txt 2021-09-28 16:18:39.000000000 +0200
@@ -1,6 +1,19 @@
Change log
==========
+1.7 2021-09-28 Eric V. Smith
+----------------------------
+
+* Changed to use setup.cfg and pyproject.toml. Deleted setup.py.
+
+* GH issue #1: No longer modify input data structures. Thanks Lenz
+ Furrer.
+
+1.6 2020-12-17 Eric V. Smith
+----------------------------
+
+* No changes, just updated the project URL from bitbucket to gitlab.
+
1.5 2016-10-24 Eric V. Smith
----------------------------
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/MANIFEST.in new/toposort-1.7/MANIFEST.in
--- old/toposort-1.5/MANIFEST.in 2015-05-16 19:16:56.000000000 +0200
+++ new/toposort-1.7/MANIFEST.in 2021-09-28 16:21:19.000000000 +0200
@@ -1 +1 @@
-include NOTICE *.txt MANIFEST.in test/__init__.py
+include NOTICE *.txt MANIFEST.in test/__init__.py Makefile
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/Makefile new/toposort-1.7/Makefile
--- old/toposort-1.5/Makefile 1970-01-01 01:00:00.000000000 +0100
+++ new/toposort-1.7/Makefile 2021-09-28 18:44:43.000000000 +0200
@@ -0,0 +1,18 @@
+all: wheel sdist
+
+wheel:
+ python3 -m build --wheel
+
+sdist:
+ python3 -m build --sdist
+
+clean:
+ rm -rf build/ dist/ src/*.egg-info src/__pycache__ test/__pycache__
+
+test: unittest doctest
+
+unittest:
+ PYTHONPATH=src:test python3 -m test.test_toposort
+
+doctest:
+ PYTHONPATH=src python3 -m doctest README.txt
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/NOTICE new/toposort-1.7/NOTICE
--- old/toposort-1.5/NOTICE 2014-02-11 01:08:24.000000000 +0100
+++ new/toposort-1.7/NOTICE 2021-09-26 18:35:36.000000000 +0200
@@ -1,4 +1,4 @@
-Copyright 2014 True Blade Systems, Inc.
+Copyright 2014-2021 True Blade Systems, Inc.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/PKG-INFO new/toposort-1.7/PKG-INFO
--- old/toposort-1.5/PKG-INFO 2016-10-25 03:05:02.000000000 +0200
+++ new/toposort-1.7/PKG-INFO 2021-09-28 19:03:16.734459900 +0200
@@ -1,185 +1,125 @@
-Metadata-Version: 1.1
+Metadata-Version: 2.1
Name: toposort
-Version: 1.5
-Summary: Implements a topological sort algorithm.
-Home-page: https://bitbucket.org/ericvsmith/toposort
-Author: Eric V. Smith
-Author-email: e...@trueblade.com
-License: Apache License Version 2.0
-Description: ========
- 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.
-
- Change log
- ==========
-
- 1.5 2016-10-24 Eric V. Smith
- ----------------------------
-
- * When a circular dependency error is detected, raise a specific
- exception, CircularDependencyError, which is a subclass of
- ValueError. The 'data' attribute of the exception will contain the
- data involved in the circular dependency (issue #2). Thanks
- lilydjwg for the initial patch.
-
- * To make building wheels easier, always require setuptools in
- setup.py (issue #5).
-
- * Mark wheel as being universal, that is, supporting both Python 2.7
- and 3.x (issue #7).
-
- 1.4 2015-05-16 Eric V. Smith
- ----------------------------
-
- * Removed 'test' package, so it won't get installed by bdist_*. It's
still
- included in sdists.
-
- * No code changes.
-
- 1.3 2015-05-15 Eric V. Smith
- ----------------------------
-
- * Fixed change log date.
-
- * No code changes.
-
- 1.2 2015-05-15 Eric V. Smith
- ----------------------------
-
- * Changed RPM name to python3-toposort if running with python 3.
-
- * No code changes.
-
- 1.1 2014-07-24 Eric V. Smith
- ----------------------------
-
- * Release version 1.1. No code changes.
-
- * Add a README.txt entry on running the test suite.
-
- * Fix missing test/__init__.py in the sdist.
-
- 1.0 2014-03-14 Eric V. Smith
- ----------------------------
-
- * Release version 1.0. The API is stable.
-
- * Add MANIFEST.in to MANIFEST.in, so that it is created in the sdist
- (issue #1).
-
- 0.2 2014-02-11 Eric V. Smith
- ----------------------------
-
- * Modify setup.py to produce a RPM name of python-toposort for
bdist_rpm.
-
- 0.1 2014-02-10 Eric V. Smith
- ----------------------------
-
- * Initial release.
-
+Version: 1.7
+Summary: "Implements a topological sort algorithm."
+Home-page: UNKNOWN
+Author: "Eric V. Smith"
+Author-email: "e...@trueblade.com"
+License: "Apache License Version 2.0"
Platform: UNKNOWN
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: Apache Software License
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Classifier: Programming Language :: Python :: 2.7
-Classifier: Programming Language :: Python :: 3.3
-Classifier: Programming Language :: Python :: 3.4
-Classifier: Programming Language :: Python :: 3.5
+Classifier: Programming Language :: Python :: 3.6
+Classifier: Programming Language :: Python :: 3.7
+Classifier: Programming Language :: Python :: 3.8
+Classifier: Programming Language :: Python :: 3.9
+Classifier: Programming Language :: Python :: 3.10
+Description-Content-Type: text/x-rst
+License-File: LICENSE.txt
+License-File: NOTICE
+
+========
+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.
+
+
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/pyproject.toml
new/toposort-1.7/pyproject.toml
--- old/toposort-1.5/pyproject.toml 1970-01-01 01:00:00.000000000 +0100
+++ new/toposort-1.7/pyproject.toml 2021-09-26 21:11:54.000000000 +0200
@@ -0,0 +1,6 @@
+[build-system]
+requires = [
+ "setuptools>=42",
+ "wheel",
+]
+build-backend = "setuptools.build_meta"
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/setup.cfg new/toposort-1.7/setup.cfg
--- old/toposort-1.5/setup.cfg 2016-10-25 03:05:02.000000000 +0200
+++ new/toposort-1.7/setup.cfg 2021-09-28 19:03:16.734971500 +0200
@@ -1,8 +1,34 @@
+[metadata]
+name = toposort
+version = attr: toposort.__version__
+author = "Eric V. Smith"
+author_email = "e...@trueblade.com"
+description = "Implements a topological sort algorithm."
+long_description = file: README.txt
+long_description_content_type = text/x-rst
+license = "Apache License Version 2.0"
+classifier =
+ Development Status :: 5 - Production/Stable
+ Intended Audience :: Developers
+ License :: OSI Approved :: Apache Software License
+ Topic :: Software Development :: Libraries :: Python Modules
+ Programming Language :: Python :: 2.7
+ Programming Language :: Python :: 3.6
+ Programming Language :: Python :: 3.7
+ Programming Language :: Python :: 3.8
+ Programming Language :: Python :: 3.9
+ Programming Language :: Python :: 3.10
+
+[options]
+package_dir =
+ =src
+py_modules =
+ toposort
+
[bdist_wheel]
universal = 1
[egg_info]
tag_build =
tag_date = 0
-tag_svn_revision = 0
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/setup.py new/toposort-1.7/setup.py
--- old/toposort-1.5/setup.py 2016-10-25 03:02:53.000000000 +0200
+++ new/toposort-1.7/setup.py 1970-01-01 01:00:00.000000000 +0100
@@ -1,46 +0,0 @@
-from __future__ import print_function
-from setuptools import setup, Command
-
-# run our tests
-class PyTest(Command):
- user_options = []
- def initialize_options(self):
- pass
- def finalize_options(self):
- pass
- def run(self):
- import sys, subprocess
- tests = [('test suite', ['-m', 'test.test_toposort']),
- ]
- if sys.hexversion >= 0x03000000:
- # Skip doctests for python < 3.0. They use set literal reprs, which
- # are different in 2.7. Testing under 3.x is good enough.
- tests.append(('doctests', ['-m' 'doctest', 'README.txt']))
- for name, cmds in tests:
- print(name)
- errno = subprocess.call([sys.executable] + cmds)
- if errno != 0:
- raise SystemExit(errno)
- print('test complete')
-
-
-setup(name='toposort',
- version='1.5',
- url='https://bitbucket.org/ericvsmith/toposort',
- author='Eric V. Smith',
- author_email='e...@trueblade.com',
- description='Implements a topological sort algorithm.',
- long_description=open('README.txt').read() + '\n' +
open('CHANGES.txt').read(),
- classifiers=['Development Status :: 5 - Production/Stable',
- 'Intended Audience :: Developers',
- 'License :: OSI Approved :: Apache Software License',
- 'Topic :: Software Development :: Libraries :: Python
Modules',
- 'Programming Language :: Python :: 2.7',
- 'Programming Language :: Python :: 3.3',
- 'Programming Language :: Python :: 3.4',
- 'Programming Language :: Python :: 3.5',
- ],
- license='Apache License Version 2.0',
- py_modules=['toposort'],
- cmdclass = {'test': PyTest},
- )
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/src/toposort.egg-info/PKG-INFO
new/toposort-1.7/src/toposort.egg-info/PKG-INFO
--- old/toposort-1.5/src/toposort.egg-info/PKG-INFO 1970-01-01
01:00:00.000000000 +0100
+++ new/toposort-1.7/src/toposort.egg-info/PKG-INFO 2021-09-28
19:03:16.000000000 +0200
@@ -0,0 +1,125 @@
+Metadata-Version: 2.1
+Name: toposort
+Version: 1.7
+Summary: "Implements a topological sort algorithm."
+Home-page: UNKNOWN
+Author: "Eric V. Smith"
+Author-email: "e...@trueblade.com"
+License: "Apache License Version 2.0"
+Platform: UNKNOWN
+Classifier: Development Status :: 5 - Production/Stable
+Classifier: Intended Audience :: Developers
+Classifier: License :: OSI Approved :: Apache Software License
+Classifier: Topic :: Software Development :: Libraries :: Python Modules
+Classifier: Programming Language :: Python :: 2.7
+Classifier: Programming Language :: Python :: 3.6
+Classifier: Programming Language :: Python :: 3.7
+Classifier: Programming Language :: Python :: 3.8
+Classifier: Programming Language :: Python :: 3.9
+Classifier: Programming Language :: Python :: 3.10
+Description-Content-Type: text/x-rst
+License-File: LICENSE.txt
+License-File: NOTICE
+
+========
+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.
+
+
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/src/toposort.egg-info/SOURCES.txt
new/toposort-1.7/src/toposort.egg-info/SOURCES.txt
--- old/toposort-1.5/src/toposort.egg-info/SOURCES.txt 1970-01-01
01:00:00.000000000 +0100
+++ new/toposort-1.7/src/toposort.egg-info/SOURCES.txt 2021-09-28
19:03:16.000000000 +0200
@@ -0,0 +1,15 @@
+CHANGES.txt
+LICENSE.txt
+MANIFEST.in
+Makefile
+NOTICE
+README.txt
+pyproject.toml
+setup.cfg
+src/toposort.py
+src/toposort.egg-info/PKG-INFO
+src/toposort.egg-info/SOURCES.txt
+src/toposort.egg-info/dependency_links.txt
+src/toposort.egg-info/top_level.txt
+test/__init__.py
+test/test_toposort.py
\ No newline at end of file
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/toposort-1.5/src/toposort.egg-info/dependency_links.txt
new/toposort-1.7/src/toposort.egg-info/dependency_links.txt
--- old/toposort-1.5/src/toposort.egg-info/dependency_links.txt 1970-01-01
01:00:00.000000000 +0100
+++ new/toposort-1.7/src/toposort.egg-info/dependency_links.txt 2021-09-28
19:03:16.000000000 +0200
@@ -0,0 +1 @@
+
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/src/toposort.egg-info/top_level.txt
new/toposort-1.7/src/toposort.egg-info/top_level.txt
--- old/toposort-1.5/src/toposort.egg-info/top_level.txt 1970-01-01
01:00:00.000000000 +0100
+++ new/toposort-1.7/src/toposort.egg-info/top_level.txt 2021-09-28
19:03:16.000000000 +0200
@@ -0,0 +1 @@
+toposort
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/src/toposort.py
new/toposort-1.7/src/toposort.py
--- old/toposort-1.5/src/toposort.py 1970-01-01 01:00:00.000000000 +0100
+++ new/toposort-1.7/src/toposort.py 2021-09-28 18:49:02.000000000 +0200
@@ -0,0 +1,96 @@
+#######################################################################
+# Implements a topological sort algorithm.
+#
+# Copyright 2014-2021 True Blade Systems, Inc.
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+# Notes:
+# Based on http://code.activestate.com/recipes/578272-topological-sort
+# with these major changes:
+# Added unittests.
+# Deleted doctests (maybe not the best idea in the world, but it cleans
+# up the docstring).
+# Moved functools import to the top of the file.
+# Changed assert to a ValueError.
+# Changed iter[items|keys] to [items|keys], for python 3
+# compatibility. I don't think it matters for python 2 these are
+# now lists instead of iterables.
+# Copy the input so as to leave it unmodified.
+# Renamed function from toposort2 to toposort.
+# Handle empty input.
+# Switch tests to use set literals.
+#
+########################################################################
+
+from functools import reduce as _reduce
+
+__all__ = ["toposort", "toposort_flatten", "CircularDependencyError"]
+__version__ = "1.7"
+
+
+class CircularDependencyError(ValueError):
+ def __init__(self, data):
+ # Sort the data just to make the output consistent, for use in
+ # error messages. That's convenient for doctests.
+ s = "Circular dependencies exist among these items: {{{}}}".format(
+ ", ".join(
+ "{!r}:{!r}".format(key, value) for key, value in
sorted(data.items())
+ )
+ )
+ super(CircularDependencyError, self).__init__(s)
+ self.data = data
+
+
+def toposort(data):
+ """\
+Dependencies are expressed as a dictionary whose keys are items
+and whose values are a set of dependent items. Output is a list of
+sets in topological order. The first set consists of items with no
+dependences, each subsequent set consists of items that depend upon
+items in the preceeding sets."""
+
+ # Special case empty input.
+ if len(data) == 0:
+ return
+
+ # Copy the input so as to leave it unmodified.
+ # Discard self-dependencies and copy two levels deep.
+ data = {item: set(e for e in dep if e != item) for item, dep in
data.items()}
+
+ # Find all items that don't depend on anything.
+ extra_items_in_deps = _reduce(set.union, data.values()) - set(data.keys())
+ # Add empty dependences where needed.
+ data.update({item: set() for item in extra_items_in_deps})
+ while True:
+ ordered = set(item for item, dep in data.items() if len(dep) == 0)
+ if not ordered:
+ break
+ yield ordered
+ data = {
+ item: (dep - ordered) for item, dep in data.items() if item not in
ordered
+ }
+ if len(data) != 0:
+ raise CircularDependencyError(data)
+
+
+def toposort_flatten(data, sort=True):
+ """\
+Returns a single list of dependencies. For any set returned by
+toposort(), those items are sorted and appended to the result (just to
+make the results deterministic)."""
+
+ result = []
+ for d in toposort(data):
+ result.extend((sorted if sort else list)(d))
+ return result
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/test/test_toposort.py
new/toposort-1.7/test/test_toposort.py
--- old/toposort-1.5/test/test_toposort.py 2016-10-25 02:38:50.000000000
+0200
+++ new/toposort-1.7/test/test_toposort.py 2021-09-28 16:24:55.000000000
+0200
@@ -1,7 +1,7 @@
#######################################################################
# Tests for toposort module.
#
-# Copyright 2014 True Blade Systems, Inc.
+# Copyright 2014-2021 True Blade Systems, Inc.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
@@ -23,64 +23,100 @@
from toposort import toposort, toposort_flatten, CircularDependencyError
+
class TestCase(unittest.TestCase):
def test_simple(self):
- self.assertEqual(list(toposort({2: {11},
- 9: {11, 8},
- 10: {11, 3},
- 11: {7, 5},
- 8: {7, 3},
- })),
- [{3, 5, 7},
- {8, 11},
- {2, 9, 10},
- ])
-
- # make sure self dependencies are ignored
- self.assertEqual(list(toposort({2: {2, 11},
- 9: {11, 8},
- 10: {10, 11, 3},
- 11: {7, 5},
- 8: {7, 3},
- })),
- [{3, 5, 7},
- {8, 11},
- {2, 9, 10},
- ])
-
- self.assertEqual(list(toposort({1: set()})),
- [{1}])
- self.assertEqual(list(toposort({1: {1}})),
- [{1}])
+ self.assertEqual(
+ list(
+ toposort(
+ {
+ 2: {11},
+ 9: {11, 8},
+ 10: {11, 3},
+ 11: {7, 5},
+ 8: {7, 3},
+ }
+ )
+ ),
+ [
+ {3, 5, 7},
+ {8, 11},
+ {2, 9, 10},
+ ],
+ )
+
+ # Make sure self dependencies are ignored.
+ self.assertEqual(
+ list(
+ toposort(
+ {
+ 2: {2, 11},
+ 9: {11, 8},
+ 10: {10, 11, 3},
+ 11: {7, 5},
+ 8: {7, 3},
+ }
+ )
+ ),
+ [
+ {3, 5, 7},
+ {8, 11},
+ {2, 9, 10},
+ ],
+ )
+
+ self.assertEqual(list(toposort({1: set()})), [{1}])
+ self.assertEqual(list(toposort({1: {1}})), [{1}])
def test_no_dependencies(self):
- self.assertEqual(list(toposort({1: {2},
- 3: {4},
- 5: {6},
- })),
- [{2, 4, 6}, {1, 3, 5}])
-
- self.assertEqual(list(toposort({1: set(),
- 3: set(),
- 5: set(),
- })),
- [{1, 3, 5}])
+ self.assertEqual(
+ list(
+ toposort(
+ {
+ 1: {2},
+ 3: {4},
+ 5: {6},
+ }
+ )
+ ),
+ [{2, 4, 6}, {1, 3, 5}],
+ )
+
+ self.assertEqual(
+ list(
+ toposort(
+ {
+ 1: set(),
+ 3: set(),
+ 5: set(),
+ }
+ )
+ ),
+ [{1, 3, 5}],
+ )
def test_empty(self):
- self.assertEqual(list(toposort({})),
- [])
+ self.assertEqual(list(toposort({})), [])
def test_strings(self):
- self.assertEqual(list(toposort({'2': {'11'},
- '9': {'11', '8'},
- '10': {'11', '3'},
- '11': {'7', '5'},
- '8': {'7', '3'},
- })),
- [{'3', '5', '7'},
- {'8', '11'},
- {'2', '9', '10'},
- ])
+ self.assertEqual(
+ list(
+ toposort(
+ {
+ "2": {"11"},
+ "9": {"11", "8"},
+ "10": {"11", "3"},
+ "11": {"7", "5"},
+ "8": {"7", "3"},
+ }
+ )
+ ),
+ [
+ {"3", "5", "7"},
+ {"8", "11"},
+ {"2", "9", "10"},
+ ],
+ )
def test_objects(self):
o2 = object()
@@ -91,92 +127,129 @@
o9 = object()
o10 = object()
o11 = object()
- self.assertEqual(list(toposort({o2: {o11},
- o9: {o11, o8},
- o10: {o11, o3},
- o11: {o7, o5},
- o8: {o7, o3, o8},
- })),
- [{o3, o5, o7},
- {o8, o11},
- {o2, o9, o10},
- ])
+ self.assertEqual(
+ list(
+ toposort(
+ {
+ o2: {o11},
+ o9: {o11, o8},
+ o10: {o11, o3},
+ o11: {o7, o5},
+ o8: {o7, o3, o8},
+ }
+ )
+ ),
+ [
+ {o3, o5, o7},
+ {o8, o11},
+ {o2, o9, o10},
+ ],
+ )
def test_cycle(self):
- # a simple, 2 element cycle
- # make sure we can catch this both as ValueError and
CircularDependencyError
- self.assertRaises(ValueError, list, toposort({1: {2},
- 2: {1}
- }))
+ # A simple, 2 element cycle.
+ # Make sure we can catch this both as ValueError and
CircularDependencyError.
+ self.assertRaises(ValueError, list, toposort({1: {2}, 2: {1}}))
with self.assertRaises(CircularDependencyError) as ex:
- list(toposort({1: {2},
- 2: {1}
- }))
+ list(toposort({1: {2}, 2: {1}}))
self.assertEqual(ex.exception.data, {1: {2}, 2: {1}})
- # an indirect cycle
- self.assertRaises(ValueError, list, toposort({1: {2},
- 2: {3},
- 3: {1},
- }))
+ # An indirect cycle.
+ self.assertRaises(
+ ValueError,
+ list,
+ toposort(
+ {
+ 1: {2},
+ 2: {3},
+ 3: {1},
+ }
+ ),
+ )
with self.assertRaises(CircularDependencyError) as ex:
- list(toposort({1: {2},
- 2: {3},
- 3: {1},
- }))
+ list(
+ toposort(
+ {
+ 1: {2},
+ 2: {3},
+ 3: {1},
+ }
+ )
+ )
self.assertEqual(ex.exception.data, {1: {2}, 2: {3}, 3: {1}})
- # not all elements involved in a cycle
+ # Not all elements involved in a cycle.
with self.assertRaises(CircularDependencyError) as ex:
- list(toposort({1: {2},
- 2: {3},
- 3: {1},
- 5: {4},
- 4: {6},
- }))
+ list(
+ toposort(
+ {
+ 1: {2},
+ 2: {3},
+ 3: {1},
+ 5: {4},
+ 4: {6},
+ }
+ )
+ )
self.assertEqual(ex.exception.data, {1: set([2]), 2: set([3]), 3:
set([1])})
def test_input_not_modified(self):
- data = {2: {11},
+ def get_data():
+ return {
+ 2: {11},
9: {11, 8},
10: {11, 3},
11: {7, 5},
- 8: {7, 3, 8}, # includes something self-referential
- }
- orig = data.copy()
+ 8: {7, 3, 8}, # Includes something self-referential.
+ }
+
+ data = get_data()
+ orig = get_data()
+ self.assertEqual(data, orig)
results = list(toposort(data))
self.assertEqual(data, orig)
def test_input_not_modified_when_cycle_error(self):
- data = {1: {2},
+ def get_data():
+ return {
+ 1: {2},
2: {1},
3: {4},
- }
- orig = data.copy()
+ }
+
+ data = get_data()
+ orig = get_data()
+ self.assertEqual(data, orig)
self.assertRaises(ValueError, list, toposort(data))
self.assertEqual(data, orig)
class TestCaseAll(unittest.TestCase):
def test_sort_flatten(self):
- data = {2: {11},
- 9: {11, 8},
- 10: {11, 3},
- 11: {7, 5},
- 8: {7, 3, 8}, # includes something self-referential
- }
+ data = {
+ 2: {11},
+ 9: {11, 8},
+ 10: {11, 3},
+ 11: {7, 5},
+ 8: {7, 3, 8}, # Includes something self-referential.
+ }
expected = [{3, 5, 7}, {8, 11}, {2, 9, 10}]
self.assertEqual(list(toposort(data)), expected)
- # now check the sorted results
+ # Now check the sorted results.
results = []
for item in expected:
results.extend(sorted(item))
self.assertEqual(toposort_flatten(data), results)
- # and the unsorted results. break the results up into groups to
compare them
+ # And the unsorted results. Break the results up into groups to
+ # compare them.
actual = toposort_flatten(data, False)
- results = [{i for i in actual[0:3]}, {i for i in actual[3:5]}, {i for
i in actual[5:8]}]
+ results = [
+ {i for i in actual[0:3]},
+ {i for i in actual[3:5]},
+ {i for i in actual[5:8]},
+ ]
self.assertEqual(results, expected)
@@ -184,18 +257,22 @@
def test_all(self):
import toposort
- # check that __all__ in the module contains everything that should be
- # public, and only those symbols
+ # Check that __all__ in the module contains everything that should be
+ # public, and only those symbols.
all = set(toposort.__all__)
- # check that things in __all__ only appear once
- self.assertEqual(len(all), len(toposort.__all__),
- 'some symbols appear more than once in __all__')
+ # Check that things in __all__ only appear once.
+ self.assertEqual(
+ len(all),
+ len(toposort.__all__),
+ "some symbols appear more than once in __all__",
+ )
- # get the list of public symbols
- found = set(name for name in dir(toposort) if not name.startswith('_'))
+ # Get the list of public symbols.
+ found = set(name for name in dir(toposort) if not name.startswith("_"))
- # make sure it matches __all__
+ # Make sure it matches __all__.
self.assertEqual(all, found)
+
unittest.main()
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/toposort.egg-info/PKG-INFO
new/toposort-1.7/toposort.egg-info/PKG-INFO
--- old/toposort-1.5/toposort.egg-info/PKG-INFO 2016-10-25 03:05:02.000000000
+0200
+++ new/toposort-1.7/toposort.egg-info/PKG-INFO 1970-01-01 01:00:00.000000000
+0100
@@ -1,185 +0,0 @@
-Metadata-Version: 1.1
-Name: toposort
-Version: 1.5
-Summary: Implements a topological sort algorithm.
-Home-page: https://bitbucket.org/ericvsmith/toposort
-Author: Eric V. Smith
-Author-email: e...@trueblade.com
-License: Apache License Version 2.0
-Description: ========
- 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.
-
- Change log
- ==========
-
- 1.5 2016-10-24 Eric V. Smith
- ----------------------------
-
- * When a circular dependency error is detected, raise a specific
- exception, CircularDependencyError, which is a subclass of
- ValueError. The 'data' attribute of the exception will contain the
- data involved in the circular dependency (issue #2). Thanks
- lilydjwg for the initial patch.
-
- * To make building wheels easier, always require setuptools in
- setup.py (issue #5).
-
- * Mark wheel as being universal, that is, supporting both Python 2.7
- and 3.x (issue #7).
-
- 1.4 2015-05-16 Eric V. Smith
- ----------------------------
-
- * Removed 'test' package, so it won't get installed by bdist_*. It's
still
- included in sdists.
-
- * No code changes.
-
- 1.3 2015-05-15 Eric V. Smith
- ----------------------------
-
- * Fixed change log date.
-
- * No code changes.
-
- 1.2 2015-05-15 Eric V. Smith
- ----------------------------
-
- * Changed RPM name to python3-toposort if running with python 3.
-
- * No code changes.
-
- 1.1 2014-07-24 Eric V. Smith
- ----------------------------
-
- * Release version 1.1. No code changes.
-
- * Add a README.txt entry on running the test suite.
-
- * Fix missing test/__init__.py in the sdist.
-
- 1.0 2014-03-14 Eric V. Smith
- ----------------------------
-
- * Release version 1.0. The API is stable.
-
- * Add MANIFEST.in to MANIFEST.in, so that it is created in the sdist
- (issue #1).
-
- 0.2 2014-02-11 Eric V. Smith
- ----------------------------
-
- * Modify setup.py to produce a RPM name of python-toposort for
bdist_rpm.
-
- 0.1 2014-02-10 Eric V. Smith
- ----------------------------
-
- * Initial release.
-
-Platform: UNKNOWN
-Classifier: Development Status :: 5 - Production/Stable
-Classifier: Intended Audience :: Developers
-Classifier: License :: OSI Approved :: Apache Software License
-Classifier: Topic :: Software Development :: Libraries :: Python Modules
-Classifier: Programming Language :: Python :: 2.7
-Classifier: Programming Language :: Python :: 3.3
-Classifier: Programming Language :: Python :: 3.4
-Classifier: Programming Language :: Python :: 3.5
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/toposort.egg-info/SOURCES.txt
new/toposort-1.7/toposort.egg-info/SOURCES.txt
--- old/toposort-1.5/toposort.egg-info/SOURCES.txt 2016-10-25
03:05:02.000000000 +0200
+++ new/toposort-1.7/toposort.egg-info/SOURCES.txt 1970-01-01
01:00:00.000000000 +0100
@@ -1,14 +0,0 @@
-CHANGES.txt
-LICENSE.txt
-MANIFEST.in
-NOTICE
-README.txt
-setup.cfg
-setup.py
-toposort.py
-test/__init__.py
-test/test_toposort.py
-toposort.egg-info/PKG-INFO
-toposort.egg-info/SOURCES.txt
-toposort.egg-info/dependency_links.txt
-toposort.egg-info/top_level.txt
\ No newline at end of file
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/toposort.egg-info/dependency_links.txt
new/toposort-1.7/toposort.egg-info/dependency_links.txt
--- old/toposort-1.5/toposort.egg-info/dependency_links.txt 2016-10-25
03:05:02.000000000 +0200
+++ new/toposort-1.7/toposort.egg-info/dependency_links.txt 1970-01-01
01:00:00.000000000 +0100
@@ -1 +0,0 @@
-
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/toposort.egg-info/top_level.txt
new/toposort-1.7/toposort.egg-info/top_level.txt
--- old/toposort-1.5/toposort.egg-info/top_level.txt 2016-10-25
03:05:02.000000000 +0200
+++ new/toposort-1.7/toposort.egg-info/top_level.txt 1970-01-01
01:00:00.000000000 +0100
@@ -1 +0,0 @@
-toposort
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/toposort-1.5/toposort.py new/toposort-1.7/toposort.py
--- old/toposort-1.5/toposort.py 2016-10-25 02:38:15.000000000 +0200
+++ new/toposort-1.7/toposort.py 1970-01-01 01:00:00.000000000 +0100
@@ -1,92 +0,0 @@
-#######################################################################
-# Implements a topological sort algorithm.
-#
-# Copyright 2014 True Blade Systems, Inc.
-#
-# Licensed under the Apache License, Version 2.0 (the "License");
-# you may not use this file except in compliance with the License.
-# You may obtain a copy of the License at
-#
-# http://www.apache.org/licenses/LICENSE-2.0
-#
-# Unless required by applicable law or agreed to in writing, software
-# distributed under the License is distributed on an "AS IS" BASIS,
-# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-# See the License for the specific language governing permissions and
-# limitations under the License.
-#
-# Notes:
-# Based on http://code.activestate.com/recipes/578272-topological-sort
-# with these major changes:
-# Added unittests.
-# Deleted doctests (maybe not the best idea in the world, but it cleans
-# up the docstring).
-# Moved functools import to the top of the file.
-# Changed assert to a ValueError.
-# Changed iter[items|keys] to [items|keys], for python 3
-# compatibility. I don't think it matters for python 2 these are
-# now lists instead of iterables.
-# Copy the input so as to leave it unmodified.
-# Renamed function from toposort2 to toposort.
-# Handle empty input.
-# Switch tests to use set literals.
-#
-########################################################################
-
-from functools import reduce as _reduce
-
-__all__ = ['toposort', 'toposort_flatten', 'CircularDependencyError']
-
-
-class CircularDependencyError(ValueError):
- def __init__(self, data):
- # Sort the data just to make the output consistent, for use in
- # error messages. That's convenient for doctests.
- s = 'Circular dependencies exist among these items: {{{}}}'.format(',
'.join('{!r}:{!r}'.format(key, value) for key, value in sorted(data.items())))
- super(CircularDependencyError, self).__init__(s)
- self.data = data
-
-
-def toposort(data):
- """Dependencies are expressed as a dictionary whose keys are items
-and whose values are a set of dependent items. Output is a list of
-sets in topological order. The first set consists of items with no
-dependences, each subsequent set consists of items that depend upon
-items in the preceeding sets.
-"""
-
- # Special case empty input.
- if len(data) == 0:
- return
-
- # Copy the input so as to leave it unmodified.
- data = data.copy()
-
- # Ignore self dependencies.
- for k, v in data.items():
- v.discard(k)
- # Find all items that don't depend on anything.
- extra_items_in_deps = _reduce(set.union, data.values()) - set(data.keys())
- # Add empty dependences where needed.
- data.update({item:set() for item in extra_items_in_deps})
- while True:
- ordered = set(item for item, dep in data.items() if len(dep) == 0)
- if not ordered:
- break
- yield ordered
- data = {item: (dep - ordered)
- for item, dep in data.items()
- if item not in ordered}
- if len(data) != 0:
- raise CircularDependencyError(data)
-
-
-def toposort_flatten(data, sort=True):
- """Returns a single list of dependencies. For any set returned by
-toposort(), those items are sorted and appended to the result (just to
-make the results deterministic)."""
-
- result = []
- for d in toposort(data):
- result.extend((sorted if sort else list)(d))
- return result
