dev/sparktestsupport/toposort.py

0001 #######################################################################
0002 # Implements a topological sort algorithm.
0003 #
0004 # Copyright 2014 True Blade Systems, Inc.
0005 #
0006 # Licensed under the Apache License, Version 2.0 (the "License");
0007 # you may not use this file except in compliance with the License.
0008 # You may obtain a copy of the License at
0009 #
0010 # http://www.apache.org/licenses/LICENSE-2.0
0011 #
0012 # Unless required by applicable law or agreed to in writing, software
0013 # distributed under the License is distributed on an "AS IS" BASIS,
0014 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0015 # See the License for the specific language governing permissions and
0016 # limitations under the License.
0017 #
0018 # Notes:
0019 #  Based on http://code.activestate.com/recipes/578272-topological-sort
0020 #   with these major changes:
0021 #    Added unittests.
0022 #    Deleted doctests (maybe not the best idea in the world, but it cleans
0023 #     up the docstring).
0024 #    Moved functools import to the top of the file.
0025 #    Changed assert to a ValueError.
0026 #    Changed iter[items|keys] to [items|keys], for python 3
0027 #     compatibility. I don't think it matters for python 2 these are
0028 #     now lists instead of iterables.
0029 #    Copy the input so as to leave it unmodified.
0030 #    Renamed function from toposort2 to toposort.
0031 #    Handle empty input.
0032 #    Switch tests to use set literals.
0033 #
0034 ########################################################################
0035
0036 from functools import reduce as _reduce
0037
0038
0039 __all__ = ['toposort', 'toposort_flatten']
0040
0041
0042 def toposort(data):
0043     """Dependencies are expressed as a dictionary whose keys are items
0044 and whose values are a set of dependent items. Output is a list of
0045 sets in topological order. The first set consists of items with no
0046 dependencies, each subsequent set consists of items that depend upon
0047 items in the preceding sets.
0048 """
0049
0050     # Special case empty input.
0051     if len(data) == 0:
0052         return
0053
0054     # Copy the input so as to leave it unmodified.
0055     data = data.copy()
0056
0057     # Ignore self dependencies.
0058     for k, v in data.items():
0059         v.discard(k)
0060     # Find all items that don't depend on anything.
0061     extra_items_in_deps = _reduce(set.union, data.values()) - set(data.keys())
0062     # Add empty dependencies where needed.
0063     data.update({item: set() for item in extra_items_in_deps})
0064     while True:
0065         ordered = set(item for item, dep in data.items() if len(dep) == 0)
0066         if not ordered:
0067             break
0068         yield ordered
0069         data = {item: (dep - ordered)
0070                 for item, dep in data.items()
0071                 if item not in ordered}
0072     if len(data) != 0:
0073         raise ValueError('Cyclic dependencies exist among these items: {}'.format(
0074             ', '.join(repr(x) for x in data.items())))
0075
0076
0077 def toposort_flatten(data, sort=True):
0078     """Returns a single list of dependencies. For any set returned by
0079 toposort(), those items are sorted and appended to the result (just to
0080 make the results deterministic)."""
0081
0082     result = []
0083     for d in toposort(data):
0084         result.extend((sorted if sort else list)(d))
0085     return result