Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/utils/heaps.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Min-heaps. | |
3 """ | |
4 | |
5 from heapq import heappop, heappush | |
6 from itertools import count | |
7 import networkx as nx | |
8 | |
9 __all__ = ["MinHeap", "PairingHeap", "BinaryHeap"] | |
10 | |
11 | |
12 class MinHeap: | |
13 """Base class for min-heaps. | |
14 | |
15 A MinHeap stores a collection of key-value pairs ordered by their values. | |
16 It supports querying the minimum pair, inserting a new pair, decreasing the | |
17 value in an existing pair and deleting the minimum pair. | |
18 """ | |
19 | |
20 class _Item: | |
21 """Used by subclassess to represent a key-value pair. | |
22 """ | |
23 | |
24 __slots__ = ("key", "value") | |
25 | |
26 def __init__(self, key, value): | |
27 self.key = key | |
28 self.value = value | |
29 | |
30 def __repr__(self): | |
31 return repr((self.key, self.value)) | |
32 | |
33 def __init__(self): | |
34 """Initialize a new min-heap. | |
35 """ | |
36 self._dict = {} | |
37 | |
38 def min(self): | |
39 """Query the minimum key-value pair. | |
40 | |
41 Returns | |
42 ------- | |
43 key, value : tuple | |
44 The key-value pair with the minimum value in the heap. | |
45 | |
46 Raises | |
47 ------ | |
48 NetworkXError | |
49 If the heap is empty. | |
50 """ | |
51 raise NotImplementedError | |
52 | |
53 def pop(self): | |
54 """Delete the minimum pair in the heap. | |
55 | |
56 Returns | |
57 ------- | |
58 key, value : tuple | |
59 The key-value pair with the minimum value in the heap. | |
60 | |
61 Raises | |
62 ------ | |
63 NetworkXError | |
64 If the heap is empty. | |
65 """ | |
66 raise NotImplementedError | |
67 | |
68 def get(self, key, default=None): | |
69 """Returns the value associated with a key. | |
70 | |
71 Parameters | |
72 ---------- | |
73 key : hashable object | |
74 The key to be looked up. | |
75 | |
76 default : object | |
77 Default value to return if the key is not present in the heap. | |
78 Default value: None. | |
79 | |
80 Returns | |
81 ------- | |
82 value : object. | |
83 The value associated with the key. | |
84 """ | |
85 raise NotImplementedError | |
86 | |
87 def insert(self, key, value, allow_increase=False): | |
88 """Insert a new key-value pair or modify the value in an existing | |
89 pair. | |
90 | |
91 Parameters | |
92 ---------- | |
93 key : hashable object | |
94 The key. | |
95 | |
96 value : object comparable with existing values. | |
97 The value. | |
98 | |
99 allow_increase : bool | |
100 Whether the value is allowed to increase. If False, attempts to | |
101 increase an existing value have no effect. Default value: False. | |
102 | |
103 Returns | |
104 ------- | |
105 decreased : bool | |
106 True if a pair is inserted or the existing value is decreased. | |
107 """ | |
108 raise NotImplementedError | |
109 | |
110 def __nonzero__(self): | |
111 """Returns whether the heap if empty. | |
112 """ | |
113 return bool(self._dict) | |
114 | |
115 def __bool__(self): | |
116 """Returns whether the heap if empty. | |
117 """ | |
118 return bool(self._dict) | |
119 | |
120 def __len__(self): | |
121 """Returns the number of key-value pairs in the heap. | |
122 """ | |
123 return len(self._dict) | |
124 | |
125 def __contains__(self, key): | |
126 """Returns whether a key exists in the heap. | |
127 | |
128 Parameters | |
129 ---------- | |
130 key : any hashable object. | |
131 The key to be looked up. | |
132 """ | |
133 return key in self._dict | |
134 | |
135 | |
136 def _inherit_doc(cls): | |
137 """Decorator for inheriting docstrings from base classes. | |
138 """ | |
139 | |
140 def func(fn): | |
141 fn.__doc__ = cls.__dict__[fn.__name__].__doc__ | |
142 return fn | |
143 | |
144 return func | |
145 | |
146 | |
147 class PairingHeap(MinHeap): | |
148 """A pairing heap. | |
149 """ | |
150 | |
151 class _Node(MinHeap._Item): | |
152 """A node in a pairing heap. | |
153 | |
154 A tree in a pairing heap is stored using the left-child, right-sibling | |
155 representation. | |
156 """ | |
157 | |
158 __slots__ = ("left", "next", "prev", "parent") | |
159 | |
160 def __init__(self, key, value): | |
161 super(PairingHeap._Node, self).__init__(key, value) | |
162 # The leftmost child. | |
163 self.left = None | |
164 # The next sibling. | |
165 self.next = None | |
166 # The previous sibling. | |
167 self.prev = None | |
168 # The parent. | |
169 self.parent = None | |
170 | |
171 def __init__(self): | |
172 """Initialize a pairing heap. | |
173 """ | |
174 super().__init__() | |
175 self._root = None | |
176 | |
177 @_inherit_doc(MinHeap) | |
178 def min(self): | |
179 if self._root is None: | |
180 raise nx.NetworkXError("heap is empty.") | |
181 return (self._root.key, self._root.value) | |
182 | |
183 @_inherit_doc(MinHeap) | |
184 def pop(self): | |
185 if self._root is None: | |
186 raise nx.NetworkXError("heap is empty.") | |
187 min_node = self._root | |
188 self._root = self._merge_children(self._root) | |
189 del self._dict[min_node.key] | |
190 return (min_node.key, min_node.value) | |
191 | |
192 @_inherit_doc(MinHeap) | |
193 def get(self, key, default=None): | |
194 node = self._dict.get(key) | |
195 return node.value if node is not None else default | |
196 | |
197 @_inherit_doc(MinHeap) | |
198 def insert(self, key, value, allow_increase=False): | |
199 node = self._dict.get(key) | |
200 root = self._root | |
201 if node is not None: | |
202 if value < node.value: | |
203 node.value = value | |
204 if node is not root and value < node.parent.value: | |
205 self._cut(node) | |
206 self._root = self._link(root, node) | |
207 return True | |
208 elif allow_increase and value > node.value: | |
209 node.value = value | |
210 child = self._merge_children(node) | |
211 # Nonstandard step: Link the merged subtree with the root. See | |
212 # below for the standard step. | |
213 if child is not None: | |
214 self._root = self._link(self._root, child) | |
215 # Standard step: Perform a decrease followed by a pop as if the | |
216 # value were the smallest in the heap. Then insert the new | |
217 # value into the heap. | |
218 # if node is not root: | |
219 # self._cut(node) | |
220 # if child is not None: | |
221 # root = self._link(root, child) | |
222 # self._root = self._link(root, node) | |
223 # else: | |
224 # self._root = (self._link(node, child) | |
225 # if child is not None else node) | |
226 return False | |
227 else: | |
228 # Insert a new key. | |
229 node = self._Node(key, value) | |
230 self._dict[key] = node | |
231 self._root = self._link(root, node) if root is not None else node | |
232 return True | |
233 | |
234 def _link(self, root, other): | |
235 """Link two nodes, making the one with the smaller value the parent of | |
236 the other. | |
237 """ | |
238 if other.value < root.value: | |
239 root, other = other, root | |
240 next = root.left | |
241 other.next = next | |
242 if next is not None: | |
243 next.prev = other | |
244 other.prev = None | |
245 root.left = other | |
246 other.parent = root | |
247 return root | |
248 | |
249 def _merge_children(self, root): | |
250 """Merge the subtrees of the root using the standard two-pass method. | |
251 The resulting subtree is detached from the root. | |
252 """ | |
253 node = root.left | |
254 root.left = None | |
255 if node is not None: | |
256 link = self._link | |
257 # Pass 1: Merge pairs of consecutive subtrees from left to right. | |
258 # At the end of the pass, only the prev pointers of the resulting | |
259 # subtrees have meaningful values. The other pointers will be fixed | |
260 # in pass 2. | |
261 prev = None | |
262 while True: | |
263 next = node.next | |
264 if next is None: | |
265 node.prev = prev | |
266 break | |
267 next_next = next.next | |
268 node = link(node, next) | |
269 node.prev = prev | |
270 prev = node | |
271 if next_next is None: | |
272 break | |
273 node = next_next | |
274 # Pass 2: Successively merge the subtrees produced by pass 1 from | |
275 # right to left with the rightmost one. | |
276 prev = node.prev | |
277 while prev is not None: | |
278 prev_prev = prev.prev | |
279 node = link(prev, node) | |
280 prev = prev_prev | |
281 # Now node can become the new root. Its has no parent nor siblings. | |
282 node.prev = None | |
283 node.next = None | |
284 node.parent = None | |
285 return node | |
286 | |
287 def _cut(self, node): | |
288 """Cut a node from its parent. | |
289 """ | |
290 prev = node.prev | |
291 next = node.next | |
292 if prev is not None: | |
293 prev.next = next | |
294 else: | |
295 node.parent.left = next | |
296 node.prev = None | |
297 if next is not None: | |
298 next.prev = prev | |
299 node.next = None | |
300 node.parent = None | |
301 | |
302 | |
303 class BinaryHeap(MinHeap): | |
304 """A binary heap. | |
305 """ | |
306 | |
307 def __init__(self): | |
308 """Initialize a binary heap. | |
309 """ | |
310 super().__init__() | |
311 self._heap = [] | |
312 self._count = count() | |
313 | |
314 @_inherit_doc(MinHeap) | |
315 def min(self): | |
316 dict = self._dict | |
317 if not dict: | |
318 raise nx.NetworkXError("heap is empty") | |
319 heap = self._heap | |
320 pop = heappop | |
321 # Repeatedly remove stale key-value pairs until a up-to-date one is | |
322 # met. | |
323 while True: | |
324 value, _, key = heap[0] | |
325 if key in dict and value == dict[key]: | |
326 break | |
327 pop(heap) | |
328 return (key, value) | |
329 | |
330 @_inherit_doc(MinHeap) | |
331 def pop(self): | |
332 dict = self._dict | |
333 if not dict: | |
334 raise nx.NetworkXError("heap is empty") | |
335 heap = self._heap | |
336 pop = heappop | |
337 # Repeatedly remove stale key-value pairs until a up-to-date one is | |
338 # met. | |
339 while True: | |
340 value, _, key = heap[0] | |
341 pop(heap) | |
342 if key in dict and value == dict[key]: | |
343 break | |
344 del dict[key] | |
345 return (key, value) | |
346 | |
347 @_inherit_doc(MinHeap) | |
348 def get(self, key, default=None): | |
349 return self._dict.get(key, default) | |
350 | |
351 @_inherit_doc(MinHeap) | |
352 def insert(self, key, value, allow_increase=False): | |
353 dict = self._dict | |
354 if key in dict: | |
355 old_value = dict[key] | |
356 if value < old_value or (allow_increase and value > old_value): | |
357 # Since there is no way to efficiently obtain the location of a | |
358 # key-value pair in the heap, insert a new pair even if ones | |
359 # with the same key may already be present. Deem the old ones | |
360 # as stale and skip them when the minimum pair is queried. | |
361 dict[key] = value | |
362 heappush(self._heap, (value, next(self._count), key)) | |
363 return value < old_value | |
364 return False | |
365 else: | |
366 dict[key] = value | |
367 heappush(self._heap, (value, next(self._count), key)) | |
368 return True |