graphs.bidirectional_breadth_first_search

https://en.wikipedia.org/wiki/Bidirectional_search

Attributes

Path
delta
grid
init

Classes

BidirectionalBreadthFirstSearch
BreadthFirstSearch	# Comment out slow pytests...
Node

Module Contents

class graphs.bidirectional_breadth_first_search.BidirectionalBreadthFirstSearch(start, goal)

>>> bd_bfs = BidirectionalBreadthFirstSearch((0, 0), (len(grid) - 1,
...                                                   len(grid[0]) - 1))
>>> bd_bfs.fwd_bfs.start.pos == bd_bfs.bwd_bfs.target.pos
True
>>> bd_bfs.retrace_bidirectional_path(bd_bfs.fwd_bfs.start,
...                                     bd_bfs.bwd_bfs.start)
[(0, 0)]
>>> bd_bfs.search()
[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3),
 (2, 4), (3, 4), (3, 5), (3, 6), (4, 6), (5, 6), (6, 6)]

retrace_bidirectional_path(fwd_node: Node, bwd_node: Node) → Path

search() → Path | None

bwd_bfs

fwd_bfs

reached = False

class graphs.bidirectional_breadth_first_search.BreadthFirstSearch(start: tuple[int, int], goal: tuple[int, int])

# 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[3][0], bfs.start.pos_x + delta[3][1]) (0, 1) # >>> [x.pos for x in bfs.get_successors(bfs.start)] [(1, 0), (0, 1)] # >>> (bfs.start.pos_y + delta[2][0], bfs.start.pos_x + delta[2][1]) (1, 0) # >>> bfs.retrace_path(bfs.start) [(0, 0)] # >>> bfs.search() # doctest: +NORMALIZE_WHITESPACE [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (4, 1),

(5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (6, 5), (6, 6)]

get_successors(parent: Node) → list[Node]

Returns a list of successors (both in the grid and free spaces)

retrace_path(node: Node | None) → Path

Retrace the path from parents to parents until start node

search() → Path | None

node_queue

reached = False

start

target

class graphs.bidirectional_breadth_first_search.Node(pos_x: int, pos_y: int, goal_x: int, goal_y: int, parent: Node | None)

goal_x

goal_y

parent

pos

pos_x

pos_y

graphs.bidirectional_breadth_first_search.Path

graphs.bidirectional_breadth_first_search.delta

graphs.bidirectional_breadth_first_search.grid = [[0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0], [1,...

graphs.bidirectional_breadth_first_search.init = (0, 0)