1 """
2 Some fundamental algorithms not found in the standard library.
3 """
4
5
6
7
8
9
10
11 import itertools
12
13
15 """is a graph that is indexed by both incoming and outgoing edges.
16
17 The constructor argument edges is an iterable of (from, to)-tuples,
18 where both from and to must be hashable.
19
20 The class keeps a set rootNodes of "root nodes" (i.e. those with
21 no incoming edges).
22
23 To find leaf nodes, you'd have to compute allNodes-set(outgoingIndex).
24
25 You may access allNodes, rootNodes, incomingIndex, and outgoingIndex
26 reading, but any external change to them will wreak havoc.
27 """
29 self.allNodes = set()
30 self.rootNodes = self.allNodes.copy()
31 self.incomingIndex, self.outgoingIndex = {}, {}
32 for comeFrom, goTo in edges:
33 self.addEdge(comeFrom, goTo)
34
36 return not not self.incomingIndex
37
39 self.incomingIndex.setdefault(goTo, set()).add(comeFrom)
40 self.outgoingIndex.setdefault(comeFrom, set()).add(goTo)
41 self.allNodes.add(goTo)
42 self.allNodes.add(comeFrom)
43 if comeFrom not in self.incomingIndex:
44 self.rootNodes.add(comeFrom)
45 self.rootNodes.discard(goTo)
46
48 if (comeFrom not in self.outgoingIndex or
49 goTo not in self.outgoingIndex[comeFrom]):
50 raise KeyError("No edge %s->%s"%(comeFrom, goTo))
51 self.outgoingIndex[comeFrom].remove(goTo)
52 self.incomingIndex[goTo].remove(comeFrom)
53 if not self.outgoingIndex[comeFrom]:
54 del self.outgoingIndex[comeFrom]
55 if comeFrom not in self.incomingIndex:
56 self.allNodes.remove(comeFrom)
57 self.rootNodes.discard(comeFrom)
58 if not self.incomingIndex[goTo]:
59 del self.incomingIndex[goTo]
60 self.rootNodes.add(goTo)
61 if goTo not in self.outgoingIndex:
62 self.allNodes.remove(goTo)
63 self.rootNodes.discard(goTo)
64
66 """returns a random edge.
67
68 It raises an IndexError if the graph is empty.
69 """
70 comeFrom = self.incomingIndex.iterkeys().next()
71 goTo = self.incomingIndex[comeFrom].pop()
72 self.incomingIndex[comeFrom].add(goTo)
73 return comeFrom, goTo
74
76 """returns an arbitrary element of rootNodes.
77
78 This will raise a KeyError if no root nodes are left.
79 """
80 el = self.rootNodes.pop()
81 self.rootNodes.add(el)
82 return el
83
84
86 """returns a list with the nodes in the graph edges sorted topologically.
87
88 edges is a sequence of (from, to)-tuples, where both from and to must
89 be hashable.
90
91 A ValueError is raised if the graph is not acyclic.
92 """
93 res, emptySet = [], frozenset()
94 graph = IndexedGraph(edges)
95 while graph.rootNodes:
96 comeFrom = graph.getSomeRootNode()
97 res.append(comeFrom)
98 outgoingFromCur = graph.outgoingIndex.get(comeFrom, emptySet).copy()
99 for goTo in outgoingFromCur:
100 graph.removeEdge(comeFrom, goTo)
101 if goTo not in graph.allNodes:
102 res.append(goTo)
103 if graph:
104 raise ValueError("Graph not acyclic, cycle: %s->%s"%graph.getEdge())
105 return res
106
107
109 """is a helper class for DeferringDict.
110 """
111 - def __init__(self, callable, args=(), kwargs={}):
112 self.callable, self.args, self.kwargs = callable, args, kwargs
113
115 return self.callable(*self.args, **self.kwargs)
116
117
119 """is a dictionary that stores tuples of a callable and its
120 arguments and will, on the first access, do the calls.
121
122 This is used below to defer the construction of instances in the class
123 resolver to when they are actually used. This is important with interfaces,
124 since they usually need the entire system up before they can sensibly
125 be built.
126 """
132
134 val = dict.__getitem__(self, key)
135 if isinstance(val, _Deferred):
136 val = val.actualize()
137 dict.__setitem__(self, key, val)
138 return val
139
141 for key in self:
142 yield key, self[key]
143
144
146 """returns the length of the common prefix of the sequences t1, t2.
147 """
148 try:
149 for prefixLength in itertools.count():
150 if t1[prefixLength]!=t2[prefixLength]:
151 return prefixLength
152 except IndexError:
153 return prefixLength
154
155
156 -def chunk(items, getChunkKey, getKeyKey=lambda a: a[0]):
157 """returns items in a chunked form.
158
159 getChunkKey(item)->chunk key is a function returning the chunk title,
160 getKeyKey(chunk)->sort key a function returning a sort key for the
161 chunks (default is just the chunk key, i.e., chunk[0]
162
163 The chunked form is a sequence of pairs of a chunk key and a sequence
164 of items belonging to that chunk.
165
166 The internal order within each chunk is not disturbed, so you should sort
167 items as desired before passing things in.
168
169 This is supposed to work like this:
170
171 >>> chunk(["abakus", "Analysis", "knopf", "Kasper", "kohl"],
172 ... lambda item: item[0].lower())
173 [('a', ['abakus', 'Analysis']), ('k', ['knopf', 'Kasper', 'kohl'])]
174 """
175 chunks = {}
176 for item in items:
177 chunkKey = getChunkKey(item)
178 chunks.setdefault(chunkKey, []).append(item)
179 return sorted(chunks.items(), key=getKeyKey)
180
181
184
185
187 """returns a list of the uniqe items in seq as they appear in seq.
188
189 Execept for order and return type, this is essentially like set(seq).
190 """
191 seenItems, result = set(), []
192 for item in seq:
193 if item not in seenItems:
194 result.append(item)
195 seenItems.add(item)
196 return result
197
198
202
203 if __name__=="__main__":
204 _test()
205