Skip to content

Prims Weighted

Module: terminaltexteffects.utils.spanningtree.algo.primsweighted

Weighted Prim-style spanning tree generator.

This module provides the PrimsWeighted spanning tree generator. The algorithm builds a spanning tree over a graph of EffectCharacter nodes using a Prim-style approach with randomly assigned per-character weights.

The algorithm starts from a chosen starting character (or a random one from the terminal) and grows the tree by linking to the unlinked neighbor with the lowest weight.

When a neighbor is linked, its unlinked neighbors are added to the pool of potential links. On each step, the pending link whose target character has the lowest assigned weight is chosen and the process repeats.

PrimsWeighted

Bases: SpanningTreeGenerator

Weighted 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 may retain its previous value when completion is reached through stale pending links.
char_link_order list[EffectCharacter]

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

Characters most recently added to the pending weighted-link pool. During initialization this is populated from the starting character's eligible neighbors.
complete bool

Whether the algorithm is complete.
Source code in terminaltexteffects/utils/spanningtree/algo/primsweighted.py 
 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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
class PrimsWeighted(SpanningTreeGenerator):
    """Weighted 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 may retain
            its previous value when completion is reached through stale pending links.
        char_link_order (list[EffectCharacter]): Characters in the order they were linked into
            the tree, beginning with the starting character.
        neighbors_last_added (list[EffectCharacter]): Characters most recently added to the
            pending weighted-link pool. During initialization this is populated from the starting
            character's eligible neighbors.
        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, and random starting-character selection is limited to the text boundary.

        Raises:
            ValueError: Unable to find a starting character, the starting character is pre-linked,
                or an eligible neighbor contains pre-existing links.

        """
        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._char_weights: dict[EffectCharacter, int] = {}
        for char in self.terminal.get_characters(inner_fill_chars=True, outer_fill_chars=True):
            weight = random.randint(0, 99)
            if not limit_to_text_boundary or self.terminal.canvas.coord_is_in_text(char.input_coord):
                self._char_weights[char] = weight
        self._char_weights.pop(starting_char, None)
        self._current_char = starting_char
        self.char_last_linked: EffectCharacter | None = self._current_char
        self.char_link_order: list[EffectCharacter] = [self._current_char]
        self.neighbors_last_added: list[EffectCharacter] = []
        self.complete = False
        self._pending_weighted_links: dict[int, list[WeightedLink]] = defaultdict(list)
        self.add_weighted_links(self._current_char)

    def add_weighted_links(self, char: EffectCharacter) -> None:
        """Add weighted links for the given character's unlinked neighbors.

        Args:
            char (EffectCharacter): Character for which weighted links are added.

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

        """
        self.neighbors_last_added.clear()
        for neighbor in self.get_neighbors(
            char,
            unlinked_only=False,
            limit_to_text_boundary=self.limit_to_text_boundary,
        ):
            if neighbor not in self._char_weights:
                continue
            self._require_unlinked(neighbor)
            self.neighbors_last_added.append(neighbor)
            self._pending_weighted_links[self._char_weights[neighbor]].append(
                WeightedLink(char, neighbor, self._char_weights[neighbor]),
            )

    def get_lowest_weight_link(self) -> WeightedLink | None:
        """Get the weighted link with the lowest weight.

        Stale pending links whose target character has already been linked are
        discarded while searching for the next valid link.

        Returns:
            WeightedLink | None: The weighted link with the lowest weight, or None if no links are available.

        """
        while self._pending_weighted_links:
            lowest_weight = min(self._pending_weighted_links)
            links_at_weight = self._pending_weighted_links[lowest_weight]
            link = links_at_weight.pop(random.randrange(len(links_at_weight)))
            if not links_at_weight:
                self._pending_weighted_links.pop(lowest_weight)
            if link.char_b not in self._char_weights:
                continue
            self._require_unlinked(link.char_b)
            return link
        return None

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

        Each step chooses the pending weighted link with the lowest target
        weight, links its target character into the tree, and adds the new
        character's eligible neighbors to the pending pool.

        Note:
            If the pending pool starts empty, this method sets `complete` to
            `True`, clears `neighbors_last_added`, and sets `char_last_linked`
            to `None`.

            If pending links exist but all remaining candidates are stale,
            `get_lowest_weight_link()` returns `None` and this method sets
            `complete` to `True` without resetting `char_last_linked` or
            `neighbors_last_added`.

        """
        if self._pending_weighted_links:
            next_link = self.get_lowest_weight_link()
            if next_link is None:
                self.complete = True
                return
            next_link.char_a._link(next_link.char_b)
            self._char_weights.pop(next_link.char_b)
            self.char_last_linked = next_link.char_b
            self.char_link_order.append(next_link.char_b)
            self.add_weighted_links(next_link.char_b)
        else:
            self.complete = True
            self.char_last_linked = None
            self.neighbors_last_added.clear()
            return

__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, and random starting-character selection is limited to the text boundary.

 False

Raises:

Type Description
ValueError

Unable to find a starting character, the starting character is pre-linked, or an eligible neighbor contains pre-existing links.
Source code in terminaltexteffects/utils/spanningtree/algo/primsweighted.py 
 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
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, and random starting-character selection is limited to the text boundary.

    Raises:
        ValueError: Unable to find a starting character, the starting character is pre-linked,
            or an eligible neighbor contains pre-existing links.

    """
    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._char_weights: dict[EffectCharacter, int] = {}
    for char in self.terminal.get_characters(inner_fill_chars=True, outer_fill_chars=True):
        weight = random.randint(0, 99)
        if not limit_to_text_boundary or self.terminal.canvas.coord_is_in_text(char.input_coord):
            self._char_weights[char] = weight
    self._char_weights.pop(starting_char, None)
    self._current_char = starting_char
    self.char_last_linked: EffectCharacter | None = self._current_char
    self.char_link_order: list[EffectCharacter] = [self._current_char]
    self.neighbors_last_added: list[EffectCharacter] = []
    self.complete = False
    self._pending_weighted_links: dict[int, list[WeightedLink]] = defaultdict(list)
    self.add_weighted_links(self._current_char)

