Skip to content

Additional data structures

Linked lists

LinkedListNode

Linked list node.

Source code in tralda/datastructures/linked.py 
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class LinkedListNode:
    """Linked list node."""

    __slots__ = ("_value", "_next")

    def __init__(self, value: Any, next_node: LinkedListNode | None = None) -> None:
        """Constructor of the inked list node.

        Args:
            value: The value that the list node shall hold.
            next_node: The successor node in the doubly-linked list.
        """
        self._value = value
        self._next = next_node

    def get(self) -> Any:
        """Getter for the value.

        Returns:
            The value held by the list node.
        """
        return self._value

__init__(value: Any, next_node: LinkedListNode | None = None) -> None

Constructor of the inked list node.

Parameters:

Name Type Description Default
value Any

The value that the list node shall hold.

 required
next_node LinkedListNode | None

The successor node in the doubly-linked list.

 None
Source code in tralda/datastructures/linked.py 
17
18
19
20
21
22
23
24
25
def __init__(self, value: Any, next_node: LinkedListNode | None = None) -> None:
    """Constructor of the inked list node.

    Args:
        value: The value that the list node shall hold.
        next_node: The successor node in the doubly-linked list.
    """
    self._value = value
    self._next = next_node

get() -> Any

Getter for the value.

Returns:

Type Description
Any

The value held by the list node.
Source code in tralda/datastructures/linked.py 
27
28
29
30
31
32
33
def get(self) -> Any:
    """Getter for the value.

    Returns:
        The value held by the list node.
    """
    return self._value

LinkedList

Linked list.

Source code in tralda/datastructures/linked.py 
 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
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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
class LinkedList:
    """Linked list."""

    __slots__ = ("_first", "_last", "_count")

    def __init__(self, *args: Any) -> None:
        """Constructor of the inked list.

        Args:
            args: A single value or an iterable of values to be added to the list.
        """
        self._first = None
        self._last = None
        self._count = 0
        for arg in args:
            if isinstance(arg, Iterable):
                for item in arg:
                    self.append(item)
            else:
                self.append(arg)

    def __len__(self) -> int:
        """Number of items in the list.

        Returns:
            The number of items in the list.
        """
        return self._count

    def __bool__(self) -> bool:
        """Returns whether the list is non-empty.

        Returns:
            True if the list is non-empty, False otherwise.
        """
        return self._count > 0

    def __iter__(self) -> LinkedListIterator:
        """Returns an iterator object for the list.

        Returns:
            An iterator for this list.
        """
        return LinkedListIterator(self)

    def __next__(self):
        pass

    def __getitem__(self, index: int) -> Any:
        """Access value at a specified index.

        Returns:
            The value at the specified index.
        """
        return self.node_at(index)._value

    def first(self) -> Any:
        """Return the first item in the list.

        Returns:
            The first item in the list.
        """
        return self._first._value

    def last(self) -> Any:
        """Return the last item in the list.

        Returns:
            The last item in the list.
        """
        return self._last._value

    def first_node(self) -> LinkedListNode:
        """Return the first list node.

        Returns:
            The first node of the list.
        """
        return self._first

    def node_at(self, index: int) -> LinkedListNode:
        """Return the list node at the specified index (in O(n) time).

        The index can also be negative in which case it is counted from the end (as for built-in
        Python lists).

        Returns:
            The list node at the specified index.

        Raises:
            TypeError: If 'index' is not an integer.
            IndexError: If the index is out of bounds.
        """
        if not isinstance(index, int):
            raise TypeError("index must be of type 'int'")

        if index < (-self._count) or index >= self._count:
            raise IndexError(f"index {index} is out of bounds")

        if index < 0:
            index += self._count

        # search from beginning
        node = self._first
        for _ in range(index):
            node = node._next

        return node

    def append(self, value: Any) -> LinkedListNode:
        """Append an item to the list.

        Args:
            value: The value to be inserted at the end of the list.

        Returns:
            The new end node of the list.
        """
        new_end = LinkedListNode(value)
        if self._last:
            self._last._next = new_end

        self._last = new_end
        if not self._first:
            self._first = new_end

        self._count += 1

        return new_end

    def extend(self, iterable: Iterable) -> None:
        """Append multiple items to the list.

        Args:
            iterable: An iterable of values to be inserted at the end of the list.
        """
        for value in iterable:
            self.append(value)

    def concatenate(self, other: LinkedList) -> LinkedList:
        """Merges two linked lists.

        The instance for which this function is called is extended, the other list should no longer
        be used.

        Args:
            other: The liked list to concatenate with this list.

        Returns:
            This LikedList instance.

        Raises:
            TypeError: If 'other' is not a LinkedList instance.
        """
        if not isinstance(other, LinkedList):
            raise TypeError("must be of type 'LinkedList'")

        if self._last:
            self._last._next = other._first
        else:
            self._first = other._first

        if other._last:
            self._last = other._last

        self._count += other._count

        return self

    def append_left(self, value: Any) -> LinkedListNode:
        """Append an item to left side of the list.

        Args:
            value: The value to be inserted at the beginning of the list.

        Returns:
            The new start node of the list.
        """
        new_start = LinkedListNode(value, next_node=self._first)
        self._first = new_start
        if not self._last:
            self._last = new_start

        self._count += 1

        return new_start

    def remove(self, value: Any) -> Any:
        """Remove an item by value (in O(n) time).

        Args:
            value: The value to be removed.

        Raises:
            KeyError: If the value was not found in the list.
        """
        node = self._first
        prev_node = None

        while node:
            if node._value == value:
                if prev_node:
                    prev_node._next = node._next
                else:
                    self._first = node._next

                if not node._next:
                    self._last = prev_node

                self._count -= 1
                return

            prev_node = node
            node = node._next

        raise KeyError(f"value {value} is not in the linked list")

    def insert_right_of(self, node: LinkedListNode, value: Any) -> LinkedListNode:
        """Insert a new item right of a node of the list in O(1).

        Args:
            node: The list node next to which the item shall be inserted.
            value: The value to be inserted.

        Returns:
            The list node for the inserted value.
        """
        if node is self._last:
            new_node = self.append(value)
        else:
            new_node = LinkedListNode(value, next_node=node._next)
            node._next = new_node
            self._count += 1

        return new_node

    def truncate(self, index: int) -> None:
        """Truncate all nodes starting from the specified index in O(n) time.

        Args:
            index: The index from which on the list is truncated.
        """
        if index <= 0:
            self.clear()
        else:
            new_end = self.node_at(index - 1)
            self._last = new_end
            if new_end._next:
                new_end._next = None
            self._count = index

    def truncate_left(self, n: int) -> None:
        """Truncate n nodes on the left side.

        Args:
            n: The number of items to be truncated.
        """
        if n >= self._count:
            self.clear()
        else:
            new_start = self.node_at(n)
            self._first = new_start
            self._count -= n

    def popleft(self) -> Any:
        """Removes the first item of the list and returns its value.

        Returns:
            The former first item of the list which has been removed.

        Raises:
            IndexError: If the list is empty.
        """
        if self._first:
            value = self._first._value
            self._first = self._first._next
            if not self._first:
                self._last = None
            self._count -= 1
            return value

        raise IndexError("cannot pop from empty linked list")

    def clear(self) -> None:
        """Clear the list."""
        self._first = None
        self._last = None
        self._count = 0

    def _count_actual(self):
        """Counts the actual number of elements (for debugging purposes).

        Runs in O(n) time.

        Returns:
            The counted number of items in the list.
        """
        current = self._first
        counter = 0

        while current:
            counter += 1
            current = current._next

        return counter

__init__(*args: Any) -> None

Constructor of the inked list.

Parameters:

Name Type Description Default
args Any

A single value or an iterable of values to be added to the list.

 ()
Source code in tralda/datastructures/linked.py 
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def __init__(self, *args: Any) -> None:
    """Constructor of the inked list.

    Args:
        args: A single value or an iterable of values to be added to the list.
    """
    self._first = None
    self._last = None
    self._count = 0
    for arg in args:
        if isinstance(arg, Iterable):
            for item in arg:
                self.append(item)
        else:
            self.append(arg)

__len__() -> int

Number of items in the list.

Returns:

Type Description
int

The number of items in the list.
Source code in tralda/datastructures/linked.py 
57
58
59
60
61
62
63
def __len__(self) -> int:
    """Number of items in the list.

    Returns:
        The number of items in the list.
    """
    return self._count

__bool__() -> bool

Returns whether the list is non-empty.

Returns:

Type Description
bool

True if the list is non-empty, False otherwise.
Source code in tralda/datastructures/linked.py 
65
66
67
68
69
70
71
def __bool__(self) -> bool:
    """Returns whether the list is non-empty.

    Returns:
        True if the list is non-empty, False otherwise.
    """
    return self._count > 0

__iter__() -> LinkedListIterator

Returns an iterator object for the list.

