Go to the documentation of this file.00001 """
00002 toposort.py
00003 Sorts dictionary keys based on lists of dependencies.
00004 """
00005
00006 class MissingDependency(Exception):
00007 """Exception raised when a listed dependency is not in the dictionary."""
00008
00009 class Sorter(object):
00010 def __init__(self, dependencies):
00011 self.dependencies = dependencies
00012 self.visited = set()
00013 self.sorted = ()
00014
00015 def sort(self):
00016 for key in self.dependencies:
00017 self._visit(key)
00018 return self.sorted
00019
00020 def _visit(self, key):
00021 if key not in self.visited:
00022 self.visited.add(key)
00023 if not self.dependencies.has_key(key):
00024 raise MissingDependency(key)
00025 for depends in self.dependencies[key]:
00026 self._visit(depends)
00027 self.sorted += (key,)
00028
00029 def toposort(dependencies):
00030 """Returns a tuple of the dependencies dictionary keys sorted by entries
00031 in the dependency lists. Given circular dependencies, sort will impose
00032 an order. Raises MissingDependency if a key is not found.
00033 """
00034 s = Sorter(dependencies)
00035 return s.sort()