/usr/lib/python3/dist-packages/networkx/utils/tests/test_heaps.py is in python3-networkx 1.11-1ubuntu2.
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 | from nose.tools import *
import networkx as nx
from networkx.utils import *
class X(object):
def __eq__(self, other):
raise self is other
def __ne__(self, other):
raise self is not other
def __lt__(self, other):
raise TypeError('cannot compare')
def __le__(self, other):
raise TypeError('cannot compare')
def __ge__(self, other):
raise TypeError('cannot compare')
def __gt__(self, other):
raise TypeError('cannot compare')
def __hash__(self):
return hash(id(self))
x = X()
data = [# min should not invent an element.
('min', nx.NetworkXError),
# Popping an empty heap should fail.
('pop', nx.NetworkXError),
# Getting nonexisting elements should return None.
('get', 0, None),
('get', x, None),
('get', None, None),
# Inserting a new key should succeed.
('insert', x, 1, True),
('get', x, 1),
('min', (x, 1)),
# min should not pop the top element.
('min', (x, 1)),
# Inserting a new key of different type should succeed.
('insert', 1, -2.0, True),
# int and float values should interop.
('min', (1, -2.0)),
# pop removes minimum-valued element.
('insert', 3, -10 ** 100, True),
('insert', 4, 5, True),
('pop', (3, -10 ** 100)),
('pop', (1, -2.0)),
# Decrease-insert should succeed.
('insert', 4, -50, True),
('insert', 4, -60, False, True),
# Decrease-insert should not create duplicate keys.
('pop', (4, -60)),
('pop', (x, 1)),
# Popping all elements should empty the heap.
('min', nx.NetworkXError),
('pop', nx.NetworkXError),
# Non-value-changing insert should fail.
('insert', x, 0, True),
('insert', x, 0, False, False),
('min', (x, 0)),
('insert', x, 0, True, False),
('min', (x, 0)),
# Failed insert should not create duplicate keys.
('pop', (x, 0)),
('pop', nx.NetworkXError),
# Increase-insert should succeed when allowed.
('insert', None, 0, True),
('insert', 2, -1, True),
('min', (2, -1)),
('insert', 2, 1, True, False),
('min', (None, 0)),
# Increase-insert should fail when disallowed.
('insert', None, 2, False, False),
('min', (None, 0)),
# Failed increase-insert should not create duplicate keys.
('pop', (None, 0)),
('pop', (2, 1)),
('min', nx.NetworkXError),
('pop', nx.NetworkXError)]
def _test_heap_class(cls, *args, **kwargs):
heap = cls(*args, **kwargs)
# Basic behavioral test
for op in data:
if op[-1] is not nx.NetworkXError:
assert_equal(op[-1], getattr(heap, op[0])(*op[1:-1]))
else:
assert_raises(op[-1], getattr(heap, op[0]), *op[1:-1])
# Coverage test.
for i in range(99, -1, -1):
assert_true(heap.insert(i, i))
for i in range(50):
assert_equal(heap.pop(), (i, i))
for i in range(100):
assert_equal(heap.insert(i, i), i < 50)
for i in range(100):
assert_false(heap.insert(i, i + 1))
for i in range(50):
assert_equal(heap.pop(), (i, i))
for i in range(100):
assert_equal(heap.insert(i, i + 1), i < 50)
for i in range(49):
assert_equal(heap.pop(), (i, i + 1))
assert_equal(sorted([heap.pop(), heap.pop()]), [(49, 50), (50, 50)])
for i in range(51, 100):
assert_false(heap.insert(i, i + 1, True))
for i in range(51, 70):
assert_equal(heap.pop(), (i, i + 1))
for i in range(100):
assert_true(heap.insert(i, i))
for i in range(100):
assert_equal(heap.pop(), (i, i))
assert_raises(nx.NetworkXError, heap.pop)
def test_PairingHeap():
_test_heap_class(PairingHeap)
def test_BinaryHeap():
_test_heap_class(BinaryHeap)
|