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