Returns:

Type Description
LinkedListIterator

An iterator for this list.
Source code in tralda/datastructures/linked.py 
73
74
75
76
77
78
79
def __iter__(self) -> LinkedListIterator:
    """Returns an iterator object for the list.

    Returns:
        An iterator for this list.
    """
    return LinkedListIterator(self)

__getitem__(index: int) -> Any

Access value at a specified index.

Returns:

Type Description
Any

The value at the specified index.
Source code in tralda/datastructures/linked.py 
84
85
86
87
88
89
90
def __getitem__(self, index: int) -> Any:
    """Access value at a specified index.

    Returns:
        The value at the specified index.
    """
    return self.node_at(index)._value

first() -> Any

Return the first item in the list.

Returns:

Type Description
Any

The first item in the list.
Source code in tralda/datastructures/linked.py 
92
93
94
95
96
97
98
def first(self) -> Any:
    """Return the first item in the list.

    Returns:
        The first item in the list.
    """
    return self._first._value

last() -> Any

Return the last item in the list.

Returns:

Type Description
Any

The last item in the list.
Source code in tralda/datastructures/linked.py 
100
101
102
103
104
105
106
def last(self) -> Any:
    """Return the last item in the list.

    Returns:
        The last item in the list.
    """
    return self._last._value

first_node() -> LinkedListNode

Return the first list node.

Returns:

Type Description
LinkedListNode

The first node of the list.
Source code in tralda/datastructures/linked.py 
108
109
110
111
112
113
114
def first_node(self) -> LinkedListNode:
    """Return the first list node.

    Returns:
        The first node of the list.
    """
    return self._first

node_at(index: int) -> LinkedListNode

Return the list node at the specified index (in O(n) time).

The index can also be negative in which case it is counted from the end (as for built-in Python lists).

Returns:

Type Description
LinkedListNode

The list node at the specified index.

Raises:

Type Description
TypeError

If 'index' is not an integer.
IndexError

If the index is out of bounds.
Source code in tralda/datastructures/linked.py 
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
def node_at(self, index: int) -> LinkedListNode:
    """Return the list node at the specified index (in O(n) time).

    The index can also be negative in which case it is counted from the end (as for built-in
    Python lists).

    Returns:
        The list node at the specified index.

    Raises:
        TypeError: If 'index' is not an integer.
        IndexError: If the index is out of bounds.
    """
    if not isinstance(index, int):
        raise TypeError("index must be of type 'int'")

    if index < (-self._count) or index >= self._count:
        raise IndexError(f"index {index} is out of bounds")

    if index < 0:
        index += self._count

    # search from beginning
    node = self._first
    for _ in range(index):
        node = node._next

    return node

append(value: Any) -> LinkedListNode

Append an item to the list.

Parameters:

Name Type Description Default
value Any

The value to be inserted at the end of the list.

 required

Returns:

Type Description
LinkedListNode

The new end node of the list.
Source code in tralda/datastructures/linked.py 
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
def append(self, value: Any) -> LinkedListNode:
    """Append an item to the list.

    Args:
        value: The value to be inserted at the end of the list.

    Returns:
        The new end node of the list.
    """
    new_end = LinkedListNode(value)
    if self._last:
        self._last._next = new_end

    self._last = new_end
    if not self._first:
        self._first = new_end

    self._count += 1

    return new_end

extend(iterable: Iterable) -> None

Append multiple items to the list.

Parameters:

Name Type Description Default
iterable Iterable

An iterable of values to be inserted at the end of the list.

 required
Source code in tralda/datastructures/linked.py 
166
167
168
169
170
171
172
173
def extend(self, iterable: Iterable) -> None:
    """Append multiple items to the list.

    Args:
        iterable: An iterable of values to be inserted at the end of the list.
    """
    for value in iterable:
        self.append(value)

concatenate(other: LinkedList) -> LinkedList

Merges two linked lists.

The instance for which this function is called is extended, the other list should no longer be used.

Parameters:

Name Type Description Default
other LinkedList

The liked list to concatenate with this list.

 required

Returns:

Type Description
LinkedList

This LikedList instance.

Raises:

Type Description
TypeError

If 'other' is not a LinkedList instance.
Source code in tralda/datastructures/linked.py 
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
def concatenate(self, other: LinkedList) -> LinkedList:
    """Merges two linked lists.

    The instance for which this function is called is extended, the other list should no longer
    be used.

    Args:
        other: The liked list to concatenate with this list.

    Returns:
        This LikedList instance.

    Raises:
        TypeError: If 'other' is not a LinkedList instance.
    """
    if not isinstance(other, LinkedList):
        raise TypeError("must be of type 'LinkedList'")

    if self._last:
        self._last._next = other._first
    else:
        self._first = other._first

    if other._last:
        self._last = other._last

    self._count += other._count

    return self

append_left(value: Any) -> LinkedListNode

Append an item to left side of the list.

Parameters:

Name Type Description Default
value Any

The value to be inserted at the beginning of the list.

 required

Returns:

Type Description
LinkedListNode

The new start node of the list.
Source code in tralda/datastructures/linked.py 
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
def append_left(self, value: Any) -> LinkedListNode:
    """Append an item to left side of the list.

    Args:
        value: The value to be inserted at the beginning of the list.

    Returns:
        The new start node of the list.
    """
    new_start = LinkedListNode(value, next_node=self._first)
    self._first = new_start
    if not self._last:
        self._last = new_start

    self._count += 1

    return new_start

remove(value: Any) -> Any

Remove an item by value (in O(n) time).

Parameters:

Name Type Description Default
value Any

The value to be removed.

 required

Raises:

Type Description
KeyError

If the value was not found in the list.
Source code in tralda/datastructures/linked.py 
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
def remove(self, value: Any) -> Any:
    """Remove an item by value (in O(n) time).

    Args:
        value: The value to be removed.

    Raises:
        KeyError: If the value was not found in the list.
    """
    node = self._first
    prev_node = None

    while node:
        if node._value == value:
            if prev_node:
                prev_node._next = node._next
            else:
                self._first = node._next

            if not node._next:
                self._last = prev_node

            self._count -= 1
            return

        prev_node = node
        node = node._next

    raise KeyError(f"value {value} is not in the linked list")

insert_right_of(node: LinkedListNode, value: Any) -> LinkedListNode

Insert a new item right of a node of the list in O(1).

Parameters:

Name Type Description Default
node LinkedListNode

The list node next to which the item shall be inserted.

 required
value Any

The value to be inserted.

 required

Returns:

Type Description
LinkedListNode

The list node for the inserted value.
Source code in tralda/datastructures/linked.py 
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
def insert_right_of(self, node: LinkedListNode, value: Any) -> LinkedListNode:
    """Insert a new item right of a node of the list in O(1).

    Args:
        node: The list node next to which the item shall be inserted.
        value: The value to be inserted.

    Returns:
        The list node for the inserted value.
    """
    if node is self._last:
        new_node = self.append(value)
    else:
        new_node = LinkedListNode(value, next_node=node._next)
        node._next = new_node
        self._count += 1

    return new_node

truncate(index: int) -> None

Truncate all nodes starting from the specified index in O(n) time.

Parameters:

Name Type Description Default
index int

The index from which on the list is truncated.

 required
Source code in tralda/datastructures/linked.py 
272
273
274
275
276
277
278
279
280
281
282
283
284
285
def truncate(self, index: int) -> None:
    """Truncate all nodes starting from the specified index in O(n) time.

    Args:
        index: The index from which on the list is truncated.
    """
    if index <= 0:
        self.clear()
    else:
        new_end = self.node_at(index - 1)
        self._last = new_end
        if new_end._next:
            new_end._next = None
        self._count = index

truncate_left(n: int) -> None

Truncate n nodes on the left side.

Parameters:

Name Type Description Default
n int

The number of items to be truncated.

 required
Source code in tralda/datastructures/linked.py 
287
288
289
290
291
292
293
294
295
296
297
298
def truncate_left(self, n: int) -> None:
    """Truncate n nodes on the left side.

    Args:
        n: The number of items to be truncated.
    """
    if n >= self._count:
        self.clear()
    else:
        new_start = self.node_at(n)
        self._first = new_start
        self._count -= n

popleft() -> Any

Removes the first item of the list and returns its value.

Returns:

Type Description
Any

The former first item of the list which has been removed.

Raises:

Type Description
IndexError

If the list is empty.
Source code in tralda/datastructures/linked.py 
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
def popleft(self) -> Any:
    """Removes the first item of the list and returns its value.

    Returns:
        The former first item of the list which has been removed.

    Raises:
        IndexError: If the list is empty.
    """
    if self._first:
        value = self._first._value
        self._first = self._first._next
        if not self._first:
            self._last = None
        self._count -= 1
        return value

    raise IndexError("cannot pop from empty linked list")

clear() -> None

Clear the list.