Add weighted links for the given character's unlinked neighbors.

Parameters:

Name Type Description Default
char EffectCharacter

Character for which weighted links are added.

 required

Raises:

Type Description
ValueError

An unvisited neighbor contains pre-existing links.
Source code in terminaltexteffects/utils/spanningtree/algo/primsweighted.py 
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
def add_weighted_links(self, char: EffectCharacter) -> None:
    """Add weighted links for the given character's unlinked neighbors.

    Args:
        char (EffectCharacter): Character for which weighted links are added.

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

    """
    self.neighbors_last_added.clear()
    for neighbor in self.get_neighbors(
        char,
        unlinked_only=False,
        limit_to_text_boundary=self.limit_to_text_boundary,
    ):
        if neighbor not in self._char_weights:
            continue
        self._require_unlinked(neighbor)
        self.neighbors_last_added.append(neighbor)
        self._pending_weighted_links[self._char_weights[neighbor]].append(
            WeightedLink(char, neighbor, self._char_weights[neighbor]),
        )

Get the weighted link with the lowest weight.

Stale pending links whose target character has already been linked are discarded while searching for the next valid link.

Returns:

Type Description
WeightedLink | None

WeightedLink | None: The weighted link with the lowest weight, or None if no links are available.
Source code in terminaltexteffects/utils/spanningtree/algo/primsweighted.py 
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
def get_lowest_weight_link(self) -> WeightedLink | None:
    """Get the weighted link with the lowest weight.

    Stale pending links whose target character has already been linked are
    discarded while searching for the next valid link.

    Returns:
        WeightedLink | None: The weighted link with the lowest weight, or None if no links are available.

    """
    while self._pending_weighted_links:
        lowest_weight = min(self._pending_weighted_links)
        links_at_weight = self._pending_weighted_links[lowest_weight]
        link = links_at_weight.pop(random.randrange(len(links_at_weight)))
        if not links_at_weight:
            self._pending_weighted_links.pop(lowest_weight)
        if link.char_b not in self._char_weights:
            continue
        self._require_unlinked(link.char_b)
        return link
    return None

step()

Advance the tree generation by one step.

Each step chooses the pending weighted link with the lowest target weight, links its target character into the tree, and adds the new character's eligible neighbors to the pending pool.

Note

If the pending pool starts empty, this method sets complete to True, clears neighbors_last_added, and sets char_last_linked to None.

If pending links exist but all remaining candidates are stale, get_lowest_weight_link() returns None and this method sets complete to True without resetting char_last_linked or neighbors_last_added.

Source code in terminaltexteffects/utils/spanningtree/algo/primsweighted.py 
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
def step(self) -> None:
    """Advance the tree generation by one step.

    Each step chooses the pending weighted link with the lowest target
    weight, links its target character into the tree, and adds the new
    character's eligible neighbors to the pending pool.

    Note:
        If the pending pool starts empty, this method sets `complete` to
        `True`, clears `neighbors_last_added`, and sets `char_last_linked`
        to `None`.

        If pending links exist but all remaining candidates are stale,
        `get_lowest_weight_link()` returns `None` and this method sets
        `complete` to `True` without resetting `char_last_linked` or
        `neighbors_last_added`.

    """
    if self._pending_weighted_links:
        next_link = self.get_lowest_weight_link()
        if next_link is None:
            self.complete = True
            return
        next_link.char_a._link(next_link.char_b)
        self._char_weights.pop(next_link.char_b)
        self.char_last_linked = next_link.char_b
        self.char_link_order.append(next_link.char_b)
        self.add_weighted_links(next_link.char_b)
    else:
        self.complete = True
        self.char_last_linked = None
        self.neighbors_last_added.clear()
        return

Weighted link.

Attributes:

Name Type Description
char_a EffectCharacter

One end of the link.
char_b EffectCharacter

The other end of the link.
weight int

Weight of the link.
Source code in terminaltexteffects/utils/spanningtree/algo/primsweighted.py 
31
32
33
34
35
36
37
38
39
40
41
42
43
44
@dataclass
class WeightedLink:
    """Weighted link.

    Attributes:
        char_a (EffectCharacter): One end of the link.
        char_b (EffectCharacter): The other end of the link.
        weight (int): Weight of the link.

    """

    char_a: EffectCharacter
    char_b: EffectCharacter
    weight: int