Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/utils/heaps.py @ 1:56ad4e20f292 draft

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