Source code in tralda/datastructures/linked.py 
319
320
321
322
323
def clear(self) -> None:
    """Clear the list."""
    self._first = None
    self._last = None
    self._count = 0

Doubly linked lists

DLListNode

Doubly-linked list node.

Source code in tralda/datastructures/doubly_linked.py 
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class DLListNode:
    """Doubly-linked list node."""

    __slots__ = ("_value", "_prev", "_next")

    def __init__(
        self, value: Any, prev_node: DLListNode | None = None, next_node: DLListNode | None = None
    ) -> None:
        """Constructor of the doubly-linked list node.

        Args:
            value: The value that the list node shall hold.
            prev_node: The predecessor node in the doubly-linked list.
            next_node: The successor node in the doubly-linked list.
        """
        self._value = value
        self._prev = prev_node
        self._next = next_node

    def get(self) -> Any:
        """Getter for the value.

        Returns:
            The value held by the list node.
        """
        return self._value

__init__(value: Any, prev_node: DLListNode | None = None, next_node: DLListNode | None = None) -> None

Constructor of the doubly-linked list node.

Parameters:

Name Type Description Default
value Any

The value that the list node shall hold.

 required
prev_node DLListNode | None

The predecessor node in the doubly-linked list.

 None
next_node DLListNode | None

The successor node in the doubly-linked list.

 None
Source code in tralda/datastructures/doubly_linked.py 
17
18
19
20
21
22
23
24
25
26
27
28
29
def __init__(
    self, value: Any, prev_node: DLListNode | None = None, next_node: DLListNode | None = None
) -> None:
    """Constructor of the doubly-linked list node.

    Args:
        value: The value that the list node shall hold.
        prev_node: The predecessor node in the doubly-linked list.
        next_node: The successor node in the doubly-linked list.
    """
    self._value = value
    self._prev = prev_node
    self._next = next_node

get() -> Any

Getter for the value.

Returns:

Type Description
Any

The value held by the list node.
Source code in tralda/datastructures/doubly_linked.py 
31
32
33
34
35
36
37
def get(self) -> Any:
    """Getter for the value.

    Returns:
        The value held by the list node.
    """
    return self._value

DLList

Doubly-linked list.

Source code in tralda/datastructures/doubly_linked.py 
 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
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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
class DLList:
    """Doubly-linked list."""

    __slots__ = ("_first", "_last", "_count")

    def __init__(self, *args: Any) -> None:
        """Constructor of the doubly-linked list.

        Args:
            args: A single value or an iterable of values to be added to the list.
        """
        self._first = None
        self._last = None
        self._count = 0
        for arg in args:
            if isinstance(arg, Iterable):
                for item in arg:
                    self.append(item)
            else:
                self.append(arg)

    def __len__(self) -> int:
        """Number of items in the list.

        Returns:
            The number of items in the list.
        """
        return self._count

    def __bool__(self) -> bool:
        """Returns whether the list is non-empty.

        Returns:
            True if the list is non-empty, False otherwise.
        """
        return self._count > 0

    def __iter__(self) -> DLListIterator:
        """Returns an iterator object for the list.

        Returns:
            An iterator for this list.
        """
        return DLListIterator(self)

    def __next__(self):
        pass

    def __getitem__(self, index: int) -> Any:
        """Access value at a specified index.

        Returns:
            The value at the specified index.
        """
        return self.node_at(index)._value

    def first(self) -> Any:
        """Return the first item in the list.

        Returns:
            The first item in the list.
        """
        return self._first._value

    def last(self) -> Any:
        """Return the last item in the list.

        Returns:
            The last item in the list.
        """
        return self._last._value

    def first_node(self) -> DLListNode:
        """Return the first list node.

        Returns:
            The first node of the list.
        """
        if self._first is None:
            raise IndexError("the list is empty")

        return self._first

    def node_at(self, index: int) -> DLListNode:
        """Return the list node at the specified index (in O(n) time).

        The index can also be negative in which case it is counted from the end (as for built-in
        Python lists).

        Returns:
            The list node at the specified index.

        Raises:
            TypeError: If 'index' is not an integer.
            IndexError: If the index is out of bounds.
        """
        if not isinstance(index, int):
            raise TypeError("index must be of type int")

        if index < (-self._count) or index >= self._count:
            raise IndexError(f"index {index} is out of bounds")

        if index < 0:
            index += self._count

        if index <= self._count // 2:
            # start from beginning
            node = self._first
            for _ in range(index):
                node = node._next

        else:
            # start from end
            node = self._last
            for _ in range(self._count - index - 1):
                node = node._prev

        return node

    def append(self, value: Any) -> DLListNode:
        """Append an item to the list.

        Args:
            value: The value to be inserted at the end of the list.

        Returns:
            The new end node of the list.
        """
        new_end = DLListNode(value, prev_node=self._last)
        if self._last:
            self._last._next = new_end

        self._last = new_end
        if not self._first:
            self._first = new_end

        self._count += 1

        return new_end

    def extend(self, iterable: Iterable) -> None:
        """Append multiple items to the list.

        Args:
            iterable: An iterable of values to be inserted at the end of the list.
        """
        for value in iterable:
            self.append(value)

    def append_left(self, value: Any) -> DLListNode:
        """Append an item to left side of the list.

        Args:
            value: The value to be inserted at the beginning of the list.

        Returns:
            The new start node of the list.
        """
        new_start = DLListNode(value, next_node=self._first)
        if self._first:
            self._first._prev = new_start

        self._first = new_start
        if not self._last:
            self._last = new_start

        self._count += 1

        return new_start

    def remove_node(self, node: DLListNode) -> None:
        """Remove an item by reference to the 'DLListNode' instance in O(1) time.

        Args:
            node: The node to be removed.
        """
        if node._prev:
            node._prev._next = node._next
        if node._next:
            node._next._prev = node._prev
        if self._first is node:
            self._first = node._next
        if self._last is node:
            self._last = node._prev

        node._prev, node._next = None, None
        self._count -= 1

    def remove(self, value: Any) -> None:
        """Remove an item by value (in O(n) time).

        Args:
            value: The value to be removed.

        Raises:
            KeyError: If the value was not found in the list.
        """
        node = self._first
        while node:
            if node._value == value:
                self.remove_node(node)
                return
            node = node._next

        raise KeyError("value {} is not in the doubly-linked list".format(value))

    def remove_range(self, index: int, length: int = None) -> None:
        """Removes a range from the index of the specified length.

        Removes the range [index, index+length) from the sequence. If no length is specified or
        index + length is out of bounds, the list gets truncated.

        Args:
            index: The start of the range to be removed.
            length: The length of the range to be removed.

        Raises:
            TypeError: If index is not an integer.
            TypeError: If length is not an integer or below 1.
        """
        if not isinstance(index, int):
            raise TypeError("index must be of type 'int'")
        elif index < 0:
            index = self._count + index

        if length is not None and (not isinstance(length, int) or length < 1):
            raise TypeError("length must be of type 'int' and >0")

        if length is None or index + length >= self._count:
            self.truncate(index)

        elif index == 0:
            self.truncate_left(length)

        else:
            cut_start = self.node_at(index)
            cut_end = self.node_at(index + length - 1)

            cut_start._prev._next = cut_end._next
            cut_end._next._prev = cut_start._prev
            cut_start._prev, cut_end._next = None, None

            self._count -= length

    def insert_right_of(self, node: DLListNode, value: Any) -> DLListNode:
        """Insert a new item right of a node of the list in O(1).

        Args:
            node: The list node next to which the item shall be inserted.
            value: The value to be inserted.

        Returns:
            The list node for the inserted value.
        """
        if node is self._last:
            new_node = self.append(value)
        else:
            new_node = DLListNode(value, prev_node=node, next_node=node._next)
            new_node._next._prev = new_node
            node._next = new_node
            self._count += 1

        return new_node

    def truncate(self, index: int) -> None:
        """Truncate all nodes starting from the specified index in O(n) time.

        Args:
            index: The index from which on the list is truncated.
        """
        if index <= 0:
            self.clear()
        else:
            new_end = self.node_at(index - 1)
            self._last = new_end
            if new_end._next:
                new_end._next._prev = None
                new_end._next = None
            self._count = index

    def truncate_left(self, n: int) -> None:
        """Truncate n nodes on the left side.

        Args:
            n: The number of items to be truncated.
        """
        if n >= self._count:
            self.clear()
        else:
            new_start = self.node_at(n)
            self._first = new_start
            if new_start._prev:
                new_start._prev._next = None
                new_start._prev = None
            self._count -= n

    def popright(self) -> Any:
        """Removes the last item of the list and returns its value.

        Returns:
            The former last item of the list which has been removed.

        Raises:
            IndexError: If the list is empty.
        """
        if self._last:
            value = self._last._value
            self.remove_node(self._last)
            return value

        raise IndexError("cannot pop from empty list")

    def popleft(self) -> Any:
        """Removes the first item of the list and returns its value.

        Returns:
            The former first item of the list which has been removed.

        Raises:
            IndexError: If the list is empty.
        """
        if self._first:
            value = self._first._value
            self.remove_node(self._first)
            return value

        raise IndexError("cannot pop from empty list")

    def clear(self) -> None:
        """Clear the list."""
        self._first = None
        self._last = None
        self._count = 0

    def sublist(self, left_node: DLListNode, right_node: DLListNode) -> list:
        """Sublist of items in the subsequence between two nodes of the list.

        Args:
            left_node: The left bound of the subsequence.
            right_node: The right bound of the subsequence.

        Returns:
            The values in the subsequence in the standard Python list.

        Raises:
            KeyError: If 'right_node' is not a successor of 'left_node' in the list.
        """
        result = []
        current = left_node

        while current:
            result.append(current._value)
            if current is right_node:
                return result

            current = current._next

        raise KeyError(
            f"{right_node} is not contained in the subsequence starting with {left_node}"
        )

    def _count_actual(self) -> int:
        """Counts the actual number of elements (for debugging purposes).

        Runs in O(n) time.

        Returns:
            The counted number of items in the list.
        """
        current = self._first
        counter = 0

        while current:
            counter += 1
            current = current._next

        return counter

