Sha256: 52b968f9f3dca38047990b45e9ddd6fbae37a7e98d889e5d663afd10442e77d9
Contents?: true
Size: 1.06 KB
Versions: 12
Compression:
Stored size: 1.06 KB
Contents
"""
toposort.py
Sorts dictionary keys based on lists of dependencies.
"""
class MissingDependency(Exception):
"""Exception raised when a listed dependency is not in the dictionary."""
class Sorter(object):
def __init__(self, dependencies):
self.dependencies = dependencies
self.visited = set()
self.sorted = ()
def sort(self):
for key in self.dependencies:
self._visit(key)
return self.sorted
def _visit(self, key):
if key not in self.visited:
self.visited.add(key)
if not self.dependencies.has_key(key):
raise MissingDependency(key)
for depends in self.dependencies[key]:
self._visit(depends)
self.sorted += (key,)
def toposort(dependencies):
"""Returns a tuple of the dependencies dictionary keys sorted by entries
in the dependency lists. Given circular dependencies, sort will impose
an order. Raises MissingDependency if a key is not found.
"""
s = Sorter(dependencies)
return s.sort()
Version data entries
12 entries across 12 versions & 2 rubygems