Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / utils / heaps.py @ 5cef0f13

History | View | Annotate | Download (10.9 KB)

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