__init__(*args: Any) -> None

Constructor of the doubly-linked list.

Parameters:

Name Type Description Default
args Any

A single value or an iterable of values to be added to the list.

 ()
Source code in tralda/datastructures/doubly_linked.py 
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def __init__(self, *args: Any) -> None:
    """Constructor of the doubly-linked list.

    Args:
        args: A single value or an iterable of values to be added to the list.
    """
    self._first = None
    self._last = None
    self._count = 0
    for arg in args:
        if isinstance(arg, Iterable):
            for item in arg:
                self.append(item)
        else:
            self.append(arg)

__len__() -> int

Number of items in the list.

Returns:

Type Description
int

The number of items in the list.
Source code in tralda/datastructures/doubly_linked.py 
61
62
63
64
65
66
67
def __len__(self) -> int:
    """Number of items in the list.

    Returns:
        The number of items in the list.
    """
    return self._count

__bool__() -> bool

Returns whether the list is non-empty.

Returns:

Type Description
bool

True if the list is non-empty, False otherwise.
Source code in tralda/datastructures/doubly_linked.py 
69
70
71
72
73
74
75
def __bool__(self) -> bool:
    """Returns whether the list is non-empty.

    Returns:
        True if the list is non-empty, False otherwise.
    """
    return self._count > 0

__iter__() -> DLListIterator

Returns an iterator object for the list.

Returns:

Type Description
DLListIterator

An iterator for this list.
Source code in tralda/datastructures/doubly_linked.py 
77
78
79
80
81
82
83
def __iter__(self) -> DLListIterator:
    """Returns an iterator object for the list.

    Returns:
        An iterator for this list.
    """
    return DLListIterator(self)

__getitem__(index: int) -> Any

Access value at a specified index.

Returns:

Type Description
Any

The value at the specified index.
Source code in tralda/datastructures/doubly_linked.py 
88
89
90
91
92
93
94
def __getitem__(self, index: int) -> Any:
    """Access value at a specified index.

    Returns:
        The value at the specified index.
    """
    return self.node_at(index)._value

first() -> Any

Return the first item in the list.

Returns:

Type Description
Any

The first item in the list.
Source code in tralda/datastructures/doubly_linked.py 
 96
 97
 98
 99
100
101
102
def first(self) -> Any:
    """Return the first item in the list.

    Returns:
        The first item in the list.
    """
    return self._first._value

last() -> Any

Return the last item in the list.

Returns:

Type Description
Any

The last item in the list.
Source code in tralda/datastructures/doubly_linked.py 
104
105
106
107
108
109
110
def last(self) -> Any:
    """Return the last item in the list.

    Returns:
        The last item in the list.
    """
    return self._last._value

first_node() -> DLListNode

Return the first list node.

Returns:

Type Description
DLListNode

The first node of the list.
Source code in tralda/datastructures/doubly_linked.py 
112
113
114
115
116
117
118
119
120
121
def first_node(self) -> DLListNode:
    """Return the first list node.

    Returns:
        The first node of the list.
    """
    if self._first is None:
        raise IndexError("the list is empty")

    return self._first

node_at(index: int) -> DLListNode

Return the list node at the specified index (in O(n) time).

The index can also be negative in which case it is counted from the end (as for built-in Python lists).

Returns:

Type Description
DLListNode

The list node at the specified index.

Raises:

Type Description
TypeError

If 'index' is not an integer.
IndexError

If the index is out of bounds.
Source code in tralda/datastructures/doubly_linked.py 
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
def node_at(self, index: int) -> DLListNode:
    """Return the list node at the specified index (in O(n) time).

    The index can also be negative in which case it is counted from the end (as for built-in
    Python lists).

    Returns:
        The list node at the specified index.

    Raises:
        TypeError: If 'index' is not an integer.
        IndexError: If the index is out of bounds.
    """
    if not isinstance(index, int):
        raise TypeError("index must be of type int")

    if index < (-self._count) or index >= self._count:
        raise IndexError(f"index {index} is out of bounds")

    if index < 0:
        index += self._count

    if index <= self._count // 2:
        # start from beginning
        node = self._first
        for _ in range(index):
            node = node._next

    else:
        # start from end
        node = self._last
        for _ in range(self._count - index - 1):
            node = node._prev

    return node

append(value: Any) -> DLListNode

Append an item to the list.

Parameters:

Name Type Description Default
value Any

The value to be inserted at the end of the list.

 required

Returns:

Type Description
DLListNode

The new end node of the list.
Source code in tralda/datastructures/doubly_linked.py 
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
def append(self, value: Any) -> DLListNode:
    """Append an item to the list.

    Args:
        value: The value to be inserted at the end of the list.

    Returns:
        The new end node of the list.
    """
    new_end = DLListNode(value, prev_node=self._last)
    if self._last:
        self._last._next = new_end

    self._last = new_end
    if not self._first:
        self._first = new_end

    self._count += 1

    return new_end

extend(iterable: Iterable) -> None

Append multiple items to the list.

Parameters:

Name Type Description Default
iterable Iterable

An iterable of values to be inserted at the end of the list.

 required
Source code in tralda/datastructures/doubly_linked.py 
180
181
182
183
184
185
186
187
def extend(self, iterable: Iterable) -> None:
    """Append multiple items to the list.

    Args:
        iterable: An iterable of values to be inserted at the end of the list.
    """
    for value in iterable:
        self.append(value)

append_left(value: Any) -> DLListNode

Append an item to left side of the list.

Parameters:

Name Type Description Default
value Any

The value to be inserted at the beginning of the list.

 required

Returns:

Type Description
DLListNode

The new start node of the list.
Source code in tralda/datastructures/doubly_linked.py 
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
def append_left(self, value: Any) -> DLListNode:
    """Append an item to left side of the list.

    Args:
        value: The value to be inserted at the beginning of the list.

    Returns:
        The new start node of the list.
    """
    new_start = DLListNode(value, next_node=self._first)
    if self._first:
        self._first._prev = new_start

    self._first = new_start
    if not self._last:
        self._last = new_start

    self._count += 1

    return new_start

remove_node(node: DLListNode) -> None

Remove an item by reference to the 'DLListNode' instance in O(1) time.

Parameters:

Name Type Description Default
node DLListNode

The node to be removed.

 required
Source code in tralda/datastructures/doubly_linked.py 
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
def remove_node(self, node: DLListNode) -> None:
    """Remove an item by reference to the 'DLListNode' instance in O(1) time.

    Args:
        node: The node to be removed.
    """
    if node._prev:
        node._prev._next = node._next
    if node._next:
        node._next._prev = node._prev
    if self._first is node:
        self._first = node._next
    if self._last is node:
        self._last = node._prev

    node._prev, node._next = None, None
    self._count -= 1

remove(value: Any) -> None

Remove an item by value (in O(n) time).

Parameters:

Name Type Description Default
value Any

The value to be removed.

 required

Raises:

Type Description
KeyError

If the value was not found in the list.
Source code in tralda/datastructures/doubly_linked.py 
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
def remove(self, value: Any) -> None:
    """Remove an item by value (in O(n) time).

    Args:
        value: The value to be removed.

    Raises:
        KeyError: If the value was not found in the list.
    """
    node = self._first
    while node:
        if node._value == value:
            self.remove_node(node)
            return
        node = node._next

    raise KeyError("value {} is not in the doubly-linked list".format(value))

remove_range(index: int, length: int = None) -> None

Removes a range from the index of the specified length.

Removes the range [index, index+length) from the sequence. If no length is specified or index + length is out of bounds, the list gets truncated.

Parameters:

Name Type Description Default
index int

The start of the range to be removed.

 required
