# Comment out slow pytests... # 9.15s call graphs/bidirectional_breadth_first_search.py:: \ # graphs.bidirectional_breadth_first_search.BreadthFirstSearch # >>> bfs = BreadthFirstSearch((0, 0), (len(grid) - 1, len(grid[0]) - 1)) # >>> (bfs.start.pos_y + delta[
| 34 | |
| 35 | |
| 36 | class BreadthFirstSearch: |
| 37 | """ |
| 38 | # Comment out slow pytests... |
| 39 | # 9.15s call graphs/bidirectional_breadth_first_search.py:: \ |
| 40 | # graphs.bidirectional_breadth_first_search.BreadthFirstSearch |
| 41 | # >>> bfs = BreadthFirstSearch((0, 0), (len(grid) - 1, len(grid[0]) - 1)) |
| 42 | # >>> (bfs.start.pos_y + delta[3][0], bfs.start.pos_x + delta[3][1]) |
| 43 | (0, 1) |
| 44 | # >>> [x.pos for x in bfs.get_successors(bfs.start)] |
| 45 | [(1, 0), (0, 1)] |
| 46 | # >>> (bfs.start.pos_y + delta[2][0], bfs.start.pos_x + delta[2][1]) |
| 47 | (1, 0) |
| 48 | # >>> bfs.retrace_path(bfs.start) |
| 49 | [(0, 0)] |
| 50 | # >>> bfs.search() # doctest: +NORMALIZE_WHITESPACE |
| 51 | [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (4, 1), |
| 52 | (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (6, 5), (6, 6)] |
| 53 | """ |
| 54 | |
| 55 | def __init__(self, start: tuple[int, int], goal: tuple[int, int]): |
| 56 | self.start = Node(start[1], start[0], goal[1], goal[0], None) |
| 57 | self.target = Node(goal[1], goal[0], goal[1], goal[0], None) |
| 58 | |
| 59 | self.node_queue = [self.start] |
| 60 | self.reached = False |
| 61 | |
| 62 | def search(self) -> Path | None: |
| 63 | while self.node_queue: |
| 64 | current_node = self.node_queue.pop(0) |
| 65 | |
| 66 | if current_node.pos == self.target.pos: |
| 67 | self.reached = True |
| 68 | return self.retrace_path(current_node) |
| 69 | |
| 70 | successors = self.get_successors(current_node) |
| 71 | |
| 72 | for node in successors: |
| 73 | self.node_queue.append(node) |
| 74 | |
| 75 | if not self.reached: |
| 76 | return [self.start.pos] |
| 77 | return None |
| 78 | |
| 79 | def get_successors(self, parent: Node) -> list[Node]: |
| 80 | """ |
| 81 | Returns a list of successors (both in the grid and free spaces) |
| 82 | """ |
| 83 | successors = [] |
| 84 | for action in delta: |
| 85 | pos_x = parent.pos_x + action[1] |
| 86 | pos_y = parent.pos_y + action[0] |
| 87 | if not (0 <= pos_x <= len(grid[0]) - 1 and 0 <= pos_y <= len(grid) - 1): |
| 88 | continue |
| 89 | |
| 90 | if grid[pos_y][pos_x] != 0: |
| 91 | continue |
| 92 | |
| 93 | successors.append( |
no outgoing calls
no test coverage detected