Skip to content

Recursive Backtracker

Module: terminaltexteffects.utils.spanningtree.algo.recursivebacktracker

Recursive backtracker spanning tree generator.

This module provides the RecursiveBacktracker spanning tree generator. The algorithm builds a spanning tree over a graph of EffectCharacter nodes using a depth-first recursive backtracker approach implemented iteratively with an explicit stack.

The algorithm starts from a chosen starting character (or a random one from the terminal) and grows the tree by repeatedly linking to a randomly selected unvisited neighbor. Linked cells are added to the stack.

When a node has no unvisited neighbors the algorithm backtracks by popping the stack until it finds a node with unvisited neighbors.

RecursiveBacktracker

Bases: SpanningTreeGenerator

Recursive backtracker spanning tree generator.

Attributes:

Name Type Description
char_last_linked EffectCharacter | None

Character most recently linked into the tree. During initialization this is the starting character. On later steps it is None when the generator backtracks instead of linking a new character.
char_link_order list[EffectCharacter]

Characters in the order they were linked into the tree, beginning with the starting character.
stack list[EffectCharacter]

Depth-first traversal stack. During initialization it contains the starting character.
stack_last_popped EffectCharacter | None

Character popped off the stack on the last step. None if no character was popped during the last step.
complete bool

Whether the algorithm is complete.
Source code in terminaltexteffects/utils/spanningtree/algo/recursivebacktracker.py 
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 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
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
class RecursiveBacktracker(SpanningTreeGenerator):
    """Recursive backtracker spanning tree generator.

    Attributes:
        char_last_linked (EffectCharacter | None): Character most recently linked into the tree.
            During initialization this is the starting character. On later steps it is `None`
            when the generator backtracks instead of linking a new character.
        char_link_order (list[EffectCharacter]): Characters in the order they were linked into
            the tree, beginning with the starting character.
        stack (list[EffectCharacter]): Depth-first traversal stack. During initialization it
            contains the starting character.
        stack_last_popped (EffectCharacter | None): Character popped off the stack on the
            last step. None if no character was popped during the last step.
        complete (bool): Whether the algorithm is complete.

    """

    def __init__(
        self,
        terminal: Terminal,
        starting_char: EffectCharacter | None = None,
        *,
        limit_to_text_boundary: bool = False,
    ) -> None:
        """Initialize the algorithm.

        Args:
            terminal (Terminal): TTE Terminal.
            starting_char (EffectCharacter | None, optional): Starting character for the tree
                generation. When `None`, a character is selected by resolving a random canvas
                coordinate to a terminal character.
            limit_to_text_boundary (bool, optional): If True, the graph will not link to neighbors outside the text
                boundary.

        Raises:
            ValueError: Unable to find a starting character or the starting character is pre-linked.

        """
        super().__init__(terminal)
        self.limit_to_text_boundary = limit_to_text_boundary
        starting_char = starting_char or terminal.get_character_by_input_coord(
            terminal.canvas.random_coord(within_text_boundary=limit_to_text_boundary),
        )
        if starting_char is None:
            msg = "Unable to find a starting character."
            raise ValueError(msg)
        self._require_unlinked(starting_char)
        self._current_char = starting_char
        self._visited_chars = {starting_char}
        self.char_last_linked: EffectCharacter | None = self._current_char
        self.char_link_order: list[EffectCharacter] = [self._current_char]
        self.stack: list[EffectCharacter] = [self._current_char]
        self.stack_last_popped: EffectCharacter | None = None
        self.complete = False

    def step(self) -> None:
        """Advance the traversal by one step.

        Each step either links one unvisited neighbor and descends deeper
        into the tree, or pops the traversal stack to backtrack when the
        current character has no unvisited neighbors.

        Note:
            `complete` becomes `True` only on a subsequent call after
            the stack is already empty. If the last stack item is popped
            during this call, the generator ends the step with an empty
            stack and `complete` still set to `False`.

        Raises:
            ValueError: An unvisited neighbor contains pre-existing links.

        """
        self.char_last_linked = None
        self.stack_last_popped = None
        if self.stack:
            unvisited_neighbors = self._get_unvisited_neighbors(
                self._current_char,
                self._visited_chars,
                limit_to_text_boundary=self.limit_to_text_boundary,
            )
            if unvisited_neighbors:
                next_char = random.choice(unvisited_neighbors)
                self._current_char._link(next_char)
                self._visited_chars.add(next_char)
                self.char_link_order.append(next_char)
                self.char_last_linked = next_char
                self.stack.append(next_char)
                self._current_char = next_char
            else:
                self.stack_last_popped = self.stack.pop()
                if self.stack:
                    self._current_char = self.stack[-1]
        else:
            self.complete = True