length int

The length of the range to be removed.

 None

Raises:

Type Description
TypeError

If index is not an integer.
TypeError

If length is not an integer or below 1.
Source code in tralda/datastructures/doubly_linked.py 
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
def remove_range(self, index: int, length: int = None) -> None:
    """Removes a range from the index of the specified length.

    Removes the range [index, index+length) from the sequence. If no length is specified or
    index + length is out of bounds, the list gets truncated.

    Args:
        index: The start of the range to be removed.
        length: The length of the range to be removed.

    Raises:
        TypeError: If index is not an integer.
        TypeError: If length is not an integer or below 1.
    """
    if not isinstance(index, int):
        raise TypeError("index must be of type 'int'")
    elif index < 0:
        index = self._count + index

    if length is not None and (not isinstance(length, int) or length < 1):
        raise TypeError("length must be of type 'int' and >0")

    if length is None or index + length >= self._count:
        self.truncate(index)

    elif index == 0:
        self.truncate_left(length)

    else:
        cut_start = self.node_at(index)
        cut_end = self.node_at(index + length - 1)

        cut_start._prev._next = cut_end._next
        cut_end._next._prev = cut_start._prev
        cut_start._prev, cut_end._next = None, None

        self._count -= length

insert_right_of(node: DLListNode, value: Any) -> DLListNode

Insert a new item right of a node of the list in O(1).

Parameters:

Name Type Description Default
node DLListNode

The list node next to which the item shall be inserted.

 required
value Any

The value to be inserted.

 required

Returns:

Type Description
DLListNode

The list node for the inserted value.
Source code in tralda/datastructures/doubly_linked.py 
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
def insert_right_of(self, node: DLListNode, value: Any) -> DLListNode:
    """Insert a new item right of a node of the list in O(1).

    Args:
        node: The list node next to which the item shall be inserted.
        value: The value to be inserted.

    Returns:
        The list node for the inserted value.
    """
    if node is self._last:
        new_node = self.append(value)
    else:
        new_node = DLListNode(value, prev_node=node, next_node=node._next)
        new_node._next._prev = new_node
        node._next = new_node
        self._count += 1

    return new_node

truncate(index: int) -> None

Truncate all nodes starting from the specified index in O(n) time.

Parameters:

Name Type Description Default
index int

The index from which on the list is truncated.

 required
Source code in tralda/datastructures/doubly_linked.py 
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
def truncate(self, index: int) -> None:
    """Truncate all nodes starting from the specified index in O(n) time.

    Args:
        index: The index from which on the list is truncated.
    """
    if index <= 0:
        self.clear()
    else:
        new_end = self.node_at(index - 1)
        self._last = new_end
        if new_end._next:
            new_end._next._prev = None
            new_end._next = None
        self._count = index

truncate_left(n: int) -> None

Truncate n nodes on the left side.

Parameters:

Name Type Description Default
n int

The number of items to be truncated.

 required
Source code in tralda/datastructures/doubly_linked.py 
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
def truncate_left(self, n: int) -> None:
    """Truncate n nodes on the left side.

    Args:
        n: The number of items to be truncated.
    """
    if n >= self._count:
        self.clear()
    else:
        new_start = self.node_at(n)
        self._first = new_start
        if new_start._prev:
            new_start._prev._next = None
            new_start._prev = None
        self._count -= n

popright() -> Any

Removes the last item of the list and returns its value.

Returns:

Type Description
Any

The former last item of the list which has been removed.

Raises:

Type Description
IndexError

If the list is empty.
Source code in tralda/datastructures/doubly_linked.py 
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
def popright(self) -> Any:
    """Removes the last item of the list and returns its value.

    Returns:
        The former last item of the list which has been removed.

    Raises:
        IndexError: If the list is empty.
    """
    if self._last:
        value = self._last._value
        self.remove_node(self._last)
        return value

    raise IndexError("cannot pop from empty list")

popleft() -> Any

Removes the first item of the list and returns its value.

Returns:

Type Description
Any

The former first item of the list which has been removed.

Raises:

Type Description
IndexError

If the list is empty.
Source code in tralda/datastructures/doubly_linked.py 
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
def popleft(self) -> Any:
    """Removes the first item of the list and returns its value.

    Returns:
        The former first item of the list which has been removed.

    Raises:
        IndexError: If the list is empty.
    """
    if self._first:
        value = self._first._value
        self.remove_node(self._first)
        return value

    raise IndexError("cannot pop from empty list")

clear() -> None

Clear the list.

Source code in tralda/datastructures/doubly_linked.py 
368
369
370
371
372
def clear(self) -> None:
    """Clear the list."""
    self._first = None
    self._last = None
    self._count = 0

sublist(left_node: DLListNode, right_node: DLListNode) -> list

Sublist of items in the subsequence between two nodes of the list.

Parameters:

Name Type Description Default
left_node DLListNode

The left bound of the subsequence.

 required
right_node DLListNode

The right bound of the subsequence.

 required

Returns:

Type Description
list

The values in the subsequence in the standard Python list.

Raises:

Type Description
KeyError

If 'right_node' is not a successor of 'left_node' in the list.
Source code in tralda/datastructures/doubly_linked.py 
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
def sublist(self, left_node: DLListNode, right_node: DLListNode) -> list:
    """Sublist of items in the subsequence between two nodes of the list.

    Args:
        left_node: The left bound of the subsequence.
        right_node: The right bound of the subsequence.

    Returns:
        The values in the subsequence in the standard Python list.

    Raises:
        KeyError: If 'right_node' is not a successor of 'left_node' in the list.
    """
    result = []
    current = left_node

    while current:
        result.append(current._value)
        if current is right_node:
            return result

        current = current._next

    raise KeyError(
        f"{right_node} is not contained in the subsequence starting with {left_node}"
    )

Dynamic partition and connectivity data structures

Partition

Dynamic partition implementation.

Source code in tralda/datastructures/partition.py 
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 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
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
class Partition:
    """Dynamic partition implementation."""

    def __init__(self, iterable: Iterable) -> None:
        """Constructor of the partition.

        Args:
            iterable: An iterable of iterables defining the initial partition.
        """
        self._partition = DLList()
        self._item2set: dict[Any, DLListNode] = {}

        for set_ in iterable:
            dll_node = self._partition.append(set(set_))
            for x in set_:
                self._item2set[x] = dll_node

    def __len__(self) -> int:
        """Current number of sets in the partition.

        Returns:
            The current number of sets in the partition.
        """
        return len(self._partition)

    def __iter__(self) -> PartitionIterator:
        """An iterator for the dynamic partition.

        Returns:
            An iterator for this partition.
        """
        return PartitionIterator(self)

    def __next__(self) -> None:
        raise TypeError(
            "'Partition' object is not an iterator; use iter() to obtain a 'PartitionIterator'"
        )

    def in_same_set(self, x: Any, y: Any) -> bool:
        """Check whether two items are in the same set of the partition.

        Args:
            x: Item 1.
            y: Item 2.

        Returns:
            True if x and y are in the same set of the partition, False otherwise.

        Raises:
            KeyError: If x or y is not an item in the partition.
        """
        try:
            return self._item2set[x] is self._item2set[y]
        except KeyError:
            if x not in self._item2set:
                raise KeyError(f"{x} is not an item in the partition")
            else:
                raise KeyError(f"{y} is not an item in the partition")

    def separated_xy_z(self, x: Any, y: Any, z: Any) -> bool:
        """Check whether two items are in the same set but in a different set than the third.

        Args:
            x: Item 1.
            y: Item 2.
            z: Item 3.

        Returns:
            True if x and y are in the same set of the partition and z is in a different one, False
                otherwise.

        Raises:
            KeyError: If x, y, or z is not an item in the partition.
        """
        try:
            sx = self._item2set[x]
        except KeyError:
            raise KeyError(f"{x} is not an item in the partition")

        try:
            sy = self._item2set[y]
        except KeyError:
            raise KeyError(f"{y} is not an item in the partition")

        try:
            sz = self._item2set[z]
        except KeyError:
            raise KeyError(f"{z} is not an item in the partition")

        return sx is sy and sx is not sz

    def merge(self, repr1: Any, repr2: Any) -> set[Any]:
        """Merge two sets of the partition based on arbitrary representatives.

        The merging is done efficiently by adding the elements of the smaller set to the bigger set.
        That way, each element is moved at most log(n) times into a new set.

        Args:
            repr1: Arbitrary representative of the first set.
            repr2: Arbitrary representative of the second set.

        Raises:
            KeyError: If 'repr1' or 'repr2' is not an item in the partition.

        Returns:
            The smaller of the original two sets that now have been merged. When both sets have
                equal size, the set containing ``repr1`` is returned.
        """
        try:
            set1 = self._item2set[repr1]
        except KeyError:
            raise KeyError(f"{repr1} is not an item in the partition")

        try:
            set2 = self._item2set[repr2]
        except KeyError:
            raise KeyError(f"{repr2} is not an item in the partition")

        if set1 is set2:
            return set()

        # ensure that set1 is smaller
        if len(set2._value) < len(set1._value):
            set1, set2 = set2, set1

        for x in set1._value:
            self._item2set[x] = set2

        # the bigger set gets extended
        set2._value |= set1._value

        self._partition.remove_node(set1)

        return set1._value

