Skip to content

search_trees

pleat.search_trees

Breadth-first search trees over half-edge graph elements.

Given a starting element (vertex or face) and a neighbour iterator, produce the edge list of a BFS spanning tree. Used to propagate orientation, colouring, and stacking-order constraints across a graph.

bfs_tree 

bfs_tree(
    source: T | set[T],
    neighbor_iter: Callable[[T], Iterable[T]],
) -> list[tuple[T, T]]

Compute a BFS spanning-tree edge list starting from a node or set.

Parameters:

Name Type Description Default
source T | set[T]

A single starting node, or a set of starting nodes (forest root).

 required
neighbor_iter Callable[[T], Iterable[T]]

Function mapping a node to an iterable of its neighbours.

 required

Returns:

Type Description
list[tuple[T, T]]

(parent, child) pairs in BFS discovery order.
Source code in pleat/search_trees.py 
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def bfs_tree(source: T | set[T], neighbor_iter: Callable[[T], Iterable[T]]) -> list[tuple[T, T]]:
    """Compute a BFS spanning-tree edge list starting from a node or set.

    Args:
        source: A single starting node, or a set of starting nodes (forest root).
        neighbor_iter: Function mapping a node to an iterable of its neighbours.

    Returns:
        ``(parent, child)`` pairs in BFS discovery order.
    """
    boundary = source if isinstance(source, set) else {source}
    parsed = boundary.copy()
    edges: list[tuple[T, T]] = []
    while boundary:
        new_boundary: set[T] = set()
        for orig in boundary:
            for dest in neighbor_iter(orig):
                if dest not in parsed:
                    parsed.add(dest)
                    new_boundary.add(dest)
                    edges.append((orig, dest))
        boundary = new_boundary
    return edges

face_bfs_tree 

face_bfs_tree(
    source: "Face | set[Face]",
) -> list[tuple["Face", "Face"]]

BFS tree over faces (interior faces only; None boundary faces are skipped).

Source code in pleat/search_trees.py 
43
44
45
def face_bfs_tree(source: "Face | set[Face]") -> list[tuple["Face", "Face"]]:
    """BFS tree over faces (interior faces only; ``None`` boundary faces are skipped)."""
    return bfs_tree(source, lambda f: (f2 for f2 in f.face_iter() if f2 is not None))

vertex_bfs_tree 

vertex_bfs_tree(
    source: "Vertex | set[Vertex]",
) -> list[tuple["Vertex", "Vertex"]]

BFS tree over vertices, traversing along incident edges.

Source code in pleat/search_trees.py 
48
49
50
def vertex_bfs_tree(source: "Vertex | set[Vertex]") -> list[tuple["Vertex", "Vertex"]]:
    """BFS tree over vertices, traversing along incident edges."""
    return bfs_tree(source, lambda v: v.vertex_iter())