(
graph: dict[int, list[int]],
queue: deque[int],
parents: dict[int, int | None],
opposite_direction_parents: dict[int, int | None],
)
| 15 | |
| 16 | |
| 17 | def expand_search( |
| 18 | graph: dict[int, list[int]], |
| 19 | queue: deque[int], |
| 20 | parents: dict[int, int | None], |
| 21 | opposite_direction_parents: dict[int, int | None], |
| 22 | ) -> int | None: |
| 23 | if not queue: |
| 24 | return None |
| 25 | |
| 26 | current = queue.popleft() |
| 27 | for neighbor in graph[current]: |
| 28 | if neighbor in parents: |
| 29 | continue |
| 30 | |
| 31 | parents[neighbor] = current |
| 32 | queue.append(neighbor) |
| 33 | |
| 34 | # Check if this creates an intersection |
| 35 | if neighbor in opposite_direction_parents: |
| 36 | return neighbor |
| 37 | |
| 38 | return None |
| 39 | |
| 40 | |
| 41 | def construct_path(current: int | None, parents: dict[int, int | None]) -> list[int]: |
no test coverage detected