__init__(iterable: Iterable) -> None

Constructor of the partition.

Parameters:

Name Type Description Default
iterable Iterable

An iterable of iterables defining the initial partition.

 required
Source code in tralda/datastructures/partition.py 
19
20
21
22
23
24
25
26
27
28
29
30
31
def __init__(self, iterable: Iterable) -> None:
    """Constructor of the partition.

    Args:
        iterable: An iterable of iterables defining the initial partition.
    """
    self._partition = DLList()
    self._item2set: dict[Any, DLListNode] = {}

    for set_ in iterable:
        dll_node = self._partition.append(set(set_))
        for x in set_:
            self._item2set[x] = dll_node

__len__() -> int

Current number of sets in the partition.

Returns:

Type Description
int

The current number of sets in the partition.
Source code in tralda/datastructures/partition.py 
33
34
35
36
37
38
39
def __len__(self) -> int:
    """Current number of sets in the partition.

    Returns:
        The current number of sets in the partition.
    """
    return len(self._partition)

__iter__() -> PartitionIterator

An iterator for the dynamic partition.

Returns:

Type Description
PartitionIterator

An iterator for this partition.
Source code in tralda/datastructures/partition.py 
41
42
43
44
45
46
47
def __iter__(self) -> PartitionIterator:
    """An iterator for the dynamic partition.

    Returns:
        An iterator for this partition.
    """
    return PartitionIterator(self)

in_same_set(x: Any, y: Any) -> bool

Check whether two items are in the same set of the partition.

Parameters:

Name Type Description Default
x Any

Item 1.

 required
y Any

Item 2.

 required

Returns:

Type Description
bool

True if x and y are in the same set of the partition, False otherwise.

Raises:

Type Description
KeyError

If x or y is not an item in the partition.
Source code in tralda/datastructures/partition.py 
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
def in_same_set(self, x: Any, y: Any) -> bool:
    """Check whether two items are in the same set of the partition.

    Args:
        x: Item 1.
        y: Item 2.

    Returns:
        True if x and y are in the same set of the partition, False otherwise.

    Raises:
        KeyError: If x or y is not an item in the partition.
    """
    try:
        return self._item2set[x] is self._item2set[y]
    except KeyError:
        if x not in self._item2set:
            raise KeyError(f"{x} is not an item in the partition")
        else:
            raise KeyError(f"{y} is not an item in the partition")

separated_xy_z(x: Any, y: Any, z: Any) -> bool

Check whether two items are in the same set but in a different set than the third.

Parameters:

Name Type Description Default
x Any

Item 1.

 required
y Any

Item 2.

 required
z Any

Item 3.

 required

Returns:

Type Description
bool

True if x and y are in the same set of the partition and z is in a different one, False otherwise.

Raises:

Type Description
KeyError

If x, y, or z is not an item in the partition.
Source code in tralda/datastructures/partition.py 
 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
def separated_xy_z(self, x: Any, y: Any, z: Any) -> bool:
    """Check whether two items are in the same set but in a different set than the third.

    Args:
        x: Item 1.
        y: Item 2.
        z: Item 3.

    Returns:
        True if x and y are in the same set of the partition and z is in a different one, False
            otherwise.

    Raises:
        KeyError: If x, y, or z is not an item in the partition.
    """
    try:
        sx = self._item2set[x]
    except KeyError:
        raise KeyError(f"{x} is not an item in the partition")

    try:
        sy = self._item2set[y]
    except KeyError:
        raise KeyError(f"{y} is not an item in the partition")

    try:
        sz = self._item2set[z]
    except KeyError:
        raise KeyError(f"{z} is not an item in the partition")

    return sx is sy and sx is not sz

merge(repr1: Any, repr2: Any) -> set[Any]

Merge two sets of the partition based on arbitrary representatives.

The merging is done efficiently by adding the elements of the smaller set to the bigger set. That way, each element is moved at most log(n) times into a new set.

Parameters:

Name Type Description Default
repr1 Any

Arbitrary representative of the first set.

 required
repr2 Any

Arbitrary representative of the second set.

 required

Raises:

Type Description
KeyError

If 'repr1' or 'repr2' is not an item in the partition.

Returns:

Type Description
set[Any]

The smaller of the original two sets that now have been merged. When both sets have equal size, the set containing repr1 is returned.
Source code in tralda/datastructures/partition.py 
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
def merge(self, repr1: Any, repr2: Any) -> set[Any]:
    """Merge two sets of the partition based on arbitrary representatives.

    The merging is done efficiently by adding the elements of the smaller set to the bigger set.
    That way, each element is moved at most log(n) times into a new set.

    Args:
        repr1: Arbitrary representative of the first set.
        repr2: Arbitrary representative of the second set.

    Raises:
        KeyError: If 'repr1' or 'repr2' is not an item in the partition.

    Returns:
        The smaller of the original two sets that now have been merged. When both sets have
            equal size, the set containing ``repr1`` is returned.
    """
    try:
        set1 = self._item2set[repr1]
    except KeyError:
        raise KeyError(f"{repr1} is not an item in the partition")

    try:
        set2 = self._item2set[repr2]
    except KeyError:
        raise KeyError(f"{repr2} is not an item in the partition")

    if set1 is set2:
        return set()

    # ensure that set1 is smaller
    if len(set2._value) < len(set1._value):
        set1, set2 = set2, set1

    for x in set1._value:
        self._item2set[x] = set2

    # the bigger set gets extended
    set2._value |= set1._value

    self._partition.remove_node(set1)

    return set1._value

HDTGraph

Undirected graph datastructure for poly-logarithmic connectivity queries.

Implementation of the poly-logarithmic dynamic graph structure (HDT datastructure).

