toposort.py
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()


websocket_gui
Author(s): Benoit Lescot and Stéphane Magnenat
autogenerated on Sat Dec 28 2013 17:46:48