Skip to content

Bfs

Breadth-first search traversal.

BFSTraversal

Bases: TraversalStrategyABC

Breadth-first traversal policy.

search 

search(
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None
) -> SearchResult

Execute search over the tree using the supplied generator.

Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/traversal/bfs.py 
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def search(
    self,
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None,
) -> SearchResult:
    frontier: deque[ConfigurationNode] = deque([tree.root])
    return run_frontier_search(
        tree=tree,
        generator=generator,
        goal=goal,
        pop_next=lambda: frontier.popleft() if frontier else None,
        push_child=frontier.append,
        frontier_has_items=lambda: bool(frontier),
        max_expansions=max_expansions,
        max_depth=max_depth,
        goal_on_pop=False,
    )

bfs 

bfs(
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None,
) -> SearchResult

Breadth-first search.

Explores nodes level by level (shortest path first). Guarantees finding the shallowest goal if one exists within the depth limit.

Parameters:

Name Type Description Default
tree ConfigurationTree

The configuration tree to search.

 required
generator MoveGenerator

Move generator for producing candidates.

 required
goal GoalPredicate

Predicate that returns True for goal configurations.

 required
max_expansions int | None

Maximum nodes to expand. None means no limit.

 None
max_depth int | None

Maximum depth to explore. None means no limit.

 None

Returns:

Type Description
SearchResult

SearchResult with the goal node (or None if not found).
Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/traversal/bfs.py 
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
def bfs(
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None,
) -> SearchResult:
    """Breadth-first search.

    Explores nodes level by level (shortest path first). Guarantees
    finding the shallowest goal if one exists within the depth limit.

    Args:
        tree: The configuration tree to search.
        generator: Move generator for producing candidates.
        goal: Predicate that returns True for goal configurations.
        max_expansions: Maximum nodes to expand. None means no limit.
        max_depth: Maximum depth to explore. None means no limit.

    Returns:
        SearchResult with the goal node (or None if not found).
    """
    return BFSTraversal().search(
        tree=tree,
        generator=generator,
        goal=goal,
        max_expansions=max_expansions,
        max_depth=max_depth,
    )