Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (3.68 KB)

1
from nose.tools import *
2
import networkx as nx
3
from networkx.utils import *
4

    
5

    
6
class X(object):
7

    
8
    def __eq__(self, other):
9
        raise self is other
10

    
11
    def __ne__(self, other):
12
        raise self is not other
13

    
14
    def __lt__(self, other):
15
        raise TypeError('cannot compare')
16

    
17
    def __le__(self, other):
18
        raise TypeError('cannot compare')
19

    
20
    def __ge__(self, other):
21
        raise TypeError('cannot compare')
22

    
23
    def __gt__(self, other):
24
        raise TypeError('cannot compare')
25

    
26
    def __hash__(self):
27
        return hash(id(self))
28

    
29

    
30
x = X()
31

    
32

    
33
data = [  # min should not invent an element.
34
    ('min', nx.NetworkXError),
35
    # Popping an empty heap should fail.
36
    ('pop', nx.NetworkXError),
37
    # Getting nonexisting elements should return None.
38
    ('get', 0, None),
39
    ('get', x, None),
40
    ('get', None, None),
41
    # Inserting a new key should succeed.
42
    ('insert', x, 1, True),
43
    ('get', x, 1),
44
    ('min', (x, 1)),
45
    # min should not pop the top element.
46
    ('min', (x, 1)),
47
    # Inserting a new key of different type should succeed.
48
    ('insert', 1, -2.0, True),
49
    # int and float values should interop.
50
    ('min', (1, -2.0)),
51
    # pop removes minimum-valued element.
52
    ('insert', 3, -10 ** 100, True),
53
    ('insert', 4, 5, True),
54
    ('pop', (3, -10 ** 100)),
55
    ('pop', (1, -2.0)),
56
    # Decrease-insert should succeed.
57
    ('insert', 4, -50, True),
58
    ('insert', 4, -60, False, True),
59
    # Decrease-insert should not create duplicate keys.
60
    ('pop', (4, -60)),
61
    ('pop', (x, 1)),
62
    # Popping all elements should empty the heap.
63
    ('min', nx.NetworkXError),
64
    ('pop', nx.NetworkXError),
65
    # Non-value-changing insert should fail.
66
    ('insert', x, 0, True),
67
    ('insert', x, 0, False, False),
68
    ('min', (x, 0)),
69
    ('insert', x, 0, True, False),
70
    ('min', (x, 0)),
71
    # Failed insert should not create duplicate keys.
72
    ('pop', (x, 0)),
73
    ('pop', nx.NetworkXError),
74
    # Increase-insert should succeed when allowed.
75
    ('insert', None, 0, True),
76
    ('insert', 2, -1, True),
77
    ('min', (2, -1)),
78
    ('insert', 2, 1, True, False),
79
    ('min', (None, 0)),
80
    # Increase-insert should fail when disallowed.
81
    ('insert', None, 2, False, False),
82
    ('min', (None, 0)),
83
    # Failed increase-insert should not create duplicate keys.
84
    ('pop', (None, 0)),
85
    ('pop', (2, 1)),
86
    ('min', nx.NetworkXError),
87
    ('pop', nx.NetworkXError)]
88

    
89

    
90
def _test_heap_class(cls, *args, **kwargs):
91
    heap = cls(*args, **kwargs)
92
    # Basic behavioral test
93
    for op in data:
94
        if op[-1] is not nx.NetworkXError:
95
            assert_equal(op[-1], getattr(heap, op[0])(*op[1:-1]))
96
        else:
97
            assert_raises(op[-1], getattr(heap, op[0]), *op[1:-1])
98
    # Coverage test.
99
    for i in range(99, -1, -1):
100
        assert_true(heap.insert(i, i))
101
    for i in range(50):
102
        assert_equal(heap.pop(), (i, i))
103
    for i in range(100):
104
        assert_equal(heap.insert(i, i), i < 50)
105
    for i in range(100):
106
        assert_false(heap.insert(i, i + 1))
107
    for i in range(50):
108
        assert_equal(heap.pop(), (i, i))
109
    for i in range(100):
110
        assert_equal(heap.insert(i, i + 1), i < 50)
111
    for i in range(49):
112
        assert_equal(heap.pop(), (i, i + 1))
113
    assert_equal(sorted([heap.pop(), heap.pop()]), [(49, 50), (50, 50)])
114
    for i in range(51, 100):
115
        assert_false(heap.insert(i, i + 1, True))
116
    for i in range(51, 70):
117
        assert_equal(heap.pop(), (i, i + 1))
118
    for i in range(100):
119
        assert_true(heap.insert(i, i))
120
    for i in range(100):
121
        assert_equal(heap.pop(), (i, i))
122
    assert_raises(nx.NetworkXError, heap.pop)
123

    
124

    
125
def test_PairingHeap():
126
    _test_heap_class(PairingHeap)
127

    
128

    
129
def test_BinaryHeap():
130
    _test_heap_class(BinaryHeap)