Skip to content

Prims Simple

Module: terminaltexteffects.utils.spanningtree.algo.primssimple

Simplified Prim-style spanning tree generator.

A simplified Prim-style algorithm uses equal weight for all links and selects from the current edge set at random.

The algorithm starts from a chosen starting character (or a random one from the terminal) and grows by randomly linking to an unlinked neighbor.

When a neighbor is linked, the neighbor is checked for unlinked neighbors. If it has unlinked neighbors, it is considered an edge. On each step, a random edge is chosen and the process repeats.

PrimsSimple

Bases: SpanningTreeGenerator

Simplified Prim-style 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 retains its previous value if no new character is linked.
char_link_order list[EffectCharacter]

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

Characters currently considered edge candidates. During initialization this contains the starting character.
edge_last_added EffectCharacter | None

Character most recently added to the edge list. During initialization this is the starting character. On later steps it retains its previous value if no new edge character is added.
edge_last_popped EffectCharacter | None

Character popped off the edge list 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/primssimple.py 
 26
 27
 28
 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 PrimsSimple(SpanningTreeGenerator):
    """Simplified Prim-style 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 retains
            its previous value if no new character is linked.
        char_link_order (list[EffectCharacter]): Characters in the order they were linked into
            the tree, beginning with the starting character.
        edge_chars (list[EffectCharacter]): Characters currently considered edge candidates.
            During initialization this contains the starting character.
        edge_last_added (EffectCharacter | None): Character most recently added to the edge list.
            During initialization this is the starting character. On later steps it retains its
            previous value if no new edge character is added.
        edge_last_popped (EffectCharacter | None): Character popped off the edge list 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.

        """
        super().__init__(terminal)
        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.limit_to_text_boundary = limit_to_text_boundary
        self._current_char = starting_char
        self.char_last_linked: EffectCharacter | None = self._current_char
        self.char_link_order: list[EffectCharacter] = [self._current_char]
        self.edge_chars = [self._current_char]
        self.edge_last_added: EffectCharacter | None = self._current_char
        self.edge_last_popped: EffectCharacter | None = None
        self.complete = False

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

        Each step pops one character from the current edge list. If that
        character has any eligible unlinked neighbors, one is linked into the
        tree, the popped character may be returned to the edge list if it still
        has eligible neighbors, and the newly linked character may be added to
        the edge list as well.

        Note:
            `complete` becomes `True` only when `edge_chars` is already empty at
            the start of a call. If a step pops the last edge character and
            links nothing, the generator ends that call with an empty edge list
            and `complete` still set to `False`.

        """
        if self.edge_chars:
            self._current_char = self.edge_chars.pop(random.randrange(len(self.edge_chars)))
            self.edge_last_popped = self._current_char
            unlinked_neighbors = self.get_neighbors(
                self._current_char,
                limit_to_text_boundary=self.limit_to_text_boundary,
            )

            if unlinked_neighbors:
                next_char = unlinked_neighbors.pop(random.randrange(len(unlinked_neighbors)))
                self._current_char._link(next_char)
                self.char_link_order.append(next_char)
                self.char_last_linked = next_char
                if unlinked_neighbors:
                    self.edge_chars.append(self._current_char)
                unlinked_neighbors = self.get_neighbors(
                    next_char,
                    limit_to_text_boundary=self.limit_to_text_boundary,
                )
                if unlinked_neighbors:
                    self.edge_chars.append(next_char)
                    self.edge_last_added = next_char
        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.
Source code in terminaltexteffects/utils/spanningtree/algo/primssimple.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
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.

    """
    super().__init__(terminal)
    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.limit_to_text_boundary = limit_to_text_boundary
    self._current_char = starting_char
    self.char_last_linked: EffectCharacter | None = self._current_char
    self.char_link_order: list[EffectCharacter] = [self._current_char]
    self.edge_chars = [self._current_char]
    self.edge_last_added: EffectCharacter | None = self._current_char
    self.edge_last_popped: EffectCharacter | None = None
    self.complete = False

step()

Advance the tree generation by one step.

Each step pops one character from the current edge list. If that character has any eligible unlinked neighbors, one is linked into the tree, the popped character may be returned to the edge list if it still has eligible neighbors, and the newly linked character may be added to the edge list as well.

Note

complete becomes True only when edge_chars is already empty at the start of a call. If a step pops the last edge character and links nothing, the generator ends that call with an empty edge list and complete still set to False.

Source code in terminaltexteffects/utils/spanningtree/algo/primssimple.py 
 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
def step(self) -> None:
    """Advance the tree generation by one step.

    Each step pops one character from the current edge list. If that
    character has any eligible unlinked neighbors, one is linked into the
    tree, the popped character may be returned to the edge list if it still
    has eligible neighbors, and the newly linked character may be added to
    the edge list as well.

    Note:
        `complete` becomes `True` only when `edge_chars` is already empty at
        the start of a call. If a step pops the last edge character and
        links nothing, the generator ends that call with an empty edge list
        and `complete` still set to `False`.

    """
    if self.edge_chars:
        self._current_char = self.edge_chars.pop(random.randrange(len(self.edge_chars)))
        self.edge_last_popped = self._current_char
        unlinked_neighbors = self.get_neighbors(
            self._current_char,
            limit_to_text_boundary=self.limit_to_text_boundary,
        )

        if unlinked_neighbors:
            next_char = unlinked_neighbors.pop(random.randrange(len(unlinked_neighbors)))
            self._current_char._link(next_char)
            self.char_link_order.append(next_char)
            self.char_last_linked = next_char
            if unlinked_neighbors:
                self.edge_chars.append(self._current_char)
            unlinked_neighbors = self.get_neighbors(
                next_char,
                limit_to_text_boundary=self.limit_to_text_boundary,
            )
            if unlinked_neighbors:
                self.edge_chars.append(next_char)
                self.edge_last_added = next_char
    else:
        self.complete = True