aboutsummaryrefslogtreecommitdiff
path: root/.venv/lib/python3.12/site-packages/networkx/utils/tests/test_heaps.py
diff options
context:
space:
mode:
authorS. Solomon Darnell2025-03-28 21:52:21 -0500
committerS. Solomon Darnell2025-03-28 21:52:21 -0500
commit4a52a71956a8d46fcb7294ac71734504bb09bcc2 (patch)
treeee3dc5af3b6313e921cd920906356f5d4febc4ed /.venv/lib/python3.12/site-packages/networkx/utils/tests/test_heaps.py
parentcc961e04ba734dd72309fb548a2f97d67d578813 (diff)
downloadgn-ai-master.tar.gz
two version of R2R are hereHEADmaster
Diffstat (limited to '.venv/lib/python3.12/site-packages/networkx/utils/tests/test_heaps.py')
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/utils/tests/test_heaps.py131
1 files changed, 131 insertions, 0 deletions
diff --git a/.venv/lib/python3.12/site-packages/networkx/utils/tests/test_heaps.py b/.venv/lib/python3.12/site-packages/networkx/utils/tests/test_heaps.py
new file mode 100644
index 00000000..5ea38716
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/utils/tests/test_heaps.py
@@ -0,0 +1,131 @@
+import pytest
+
+import networkx as nx
+from networkx.utils import BinaryHeap, PairingHeap
+
+
+class X:
+ 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 op[-1] == getattr(heap, op[0])(*op[1:-1])
+ else:
+ pytest.raises(op[-1], getattr(heap, op[0]), *op[1:-1])
+ # Coverage test.
+ for i in range(99, -1, -1):
+ assert heap.insert(i, i)
+ for i in range(50):
+ assert heap.pop() == (i, i)
+ for i in range(100):
+ assert heap.insert(i, i) == (i < 50)
+ for i in range(100):
+ assert not heap.insert(i, i + 1)
+ for i in range(50):
+ assert heap.pop() == (i, i)
+ for i in range(100):
+ assert heap.insert(i, i + 1) == (i < 50)
+ for i in range(49):
+ assert heap.pop() == (i, i + 1)
+ assert sorted([heap.pop(), heap.pop()]) == [(49, 50), (50, 50)]
+ for i in range(51, 100):
+ assert not heap.insert(i, i + 1, True)
+ for i in range(51, 70):
+ assert heap.pop() == (i, i + 1)
+ for i in range(100):
+ assert heap.insert(i, i)
+ for i in range(100):
+ assert heap.pop() == (i, i)
+ pytest.raises(nx.NetworkXError, heap.pop)
+
+
+def test_PairingHeap():
+ _test_heap_class(PairingHeap)
+
+
+def test_BinaryHeap():
+ _test_heap_class(BinaryHeap)