References
  1. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, July 2001.
Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
class HDTGraph:
    """Undirected graph datastructure for poly-logarithmic connectivity queries.

    Implementation of the poly-logarithmic dynamic graph structure (HDT datastructure).

    References:
        1. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic
           fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and
           biconnectivity. J. ACM, 48(4):723-760, July 2001.
    """

    def __init__(self) -> None:
        """Constructor of the undirected graph for poly-logarithmic connectivity queries."""
        self._levels: list[_Level] = [_Level(0)]
        self._edges: dict[tuple[Any, Any], _Edge] = dict()

    def get_nodes(self) -> Iterator[Any]:
        """Generator for the nodes in the graph.

        Yields:
            The nodes in the graph.
        """
        yield from self._levels[0].node2active_occurrence.keys()

    def get_edges(self) -> Iterator[tuple[Any, Any]]:
        """Generator for the edges in the graph.

        Yields:
            The edges in the graph.
        """
        yield from self._edges.keys()

    def has_node(self, node: Any) -> bool:
        """Determine whether a node is in the graph.

        Args:
            node: The node for which to check if it is in the graph.

        Return:
            Whether the node is contained in the graph.
        """
        return node in self._levels[0].node2active_occurrence

    def has_edge(self, u: Any, v: Any) -> bool:
        """Determine whether an edge is in the graph.

        Args:
            u: The first node.
            v: The second node.

        Returns:
            Whether the graph has the undirected edge (u, v).
        """
        return sort_edge(u, v) in self._edges

    def connected(self, u: Any, v: Any, level: int = 0) -> bool:
        """Determine in O(log n) whether u and v are connected in the graph.

        Args:
            u: The first node.
            v: The second node.
            level: If provided, check for connectivity on that level. The default is 0 which checks
                for connectivity in the full current graph.

        Returns:
            Whether u and v are connected by a path in the graph.
        """
        return self._levels[level].connected(u, v)

    def get_component(self, node: Any) -> ETTree:
        """Return the connected component (ETT) of a given value.

        Args:
            node: A node in the graph.

        Returns:
            The connected component that contains the node.

        Raises:
            KeyError: If the node is not in the graph.
        """
        active_occurrence = self._levels[0].node2active_occurrence.get(node)

        if active_occurrence is None:
            raise KeyError(f"{node} is not a node in the graph")

        return active_occurrence.get_root().ett if active_occurrence is not None else None

    def insert_node(self, node: Any) -> None:
        """Insert a loose node into the graph.

        Args:
            node: The node to add to the graph.

        Raises:
            KeyError: If the node is already in the graph.
        """
        if node in self._levels[0].node2active_occurrence:
            raise KeyError(f"node {node} is already in the graph")

        self._levels[0].add_node(node)

    def insert_edge(self, u: Any, v: Any) -> None:
        """Insert an edge (u, v) into the graph.

        Args:
            u: The first node.
            v: The second node.
        """
        u, v = sort_edge(u, v)
        e = (u, v)

        if e in self._edges:
            return

        if self.connected(u, v):
            new_edge = _Edge(e, is_tree_edge=False)  # new edge on level 0
            self._levels[0].add_nontree_edge(new_edge)  # append nontree edge to u and v
        else:
            new_edge = _Edge(e, is_tree_edge=True)  # new edge on level 0
            self._levels[0].connect(u, v, edge=new_edge)  # connect + append tree edge to u and v

        self._edges[e] = new_edge

    def delete_edge(self, u: Any, v: Any) -> None:
        """Delete an edge from the graph.

        Args:
            u: The first endpoint of the edge.
            v: The second endpoint of the edge.
        """
        u, v = sort_edge(u, v)
        edge = self._edges.get((u, v))

        if edge is None:  # edge does not exist
            return

        self._edges.pop(edge.e)
        level = self._levels[edge.level]

        # e is not a tree edge --> simply delete e
        if not edge.is_tree_edge:
            if u in level.node2active_occurrence:
                level.node2nontree_edges[u].remove_node(edge.dllist_entries[0])
            if v in level.node2active_occurrence:
                level.node2nontree_edges[v].remove_node(edge.dllist_entries[1])

        # e is a tree edge --> search for replacement
        else:
            level.node2tree_edges[u].remove_node(edge.dllist_entries[0])
            level.node2tree_edges[v].remove_node(edge.dllist_entries[1])

            # remove the edge on all levels <= l(e)
            for i in range(level.index, -1, -1):
                self._levels[i].cut(u, v)

            self._replace(u, v, level)

    def add_loose_tree(self, tree: Tree) -> None:
        """Add the edges of a (rooted) tree as undirected edges.

        The elements of the 'Tree' instance must not yet be nodes in the graph.

        Args:
            tree: The tree whose nodes and edges shall be added to the graph.

        Raises:
            TypeError: If tree is not an instance of type Tree.
        """
        if not isinstance(tree, Tree):
            raise TypeError("instance of type 'Tree' required")

        # empty tree --> nothing to add
        if not tree.root:
            return

        node2active_occurrence = self._levels[0].node2active_occurrence
        node2tree_edges = self._levels[0].node2tree_edges
        edge2occurrences = self._levels[0].edge2occurrences

        ett = ETTree()

        # construct the Euler Tour tree
        previous_ett_node = None
        for node in tree.euler_generator():
            if node not in node2active_occurrence:
                ett_node = self._levels[0].add_loose_node(node)
            else:
                ett_node = ETTreeNode(node, active=False)

            ett.add_right_child_and_rebalance(previous_ett_node, ett_node, edge2occurrences)
            previous_ett_node = ett_node

        # create and add the _Edge instances (which are already represented in the ET tree)
        for node in tree.preorder():
            if not node.parent:
                continue

            e = sort_edge(node, node.parent)
            edge = _Edge(e, level=0, is_tree_edge=True)
            edge.dllist_entries = (
                node2tree_edges[e[0]].append(edge),
                node2tree_edges[e[1]].append(edge),
            )
            self._edges[e] = edge

        # the root stores a reference to the ETTree instance
        ett.root.ett = ett

        # finally, add the new component to the forest
        self._levels[0].forest.add(ett)

    def is_connected(self) -> bool:
        """Determine if the graph is connected (on level 0).

        Returns:
            Whether the graph is connected.
        """
        return len(self._levels[0].forest) == 1

    def component_iterator(self, representative: Any) -> Iterator[Any]:
        """Iterator over the connected component of a given value.

        Args:
            representative: A representative node of the component.

        Yields:
            The nodes in the connected component.
        """
        ett = self.get_component(representative)

        if ett is None:
            raise KeyError(f"representative node {representative} is not contained in the graph")

        for occ in ett:
            if occ.active:
                yield occ.key

    def print_ett_forest(self, level: str | int = "all") -> None:
        """Print Euler tour of the spanning forest.

        Intended for testing purpose.

        Args:
            level: Level of the ETT spanning forest to be printed. The default is "all" in which
                case all levels are printed.
        """
        if level == "all":
            for level_i in self._levels:
                print(f"----- Level {level_i.index} -----")
                for ett in level_i.forest:
                    print([occ.key for occ in ett], ett.num_active_occurrences)
        elif isinstance(level, int):
            for ett in self._levels[level].forest:
                print([occ.key for occ in ett], ett.num_active_occurrences)
        else:
            raise ValueError(f"invalid level: {level} of type {type(level)}")

    def _replace(self, u: Any, v: Any, level: _Level) -> None:
        """Search for an replacement edge to reconnect u and v on the given level.

        Args:
            u: The first node.
            v: The second node.
            level: The level on which to search for a replacement edge of (u, v).
        """
        ett1 = level.node2active_occurrence[u].get_root().ett
        ett2 = level.node2active_occurrence[v].get_root().ett

        if ett1.num_active_occurrences <= ett2.num_active_occurrences:
            smaller_ett = ett1
            root2 = ett2.root
        else:
            smaller_ett = ett2
            root2 = ett1.root

        self._raise_tree_edges(smaller_ett, level)
        found = None

        for occ in smaller_ett:
            if not occ.active:
                continue

            nontree_edges = level.node2nontree_edges[occ.key]

            while nontree_edges:
                edge = nontree_edges.popleft()

                # also remove the non-tree edge at the other node
                i = 1 - int(edge.e[0] != occ.key)
                other_end = edge.e[i]
                level.node2nontree_edges[other_end].remove_node(edge.dllist_entries[i])

                # edge is a replacement edge
                if (other_end in level.node2active_occurrence) and (
                    level.node2active_occurrence[other_end].get_root() is root2
                ):
                    found = edge
                    break

                # edge is not a replacement edge --> raise to next level
                edge.level += 1
                self._levels[level.index + 1].add_nontree_edge(edge)

            if found:
                break

        if found:
            found.is_tree_edge = True
            found.dllist_entries = None
            u, v = found.e[0], found.e[1]
            level.connect(u, v, found)

            # reconnect on all lower levels
            for i in range(level.index - 1, -1, -1):
                self._levels[i].connect(u, v)

        # no replament edge found --> try on lower levels if available
        elif level.index > 0:
            self._replace(u, v, self._levels[level.index - 1])

    def _raise_tree_edges(self, ett: ETTree, level: _Level) -> None:
        """Raise all tree edges of an Euler Tour tree (ETT) to the next level.

        Args:
            ett: The ETT whose edges shall be raised up a level.
            level: The current level of the edges represented by the ETT.
        """
        # create new level if necessary
        if level.index >= len(self._levels) - 1:
            self._levels.append(_Level(len(self._levels)))

        for occ in ett:
            if not occ.active:
                continue

            tree_edges = level.node2tree_edges[occ.key]

            for edge in tree_edges:
                if edge.level == level.index:
                    edge.level += 1
                    u, v = edge.e[0], edge.e[1]
                    self._levels[level.index + 1].connect(u, v, edge=edge)

            # remove all tree edges (of this ET tree) on this level
            tree_edges.clear()

__init__() -> None

Constructor of the undirected graph for poly-logarithmic connectivity queries.

Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
219
220
221
222
def __init__(self) -> None:
    """Constructor of the undirected graph for poly-logarithmic connectivity queries."""
    self._levels: list[_Level] = [_Level(0)]
    self._edges: dict[tuple[Any, Any], _Edge] = dict()

get_nodes() -> Iterator[Any]

Generator for the nodes in the graph.

Yields:

Type Description
Any

The nodes in the graph.
Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
224
225
226
227
228
229
230
def get_nodes(self) -> Iterator[Any]:
    """Generator for the nodes in the graph.

    Yields:
        The nodes in the graph.
    """
    yield from self._levels[0].node2active_occurrence.keys()

get_edges() -> Iterator[tuple[Any, Any]]

Generator for the edges in the graph.

Yields:

Type Description
tuple[Any, Any]

The edges in the graph.
Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
232
233
234
235
236
237
238
def get_edges(self) -> Iterator[tuple[Any, Any]]:
    """Generator for the edges in the graph.

    Yields:
        The edges in the graph.
    """
    yield from self._edges.keys()

has_node(node: Any) -> bool

Determine whether a node is in the graph.

Parameters:

Name Type Description Default
node Any

The node for which to check if it is in the graph.

 required
Return

Whether the node is contained in the graph.

Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
240
241
242
243
244
245
246
247
248
249
def has_node(self, node: Any) -> bool:
    """Determine whether a node is in the graph.

    Args:
        node: The node for which to check if it is in the graph.

    Return:
        Whether the node is contained in the graph.
    """
    return node in self._levels[0].node2active_occurrence

has_edge(u: Any, v: Any) -> bool

Determine whether an edge is in the graph.

Parameters:

