94 lines
2.3 KiB
Python
94 lines
2.3 KiB
Python
import random
|
|
from astar import astar, dijkstra
|
|
|
|
|
|
def test_simple():
|
|
g = {'s': {'a': 1, 'b': 4}, 'a': {'g': 2}, 'b': {'g': 1}, 'g': {}}
|
|
d, p = astar(g, 's', 'g')
|
|
assert d == 3 and p == ['s', 'a', 'g']
|
|
|
|
|
|
def test_no_path():
|
|
g = {'s': {'a': 1}, 'a': {}, 'g': {}}
|
|
d, p = astar(g, 's', 'g')
|
|
assert d == float('inf') and p == []
|
|
|
|
|
|
def test_start_goal_same():
|
|
g = {'s': {}}
|
|
d, p = astar(g, 's', 's')
|
|
assert d == 0 and p == ['s']
|
|
|
|
|
|
def test_invalid_node():
|
|
g = {'s': {}}
|
|
try:
|
|
astar(g, 'x', 's')
|
|
except ValueError:
|
|
pass
|
|
else:
|
|
raise AssertionError("expected ValueError")
|
|
|
|
|
|
def test_negative_edge():
|
|
g = {'s': {'a': -1}, 'a': {}}
|
|
try:
|
|
astar(g, 's', 'a')
|
|
except ValueError:
|
|
pass
|
|
else:
|
|
raise AssertionError("expected ValueError")
|
|
|
|
|
|
def test_heuristic_admissible():
|
|
# grid 3x3, h = manhattan distance
|
|
nodes = [(r, c) for r in range(3) for c in range(3)]
|
|
g = {n: {} for n in nodes}
|
|
for r, c in nodes:
|
|
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
|
|
nr, nc = r + dr, c + dc
|
|
if 0 <= nr < 3 and 0 <= nc < 3:
|
|
g[(r, c)][(nr, nc)] = 1.0
|
|
|
|
def manhattan(n):
|
|
return abs(n[0] - 2) + abs(n[1] - 2)
|
|
|
|
d, p = astar(g, (0, 0), (2, 2), h=manhattan)
|
|
assert d == 4
|
|
|
|
|
|
def test_matches_dijkstra_random():
|
|
random.seed(42)
|
|
for _ in range(200):
|
|
n = random.randint(2, 8)
|
|
nodes = list(range(n))
|
|
g = {i: {} for i in nodes}
|
|
for i in nodes:
|
|
for j in nodes:
|
|
if i != j and random.random() < 0.35:
|
|
g[i][j] = random.randint(1, 9)
|
|
s, t = random.choice(nodes), random.choice(nodes)
|
|
# ensure both present (they are)
|
|
da, pa = astar(g, s, t)
|
|
dd, pd = dijkstra(g, s, t)
|
|
assert da == dd, (da, dd)
|
|
# path validity
|
|
if da != float('inf'):
|
|
# verify path cost
|
|
cost = 0.0
|
|
for a, b in zip(pa, pa[1:]):
|
|
cost += g[a][b]
|
|
assert abs(cost - da) < 1e-9
|
|
assert pa[0] == s and pa[-1] == t
|
|
|
|
|
|
if __name__ == '__main__':
|
|
test_simple()
|
|
test_no_path()
|
|
test_start_goal_same()
|
|
test_invalid_node()
|
|
test_negative_edge()
|
|
test_heuristic_admissible()
|
|
test_matches_dijkstra_random()
|
|
print("ALL TESTS PASSED")
|