ioftools / networkxMiCe / networkxmaster / 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 minimumvalued element.

52 
('insert', 3, 10 ** 100, True), 
53 
('insert', 4, 5, True), 
54 
('pop', (3, 10 ** 100)), 
55 
('pop', (1, 2.0)), 
56 
# Decreaseinsert should succeed.

57 
('insert', 4, 50, True), 
58 
('insert', 4, 60, False, True), 
59 
# Decreaseinsert 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 
# Nonvaluechanging 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 
# Increaseinsert 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 
# Increaseinsert should fail when disallowed.

81 
('insert', None, 2, False, False), 
82 
('min', (None, 0)), 
83 
# Failed increaseinsert 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) 