Skip to content

Prims Weighted

Module: terminaltexteffects.utils.spanningtree.algo.primsweighted

Prims weighted minimum spanning tree algorithm implementation.

This module provides the PrimsWeighted spanning tree generator implementation. The algorithm builds a spanning tree over a graph of EffectCharacter nodes using Prim's algorithm with weighted edges.

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 unlinked neighbor with the lowest weight is chosen and the process repeats.

PrimsWeighted

Bases: SpanningTreeGenerator

Prims weighted minimum spanning tree algorithm.

Attributes:

Name Type Description
char_last_linked EffectCharacter | None

Character linked into the tree on the last step. None, if no character was linked during the last step.
char_link_order list[EffectCharacter]

Characters in linked order.
neighbors_last_added list[EffectCharacter]

Characters added as neighbors on the last step.
complete bool

Whether the algorithm is complete.
Source code in terminaltexteffects/utils/spanningtree/algo/primsweighted.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
 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
class PrimsWeighted(SpanningTreeGenerator):
    """Prims weighted minimum spanning tree algorithm.

    Attributes:
        char_last_linked (EffectCharacter | None): Character linked into the tree on the
            last step. None, if no character was linked during the last step.
        char_link_order (list[EffectCharacter]): Characters in linked order.
        neighbors_last_added (list[EffectCharacter]): Characters added as neighbors on 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 EffectCharacter. Defaults to None.
            limit_to_text_boundary (bool, optional): If True, the graph will not link to neighbors outside the text
                boundary.

        """
        super().__init__(terminal)
        starting_char = starting_char or terminal.get_character_by_input_coord(terminal.canvas.random_coord())
        self.limit_to_text_boundary = limit_to_text_boundary
        if starting_char is None:
            msg = "Unable to find a starting character."
            raise ValueError(msg)
        self._char_weights: dict[EffectCharacter, int] = {}
        for char in self.terminal.get_characters(inner_fill_chars=True, outer_fill_chars=True):
            self._char_weights[char] = random.randint(0, 99)
        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.

        """
        self.neighbors_last_added.clear()
        for neighbor in self.get_neighbors(char, limit_to_text_boundary=self.limit_to_text_boundary):
            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.

        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 not link.char_b.links:
                return link
        return None

    def step(self) -> None:
        """Perform a single step of the algorithm."""
        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_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 EffectCharacter. Defaults to None.

 None
limit_to_text_boundary bool

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

 False
Source code in terminaltexteffects/utils/spanningtree/algo/primsweighted.py 
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
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 EffectCharacter. Defaults to None.
        limit_to_text_boundary (bool, optional): If True, the graph will not link to neighbors outside the text
            boundary.

    """
    super().__init__(terminal)
    starting_char = starting_char or terminal.get_character_by_input_coord(terminal.canvas.random_coord())
    self.limit_to_text_boundary = limit_to_text_boundary
    if starting_char is None:
        msg = "Unable to find a starting character."
        raise ValueError(msg)
    self._char_weights: dict[EffectCharacter, int] = {}
    for char in self.terminal.get_characters(inner_fill_chars=True, outer_fill_chars=True):
        self._char_weights[char] = random.randint(0, 99)
    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
Source code in terminaltexteffects/utils/spanningtree/algo/primsweighted.py 
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
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.

    """
    self.neighbors_last_added.clear()
    for neighbor in self.get_neighbors(char, limit_to_text_boundary=self.limit_to_text_boundary):
        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.

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 
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
def get_lowest_weight_link(self) -> WeightedLink | None:
    """Get the weighted link with the lowest weight.

    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 not link.char_b.links:
            return link
    return None

step()

Perform a single step of the algorithm.

Source code in terminaltexteffects/utils/spanningtree/algo/primsweighted.py 
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
def step(self) -> None:
    """Perform a single step of the algorithm."""
    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_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 
30
31
32
33
34
35
36
37
38
39
40
41
42
43
@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