Spaces:
Sleeping
Sleeping
| """Tests for search algorithms (BFS, DFS, UCS, A*, Greedy, IDS).""" | |
| import pytest | |
| from app.algorithms.bfs import bfs_search | |
| from app.algorithms.dfs import dfs_search | |
| from app.algorithms.ucs import ucs_search | |
| from app.algorithms.astar import astar_search | |
| from app.algorithms.greedy import greedy_search | |
| from app.algorithms.ids import ids_search | |
| from app.heuristics import manhattan_heuristic, euclidean_heuristic | |
| from app.core.delivery_search import DeliverySearch | |
| from app.models.grid import Grid | |
| class TestBFS: | |
| """Tests for Breadth-First Search.""" | |
| def test_bfs_finds_path(self, simple_grid): | |
| """Test BFS finds a path.""" | |
| search = DeliverySearch(simple_grid, (0, 0), (2, 2), []) | |
| result, steps = bfs_search(search, visualize=False) | |
| assert result.plan != "" | |
| assert result.cost < float("inf") | |
| assert len(result.path) > 0 | |
| assert result.path[0] == (0, 0) | |
| assert result.path[-1] == (2, 2) | |
| def test_bfs_shortest_path(self, simple_grid): | |
| """Test BFS finds shortest path by steps.""" | |
| search = DeliverySearch(simple_grid, (0, 0), (2, 2), []) | |
| result, _ = bfs_search(search, visualize=False) | |
| # BFS should find path with minimum steps | |
| # From (0,0) to (2,2) needs at least 4 steps | |
| assert len(result.path) == 5 # 5 nodes including start and end | |
| def test_bfs_no_path(self): | |
| """Test BFS when no path exists.""" | |
| grid = Grid(width=3, height=3) | |
| # Create disconnected grid - only add vertical segment | |
| grid.add_segment((0, 0), (0, 1), 1) | |
| search = DeliverySearch(grid, (0, 0), (2, 2), []) | |
| result, _ = bfs_search(search, visualize=False) | |
| assert result.plan == "" | |
| assert result.cost == float("inf") | |
| assert len(result.path) == 0 | |
| def test_bfs_same_start_goal(self, simple_grid): | |
| """Test BFS when start equals goal.""" | |
| search = DeliverySearch(simple_grid, (1, 1), (1, 1), []) | |
| result, _ = bfs_search(search, visualize=False) | |
| assert result.cost == 0 | |
| assert len(result.path) == 1 | |
| assert result.path[0] == (1, 1) | |
| def test_bfs_visualization(self, simple_grid): | |
| """Test BFS with visualization enabled.""" | |
| search = DeliverySearch(simple_grid, (0, 0), (2, 2), []) | |
| result, steps = bfs_search(search, visualize=True) | |
| assert steps is not None | |
| assert len(steps) > 0 | |
| # First step should have start node | |
| assert steps[0].current_node == (0, 0) | |
| class TestDFS: | |
| """Tests for Depth-First Search.""" | |
| def test_dfs_finds_path(self, simple_grid): | |
| """Test DFS finds a path.""" | |
| search = DeliverySearch(simple_grid, (0, 0), (2, 2), []) | |
| result, steps = dfs_search(search, visualize=False) | |
| assert result.plan != "" | |
| assert result.cost < float("inf") | |
| assert len(result.path) > 0 | |
| assert result.path[0] == (0, 0) | |
| assert result.path[-1] == (2, 2) | |
| def test_dfs_no_path(self): | |
| """Test DFS when no path exists.""" | |
| grid = Grid(width=3, height=3) | |
| grid.add_segment((0, 0), (0, 1), 1) | |
| search = DeliverySearch(grid, (0, 0), (2, 2), []) | |
| result, _ = dfs_search(search, visualize=False) | |
| assert result.plan == "" | |
| assert result.cost == float("inf") | |
| def test_dfs_same_start_goal(self, simple_grid): | |
| """Test DFS when start equals goal.""" | |
| search = DeliverySearch(simple_grid, (1, 1), (1, 1), []) | |
| result, _ = dfs_search(search, visualize=False) | |
| assert result.cost == 0 | |
| assert len(result.path) == 1 | |
| class TestUCS: | |
| """Tests for Uniform Cost Search.""" | |
| def test_ucs_finds_optimal_path(self, grid_with_varied_traffic): | |
| """Test UCS finds optimal (minimum cost) path.""" | |
| search = DeliverySearch(grid_with_varied_traffic, (0, 0), (2, 2), []) | |
| result, _ = ucs_search(search, visualize=False) | |
| assert result.plan != "" | |
| assert result.cost < float("inf") | |
| def test_ucs_prefers_low_traffic(self, grid_with_varied_traffic): | |
| """Test UCS prefers lower traffic segments.""" | |
| search = DeliverySearch(grid_with_varied_traffic, (0, 0), (2, 2), []) | |
| ucs_result, _ = ucs_search(search, visualize=False) | |
| bfs_result, _ = bfs_search(search, visualize=False) | |
| # UCS should find equal or better cost than BFS | |
| assert ucs_result.cost <= bfs_result.cost | |
| def test_ucs_no_path(self): | |
| """Test UCS when no path exists.""" | |
| grid = Grid(width=3, height=3) | |
| grid.add_segment((0, 0), (0, 1), 1) | |
| search = DeliverySearch(grid, (0, 0), (2, 2), []) | |
| result, _ = ucs_search(search, visualize=False) | |
| assert result.cost == float("inf") | |
| def test_ucs_same_start_goal(self, simple_grid): | |
| """Test UCS when start equals goal.""" | |
| search = DeliverySearch(simple_grid, (1, 1), (1, 1), []) | |
| result, _ = ucs_search(search, visualize=False) | |
| assert result.cost == 0 | |
| class TestAStar: | |
| """Tests for A* Search.""" | |
| def test_astar_manhattan_finds_path(self, simple_grid): | |
| """Test A* with Manhattan heuristic finds a path.""" | |
| search = DeliverySearch(simple_grid, (0, 0), (2, 2), []) | |
| result, _ = astar_search(search, manhattan_heuristic, visualize=False) | |
| assert result.plan != "" | |
| assert result.cost < float("inf") | |
| assert result.path[0] == (0, 0) | |
| assert result.path[-1] == (2, 2) | |
| def test_astar_euclidean_finds_path(self, simple_grid): | |
| """Test A* with Euclidean heuristic finds a path.""" | |
| search = DeliverySearch(simple_grid, (0, 0), (2, 2), []) | |
| result, _ = astar_search(search, euclidean_heuristic, visualize=False) | |
| assert result.plan != "" | |
| assert result.cost < float("inf") | |
| def test_astar_optimal(self, grid_with_varied_traffic): | |
| """Test A* finds optimal path (same as UCS with admissible heuristic).""" | |
| search = DeliverySearch(grid_with_varied_traffic, (0, 0), (2, 2), []) | |
| astar_result, _ = astar_search(search, manhattan_heuristic, visualize=False) | |
| ucs_result, _ = ucs_search(search, visualize=False) | |
| # A* with admissible heuristic should find same cost as UCS | |
| assert astar_result.cost == ucs_result.cost | |
| def test_astar_fewer_nodes_than_ucs(self, larger_grid): | |
| """Test A* expands fewer nodes than UCS.""" | |
| search = DeliverySearch(larger_grid, (0, 0), (4, 4), []) | |
| astar_result, _ = astar_search(search, manhattan_heuristic, visualize=False) | |
| ucs_result, _ = ucs_search(search, visualize=False) | |
| # A* should expand fewer or equal nodes | |
| assert astar_result.nodes_expanded <= ucs_result.nodes_expanded | |
| def test_astar_no_path(self): | |
| """Test A* when no path exists.""" | |
| grid = Grid(width=3, height=3) | |
| grid.add_segment((0, 0), (0, 1), 1) | |
| search = DeliverySearch(grid, (0, 0), (2, 2), []) | |
| result, _ = astar_search(search, manhattan_heuristic, visualize=False) | |
| assert result.cost == float("inf") | |
| class TestGreedy: | |
| """Tests for Greedy Best-First Search.""" | |
| def test_greedy_manhattan_finds_path(self, simple_grid): | |
| """Test Greedy with Manhattan heuristic finds a path.""" | |
| search = DeliverySearch(simple_grid, (0, 0), (2, 2), []) | |
| result, _ = greedy_search(search, manhattan_heuristic, visualize=False) | |
| assert result.plan != "" | |
| assert result.cost < float("inf") | |
| def test_greedy_euclidean_finds_path(self, simple_grid): | |
| """Test Greedy with Euclidean heuristic finds a path.""" | |
| search = DeliverySearch(simple_grid, (0, 0), (2, 2), []) | |
| result, _ = greedy_search(search, euclidean_heuristic, visualize=False) | |
| assert result.plan != "" | |
| assert result.cost < float("inf") | |
| def test_greedy_fast_but_suboptimal(self, grid_with_varied_traffic): | |
| """Test Greedy is fast but may not find optimal path.""" | |
| search = DeliverySearch(grid_with_varied_traffic, (0, 0), (2, 2), []) | |
| greedy_result, _ = greedy_search(search, manhattan_heuristic, visualize=False) | |
| ucs_result, _ = ucs_search(search, visualize=False) | |
| # Greedy may find suboptimal path | |
| assert greedy_result.cost >= ucs_result.cost | |
| def test_greedy_no_path(self): | |
| """Test Greedy when no path exists.""" | |
| grid = Grid(width=3, height=3) | |
| grid.add_segment((0, 0), (0, 1), 1) | |
| search = DeliverySearch(grid, (0, 0), (2, 2), []) | |
| result, _ = greedy_search(search, manhattan_heuristic, visualize=False) | |
| assert result.cost == float("inf") | |
| class TestIDS: | |
| """Tests for Iterative Deepening Search.""" | |
| def test_ids_finds_path(self, simple_grid): | |
| """Test IDS finds a path.""" | |
| search = DeliverySearch(simple_grid, (0, 0), (2, 2), []) | |
| result, _ = ids_search(search, visualize=False) | |
| assert result.plan != "" | |
| assert result.cost < float("inf") | |
| assert result.path[0] == (0, 0) | |
| assert result.path[-1] == (2, 2) | |
| def test_ids_optimal_steps(self, simple_grid): | |
| """Test IDS finds path with optimal number of steps.""" | |
| search = DeliverySearch(simple_grid, (0, 0), (2, 2), []) | |
| ids_result, _ = ids_search(search, visualize=False) | |
| bfs_result, _ = bfs_search(search, visualize=False) | |
| # IDS should find same path length as BFS | |
| assert len(ids_result.path) == len(bfs_result.path) | |
| def test_ids_no_path(self): | |
| """Test IDS when no path exists.""" | |
| grid = Grid(width=3, height=3) | |
| grid.add_segment((0, 0), (0, 1), 1) | |
| search = DeliverySearch(grid, (0, 0), (2, 2), []) | |
| result, _ = ids_search(search, visualize=False) | |
| assert result.cost == float("inf") | |
| def test_ids_same_start_goal(self, simple_grid): | |
| """Test IDS when start equals goal.""" | |
| search = DeliverySearch(simple_grid, (1, 1), (1, 1), []) | |
| result, _ = ids_search(search, visualize=False) | |
| assert result.cost == 0 | |
| assert len(result.path) == 1 | |
| class TestAlgorithmComparison: | |
| """Tests comparing different algorithms.""" | |
| def test_all_algorithms_find_same_goal(self, simple_grid): | |
| """Test all algorithms reach the same goal.""" | |
| search = DeliverySearch(simple_grid, (0, 0), (2, 2), []) | |
| bfs_result, _ = bfs_search(search, visualize=False) | |
| dfs_result, _ = dfs_search(search, visualize=False) | |
| ucs_result, _ = ucs_search(search, visualize=False) | |
| astar_result, _ = astar_search(search, manhattan_heuristic, visualize=False) | |
| greedy_result, _ = greedy_search(search, manhattan_heuristic, visualize=False) | |
| ids_result, _ = ids_search(search, visualize=False) | |
| # All should find a path ending at goal | |
| assert bfs_result.path[-1] == (2, 2) | |
| assert dfs_result.path[-1] == (2, 2) | |
| assert ucs_result.path[-1] == (2, 2) | |
| assert astar_result.path[-1] == (2, 2) | |
| assert greedy_result.path[-1] == (2, 2) | |
| assert ids_result.path[-1] == (2, 2) | |
| def test_optimal_algorithms_same_cost(self, grid_with_varied_traffic): | |
| """Test UCS and A* find same optimal cost.""" | |
| search = DeliverySearch(grid_with_varied_traffic, (0, 0), (2, 2), []) | |
| ucs_result, _ = ucs_search(search, visualize=False) | |
| astar_result, _ = astar_search(search, manhattan_heuristic, visualize=False) | |
| assert ucs_result.cost == astar_result.cost | |
| def test_visualization_consistency(self, simple_grid): | |
| """Test visualization steps are consistent across algorithms.""" | |
| search = DeliverySearch(simple_grid, (0, 0), (2, 2), []) | |
| _, bfs_steps = bfs_search(search, visualize=True) | |
| _, ucs_steps = ucs_search(search, visualize=True) | |
| # Both should have visualization steps | |
| assert bfs_steps is not None | |
| assert ucs_steps is not None | |
| assert len(bfs_steps) > 0 | |
| assert len(ucs_steps) > 0 | |