1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
"""
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()
|