__init__(terminal, starting_char=None, *, limit_to_text_boundary=False)

Initialize the algorithm.

Parameters:

Name Type Description Default
terminal Terminal

TTE Terminal.

 required
starting_char EffectCharacter | None

Starting character for the tree generation. When None, a character is selected by resolving a random canvas coordinate to a terminal character.

 None
limit_to_text_boundary bool

If True, the graph will not link to neighbors outside the text boundary.

 False

Raises:

Type Description
ValueError

Unable to find a starting character or the starting character is pre-linked.
Source code in terminaltexteffects/utils/spanningtree/algo/recursivebacktracker.py 
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
72
73
74
75
76
77
78
79
80
81
82
def __init__(
    self,
    terminal: Terminal,
    starting_char: EffectCharacter | None = None,
    *,
    limit_to_text_boundary: bool = False,
) -> None:
    """Initialize the algorithm.

    Args:
        terminal (Terminal): TTE Terminal.
        starting_char (EffectCharacter | None, optional): Starting character for the tree
            generation. When `None`, a character is selected by resolving a random canvas
            coordinate to a terminal character.
        limit_to_text_boundary (bool, optional): If True, the graph will not link to neighbors outside the text
            boundary.

    Raises:
        ValueError: Unable to find a starting character or the starting character is pre-linked.

    """
    super().__init__(terminal)
    self.limit_to_text_boundary = limit_to_text_boundary
    starting_char = starting_char or terminal.get_character_by_input_coord(
        terminal.canvas.random_coord(within_text_boundary=limit_to_text_boundary),
    )
    if starting_char is None:
        msg = "Unable to find a starting character."
        raise ValueError(msg)
    self._require_unlinked(starting_char)
    self._current_char = starting_char
    self._visited_chars = {starting_char}
    self.char_last_linked: EffectCharacter | None = self._current_char
    self.char_link_order: list[EffectCharacter] = [self._current_char]
    self.stack: list[EffectCharacter] = [self._current_char]
    self.stack_last_popped: EffectCharacter | None = None
    self.complete = False

step()

Advance the traversal by one step.

Each step either links one unvisited neighbor and descends deeper into the tree, or pops the traversal stack to backtrack when the current character has no unvisited neighbors.

Note

complete becomes True only on a subsequent call after the stack is already empty. If the last stack item is popped during this call, the generator ends the step with an empty stack and complete still set to False.

Raises:

Type Description
ValueError

An unvisited neighbor contains pre-existing links.
Source code in terminaltexteffects/utils/spanningtree/algo/recursivebacktracker.py 
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
def step(self) -> None:
    """Advance the traversal by one step.

    Each step either links one unvisited neighbor and descends deeper
    into the tree, or pops the traversal stack to backtrack when the
    current character has no unvisited neighbors.

    Note:
        `complete` becomes `True` only on a subsequent call after
        the stack is already empty. If the last stack item is popped
        during this call, the generator ends the step with an empty
        stack and `complete` still set to `False`.

    Raises:
        ValueError: An unvisited neighbor contains pre-existing links.

    """
    self.char_last_linked = None
    self.stack_last_popped = None
    if self.stack:
        unvisited_neighbors = self._get_unvisited_neighbors(
            self._current_char,
            self._visited_chars,
            limit_to_text_boundary=self.limit_to_text_boundary,
        )
        if unvisited_neighbors:
            next_char = random.choice(unvisited_neighbors)
            self._current_char._link(next_char)
            self._visited_chars.add(next_char)
            self.char_link_order.append(next_char)
            self.char_last_linked = next_char
            self.stack.append(next_char)
            self._current_char = next_char
        else:
            self.stack_last_popped = self.stack.pop()
            if self.stack:
                self._current_char = self.stack[-1]
    else:
        self.complete = True