Name Type Description Default
u Any

The first node.

 required
v Any

The second node.

 required

Returns:

Type Description
bool

Whether the graph has the undirected edge (u, v).
Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
251
252
253
254
255
256
257
258
259
260
261
def has_edge(self, u: Any, v: Any) -> bool:
    """Determine whether an edge is in the graph.

    Args:
        u: The first node.
        v: The second node.

    Returns:
        Whether the graph has the undirected edge (u, v).
    """
    return sort_edge(u, v) in self._edges

connected(u: Any, v: Any, level: int = 0) -> bool

Determine in O(log n) whether u and v are connected in the graph.

Parameters:

Name Type Description Default
u Any

The first node.

 required
v Any

The second node.

 required
level int

If provided, check for connectivity on that level. The default is 0 which checks for connectivity in the full current graph.

 0

Returns:

Type Description
bool

Whether u and v are connected by a path in the graph.
Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
263
264
265
266
267
268
269
270
271
272
273
274
275
def connected(self, u: Any, v: Any, level: int = 0) -> bool:
    """Determine in O(log n) whether u and v are connected in the graph.

    Args:
        u: The first node.
        v: The second node.
        level: If provided, check for connectivity on that level. The default is 0 which checks
            for connectivity in the full current graph.

    Returns:
        Whether u and v are connected by a path in the graph.
    """
    return self._levels[level].connected(u, v)

get_component(node: Any) -> ETTree

Return the connected component (ETT) of a given value.

Parameters:

Name Type Description Default
node Any

A node in the graph.

 required

Returns:

Type Description
ETTree

The connected component that contains the node.

Raises:

Type Description
KeyError

If the node is not in the graph.
Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
def get_component(self, node: Any) -> ETTree:
    """Return the connected component (ETT) of a given value.

    Args:
        node: A node in the graph.

    Returns:
        The connected component that contains the node.

    Raises:
        KeyError: If the node is not in the graph.
    """
    active_occurrence = self._levels[0].node2active_occurrence.get(node)

    if active_occurrence is None:
        raise KeyError(f"{node} is not a node in the graph")

    return active_occurrence.get_root().ett if active_occurrence is not None else None

insert_node(node: Any) -> None

Insert a loose node into the graph.

Parameters:

Name Type Description Default
node Any

The node to add to the graph.

 required

Raises:

Type Description
KeyError

If the node is already in the graph.
Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
296
297
298
299
300
301
302
303
304
305
306
307
308
def insert_node(self, node: Any) -> None:
    """Insert a loose node into the graph.

    Args:
        node: The node to add to the graph.

    Raises:
        KeyError: If the node is already in the graph.
    """
    if node in self._levels[0].node2active_occurrence:
        raise KeyError(f"node {node} is already in the graph")

    self._levels[0].add_node(node)

insert_edge(u: Any, v: Any) -> None

Insert an edge (u, v) into the graph.

Parameters:

Name Type Description Default
u Any

The first node.

 required
v Any

The second node.

 required
Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
def insert_edge(self, u: Any, v: Any) -> None:
    """Insert an edge (u, v) into the graph.

    Args:
        u: The first node.
        v: The second node.
    """
    u, v = sort_edge(u, v)
    e = (u, v)

    if e in self._edges:
        return

    if self.connected(u, v):
        new_edge = _Edge(e, is_tree_edge=False)  # new edge on level 0
        self._levels[0].add_nontree_edge(new_edge)  # append nontree edge to u and v
    else:
        new_edge = _Edge(e, is_tree_edge=True)  # new edge on level 0
        self._levels[0].connect(u, v, edge=new_edge)  # connect + append tree edge to u and v

    self._edges[e] = new_edge

delete_edge(u: Any, v: Any) -> None

Delete an edge from the graph.

Parameters:

Name Type Description Default
u Any

The first endpoint of the edge.

 required
v Any

The second endpoint of the edge.

 required
Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
def delete_edge(self, u: Any, v: Any) -> None:
    """Delete an edge from the graph.

    Args:
        u: The first endpoint of the edge.
        v: The second endpoint of the edge.
    """
    u, v = sort_edge(u, v)
    edge = self._edges.get((u, v))

    if edge is None:  # edge does not exist
        return

    self._edges.pop(edge.e)
    level = self._levels[edge.level]

    # e is not a tree edge --> simply delete e
    if not edge.is_tree_edge:
        if u in level.node2active_occurrence:
            level.node2nontree_edges[u].remove_node(edge.dllist_entries[0])
        if v in level.node2active_occurrence:
            level.node2nontree_edges[v].remove_node(edge.dllist_entries[1])

    # e is a tree edge --> search for replacement
    else:
        level.node2tree_edges[u].remove_node(edge.dllist_entries[0])
        level.node2tree_edges[v].remove_node(edge.dllist_entries[1])

        # remove the edge on all levels <= l(e)
        for i in range(level.index, -1, -1):
            self._levels[i].cut(u, v)

        self._replace(u, v, level)

add_loose_tree(tree: Tree) -> None

Add the edges of a (rooted) tree as undirected edges.

The elements of the 'Tree' instance must not yet be nodes in the graph.

Parameters:

Name Type Description Default
tree Tree

The tree whose nodes and edges shall be added to the graph.

 required

Raises:

Type Description
TypeError

If tree is not an instance of type Tree.
Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
def add_loose_tree(self, tree: Tree) -> None:
    """Add the edges of a (rooted) tree as undirected edges.

    The elements of the 'Tree' instance must not yet be nodes in the graph.

    Args:
        tree: The tree whose nodes and edges shall be added to the graph.

    Raises:
        TypeError: If tree is not an instance of type Tree.
    """
    if not isinstance(tree, Tree):
        raise TypeError("instance of type 'Tree' required")

    # empty tree --> nothing to add
    if not tree.root:
        return

    node2active_occurrence = self._levels[0].node2active_occurrence
    node2tree_edges = self._levels[0].node2tree_edges
    edge2occurrences = self._levels[0].edge2occurrences

    ett = ETTree()

    # construct the Euler Tour tree
    previous_ett_node = None
    for node in tree.euler_generator():
        if node not in node2active_occurrence:
            ett_node = self._levels[0].add_loose_node(node)
        else:
            ett_node = ETTreeNode(node, active=False)

        ett.add_right_child_and_rebalance(previous_ett_node, ett_node, edge2occurrences)
        previous_ett_node = ett_node

    # create and add the _Edge instances (which are already represented in the ET tree)
    for node in tree.preorder():
        if not node.parent:
            continue

        e = sort_edge(node, node.parent)
        edge = _Edge(e, level=0, is_tree_edge=True)
        edge.dllist_entries = (
            node2tree_edges[e[0]].append(edge),
            node2tree_edges[e[1]].append(edge),
        )
        self._edges[e] = edge

    # the root stores a reference to the ETTree instance
    ett.root.ett = ett

    # finally, add the new component to the forest
    self._levels[0].forest.add(ett)

is_connected() -> bool

Determine if the graph is connected (on level 0).

Returns:

Type Description
bool

Whether the graph is connected.
Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
420
421
422
423
424
425
426
def is_connected(self) -> bool:
    """Determine if the graph is connected (on level 0).

    Returns:
        Whether the graph is connected.
    """
    return len(self._levels[0].forest) == 1

component_iterator(representative: Any) -> Iterator[Any]

Iterator over the connected component of a given value.

Parameters:

Name Type Description Default
representative Any

A representative node of the component.

 required

Yields:

Type Description
Any

The nodes in the connected component.
Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
def component_iterator(self, representative: Any) -> Iterator[Any]:
    """Iterator over the connected component of a given value.

    Args:
        representative: A representative node of the component.

    Yields:
        The nodes in the connected component.
    """
    ett = self.get_component(representative)

    if ett is None:
        raise KeyError(f"representative node {representative} is not contained in the graph")

    for occ in ett:
        if occ.active:
            yield occ.key

print_ett_forest(level: str | int = 'all') -> None

Print Euler tour of the spanning forest.

Intended for testing purpose.

Parameters:

Name Type Description Default
level str | int

Level of the ETT spanning forest to be printed. The default is "all" in which case all levels are printed.

 'all'
Source code in tralda/datastructures/hdtgraph/dynamic_graph.py 
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
def print_ett_forest(self, level: str | int = "all") -> None:
    """Print Euler tour of the spanning forest.

    Intended for testing purpose.

    Args:
        level: Level of the ETT spanning forest to be printed. The default is "all" in which
            case all levels are printed.
    """
    if level == "all":
        for level_i in self._levels:
            print(f"----- Level {level_i.index} -----")
            for ett in level_i.forest:
                print([occ.key for occ in ett], ett.num_active_occurrences)
    elif isinstance(level, int):
        for ett in self._levels[level].forest:
            print([occ.key for occ in ett], ett.num_active_occurrences)
    else:
        raise ValueError(f"invalid level: {level} of type {type(level)}")