elektro

Better filename

activateEnv.srcme

@@ -1,24 +0,0 @@
-#!/bin/bash -u
-
-# 
-# Source python venv (installed via curl https://pyenv.run | bash) to use specific python-version for this project without affecting system
-# For Algorithms and Datastructures Class
-#
-# For WSLg support for matplotlib export="DISPLAY:0" and 
-# echo "backend: TkAgg" > ~/.config/matplotlib/matplotlibrc
-
-export PYENV_ROOT="$HOME/.pyenv"
-export PATH="$PYENV_ROOT/bin:$PATH"
-export PYTHONPATH=".:$PYTHONPATH"
-eval "$(pyenv init --path)"
-eval "$(pyenv init -)"
-eval "$(pyenv virtualenv-init -)"
-
-# Create virtualenv if it doesn't exist
-if ! pyenv versions | grep -q AUD; then
-    echo "Creating Python environment..."
-    pyenv install -s 3.12.0
-    pyenv virtualenv 3.12.0 AUD
-fi
-
-pyenv activate AUD

data/aoc2212test.txt

@@ -0,0 +1,5 @@
+Sabqponm
+abcryxxl
+accszExk
+acctuvwj
+abdefghi

data/aoc2416test.txt

@@ -0,0 +1,15 @@
+###############
+#.......#....E#
+#.#.###.#.###.#
+#.....#.#...#.#
+#.###.#####.#.#
+#.#.#.......#.#
+#.#.#####.###.#
+#...........#.#
+###.#.#####.#.#
+#...#.....#.#.#
+#.#.#.###.#.#.#
+#.....#...#.#.#
+#.###.#.#.#.#.#
+#S..#.....#...#
+###############

data/elektro.txt

@@ -0,0 +1,8 @@
+"Höhleneingang";"Ost/West-Passage";5
+"Höhleneingang";"Nord/Süd-Passage";3
+"Nord/Süd-Passage";"Nebelraum";7
+"Steiniger Pfad";"Ost/West-Passage";2
+"Ost/West-Passage";"Schwefelgewölbe";4
+"Schwefelgewölbe";"Steiniger Pfad";1
+"Schatzkammer";"Nebelraum";2
+"Steiniger Pfad";"Schatzkammer";6

data/hoehle.txt

@@ -0,0 +1,8 @@
+"Höhleneingang" <> "Ost/West-Passage"
+"Höhleneingang" <> "Nord/Süd-Passage"
+"Nord/Süd-Passage" <> "Nebelraum"
+"Steiniger Pfad" > "Ost/West-Passage"
+"Ost/West-Passage" <> "Schwefelgewölbe"
+"Schwefelgewölbe" > "Steiniger Pfad"
+"Schatzkammer" > "Nebelraum"
+"Steiniger Pfad" > "Schatzkammer"

data/labyrinth.txt

@@ -0,0 +1,9 @@
+xxxxxxxxxxxxxxxxxxxxx
+x                   x
+x        S          x
+x                   x
+x      xxxxxxxx     x
+x                   x
+x                   x
+x            A      x
+xxxxxxxxxxxxxxxxxxxxx

data/labyrinth1.txt

@@ -0,0 +1,5 @@
+xxxxxAxxxxxxxxx
+x           xSx
+xxxxxxxxxx xx x
+x             x
+xxxxxxxxxxxxxxx

myreqs.txt

@@ -1,13 +0,0 @@
-contourpy==1.3.1
-cycler==0.12.1
-fonttools==4.56.0
-kiwisolver==1.4.8
-matplotlib==3.10.1
-numpy==2.2.4
-packaging==24.2
-pillow==11.1.0
-pygame==2.6.1
-pyparsing==3.2.3
-python-dateutil==2.9.0.post0
-six==1.17.0
-tk==0.1.0

praktika/05_avl_baum/gv_avl_tree.py

@@ -0,0 +1,12 @@
+from utils.memory_array import MemoryArray
+from vorlesung.L05_binaere_baeume.avl_tree import AVLTree
+
+if __name__ == "__main__":
+    a = MemoryArray.create_array_from_file("data/seq0.txt")
+    tree = AVLTree()
+
+    for cell in a:
+        tree.insert(int(cell))
+
+    tree.graph_traversal()
+

praktika/05_avl_baum/gv_binary_tree.py

@@ -0,0 +1,12 @@
+from utils.memory_array import MemoryArray
+from vorlesung.L05_binaere_baeume.bin_tree import BinaryTree
+
+if __name__ == "__main__":
+    a = MemoryArray.create_array_from_file("data/seq0.txt")
+    tree = BinaryTree()
+
+    for cell in a:
+        tree.insert(int(cell))
+
+    tree.graph_traversal()
+

praktika/07_hashtable/praktikum.py

@@ -0,0 +1,106 @@
+import math
+import unittest
+from utils.literal import Literal
+from utils.memory_cell import MemoryCell
+from utils.memory_array import MemoryArray
+from vorlesung.L07_hashtable.hashtable import HashTableOpenAddressing
+
+#Goldener Schnitt
+a = Literal((math.sqrt(5) - 1) / 2)
+
+# Hashfunktion nach multiplikativer Methode
+def h(x: MemoryCell, m: Literal) -> Literal:
+    with MemoryCell(int(x * a)) as integer_part, MemoryCell(x * a) as full_product:
+        with MemoryCell(full_product - integer_part) as fractional_part:
+            return Literal(abs(int(fractional_part * m)))
+
+# Quadratische Sondierung
+def f(x: MemoryCell, i: Literal, m: Literal) -> Literal:
+    c1 = 1
+    c2 = 5
+    with MemoryCell(h(x, m)) as initial_hash, MemoryCell(c2 * int(i) * int(i)) as quadratic_offset:
+        with MemoryCell(initial_hash + quadratic_offset) as probe_position:
+            probe_position += Literal(c1 * int(i)) # Linear component
+            return probe_position % m
+
+# Symmetrische quadratische Sondierung
+def fs(x: MemoryCell, i: Literal, m: Literal) -> Literal:
+    with MemoryCell(h(x, m)) as base_hash, MemoryCell(int(i) * int(i)) as square:
+        if int(i) % 2 == 0:  # gerades i: Vorwärtssondierung
+            with MemoryCell(base_hash + square) as position:
+                return position % m
+        else:  # ungerades i: Rückwärtssondierung
+            with MemoryCell(base_hash - square) as position:
+                return position % m
+
+
+
+
+if __name__ == "__main__":
+
+    print("*** Aufgabe 3 ***")
+    size =  Literal(20)
+    print(f"Anlage einer Hash-Tabelle mit offener Adressierung mit Größe {size}")
+    ht = HashTableOpenAddressing(size, f)
+    print("Einfügen der Werte aus seq0.txt")
+    for cell in MemoryArray.create_array_from_file("data/seq0.txt"):
+        if not ht.insert(cell):
+            print(f"Einfügen von {cell} nicht möglich")
+    print(ht)
+    print(f"Belegungsfaktor: {ht.alpha()}")
+
+    with MemoryCell(52) as cell:
+        print(f"Suche nach {cell}")
+        if ht.search(cell):
+            print(f"{cell} gefunden, wird gelöscht.")
+            ht.delete(cell)
+        else:
+            print(f"{cell} nicht gefunden")
+    print(ht)
+    print(f"Belegungsfaktor: {ht.alpha()}")
+    print("Einfügen von 24")
+    with MemoryCell(24) as cell:
+        if not ht.insert(cell):
+            print(f"Einfügen von {cell} nicht möglich")
+    print(ht)
+    print(f"Belegungsfaktor: {ht.alpha()}")
+    print()
+
+    print("*** Aufgabe 4 ***")
+    size =  Literal(90)
+    print(f"Anlage einer Hash-Tabelle mit offener Adressierung mit Größe {size}")
+    ht = HashTableOpenAddressing(size, f)
+    print("Einfügen der Werte aus seq1.txt")
+    for cell in MemoryArray.create_array_from_file("data/seq1.txt"):
+        if not ht.insert(cell):
+            print(f"Einfügen von {cell} nicht möglich")
+    print(ht)
+    print(f"Belegungsfaktor: {ht.alpha()}")
+    print()
+
+    print("*** Aufgabe 5 ***")
+    size =  Literal(89)
+    print(f"Anlage einer Hash-Tabelle mit offener Adressierung mit Größe {size}")
+    ht = HashTableOpenAddressing(size, f)
+    print("Einfügen der Werte aus seq1.txt")
+    for cell in MemoryArray.create_array_from_file("data/seq1.txt"):
+        if not ht.insert(cell):
+            print(f"Einfügen von {cell} nicht möglich")
+    print(ht)
+    print(f"Belegungsfaktor: {ht.alpha()}")
+    print()
+
+    print("*** Aufgabe 6 ***")
+    size =  Literal(90)
+    print(f"Anlage einer Hash-Tabelle mit offener Adressierung mit Größe {size}")
+    print("Verwendung der symmetrischen quadratischen Sondierung")
+    ht = HashTableOpenAddressing(size, fs)
+    print("Einfügen der Werte aus seq1.txt")
+    for cell in MemoryArray.create_array_from_file("data/seq1.txt"):
+        if not ht.insert(cell):
+            print(f"Einfügen von {cell} nicht möglich")
+    print(ht)
+    print(f"Belegungsfaktor: {ht.alpha()}")
+    print()
+
+

praktika/08_graph/schatz.py

@@ -0,0 +1,37 @@
+import re
+from utils.project_dir import get_path
+from vorlesung.L08_graphen.graph import Graph, AdjacencyListGraph, AdjacencyMatrixGraph
+
+
+def read_cave_into_graph(graph: Graph, filename: str):
+    """Read a cave description from a file and insert it into the given graph."""
+    filename = get_path(filename)
+    with open(filename, "r") as file:
+        lines = file.readlines()
+        for line in lines:
+            # match a line with two node names and an optional direction
+            m = re.match(r"(^\s*\"(.*)\"\s*([<>]*)\s*\"(.*)\"\s*)", line)
+            if m:
+                startnode = m.group(2)
+                endnode = m.group(4)
+                opcode = m.group(3)
+                graph.insert_vertex(startnode)
+                graph.insert_vertex(endnode)
+                if '>' in opcode:
+                    graph.connect(startnode, endnode)
+                if '<' in opcode:
+                    graph.connect(endnode, startnode)
+
+
+graph = AdjacencyListGraph()
+# graph = AdjacencyMatrixGraph()
+read_cave_into_graph(graph, "data/hoehle.txt")
+_, predecessor_map = graph.bfs('Höhleneingang')
+path = graph.path('Schatzkammer', predecessor_map)
+print(path)
+_, predecessor_map = graph.bfs('Schatzkammer')
+path = graph.path('Höhleneingang', predecessor_map)
+print(path)
+graph.graph("Höhle")
+
+

praktika/09_aoc/rendeer.py

@@ -0,0 +1,59 @@
+from utils.project_dir import get_path
+from vorlesung.L08_graphen.graph import AdjacencyListGraph
+
+DIRECTIONS = [(1,0), (0, 1), (-1, 0), (0, -1)]
+
+class D16Solution:
+
+    def __init__(self):
+        with open(get_path("data/aoc2416.txt"), "r") as file:
+            self.puzzle = [line.strip() for line in file]
+        self.cells = set()
+        self.start = None
+        self.end = None
+
+    def get_cells_start_end(self):
+        for row in range(len(self.puzzle)):
+            for col in range(len(self.puzzle[row])):
+                if self.puzzle[row][col] != '#':
+                    self.cells.add((col, row))
+                if self.puzzle[row][col] == 'S':
+                    self.start = (col, row)
+                if self.puzzle[row][col] == 'E':
+                    self.end = (col, row)
+
+    def get_label(self, cell, direction):
+        """Generate a label for a cell based on its coordinates and direction."""
+        return f"{cell[0]},{cell[1]}_{direction}"
+
+    def create_graph(self):
+        graph = AdjacencyListGraph()
+        for cell in self.cells:
+            for direction in DIRECTIONS:
+                label = self.get_label(cell, direction)
+                graph.insert_vertex(label)
+        for cell in self.cells:
+            for d, direction in enumerate(DIRECTIONS):
+                label = self.get_label(cell, direction)
+                dx, dy = direction
+                neighbor = (cell[0] + dx, cell[1] + dy)
+                if neighbor in self.cells:
+                    graph.connect(label, self.get_label(neighbor, direction))
+                direction_left = DIRECTIONS[(d - 1) % 4]
+                direction_right = DIRECTIONS[(d + 1) % 4]
+                graph.connect(label, self.get_label(cell, direction_left), 1000)
+                graph.connect(label, self.get_label(cell, direction_right), 1000)
+        return graph
+
+if __name__ == "__main__":
+    solution = D16Solution()
+    solution.get_cells_start_end()
+    graph = solution.create_graph()
+    start = solution.get_label(solution.start, DIRECTIONS[0])
+    print(f"Start: {start}")
+    distance_map, predecessor_map = graph.dijkstra(start)
+    end_labels = [solution.get_label(solution.end, direction) for direction in DIRECTIONS]
+    end_vertices = [graph.get_vertex(label) for label in end_labels]
+    min_weight = min([distance_map[vertex] for vertex in end_vertices])
+    print(f"Minimum distance to End {solution.end}: {min_weight}")
+

praktika/10_electro/electro.py

@@ -0,0 +1,32 @@
+from vorlesung.L08_graphen.graph import Graph, AdjacencyMatrixGraph
+from utils.project_dir import get_path
+import re
+
+def read_elektro_into_graph(graph: Graph, filename: str):
+    pattern = re.compile(r'"([^"]+)";"([^"]+)";(\d+)')
+    with (open(filename, "r") as file):
+        for line in file:
+            m = pattern.match(line)
+            if m:
+                start_name = m.group(1)
+                end_name = m.group(2)
+                cost = int(m.group(3))
+                graph.insert_vertex(start_name)
+                graph.insert_vertex(end_name)
+                graph.connect(start_name, end_name, cost)
+                graph.connect(end_name, start_name, cost)
+
+if __name__ == "__main__":
+    graph = AdjacencyMatrixGraph()
+    read_elektro_into_graph(graph, get_path("data/elektro.txt"))
+
+    parents, cost = graph.mst_prim()
+    print(f"Kosten nach Prim: {cost}")
+    for node, parent in parents.items():
+        if parent is not None:
+            print(f"{node} - {parent}")
+
+    edges, cost = graph.mst_kruskal()
+    print(f"Kosten nach Kruskal: {cost}")
+    for start_name, end_name, _ in edges:
+        print(f"{start_name} - {end_name}")

requirements.txt

@@ -1,3 +1,4 @@
 matplotlib
 numpy
 pygame
+graphviz

schoeffelbe/pr01.py

@@ -1,165 +0,0 @@
-from utils.memory_array import MemoryArray
-from utils.memory_cell import MemoryCell
-from utils.literal import Literal
-from utils.constants import MIN_VALUE
-from utils.memory_manager import MemoryManager
-from utils.memory_range import mrange
-
-def max_sequence_1(z: MemoryArray):
-    n = z.length()
-    m = MemoryCell(MIN_VALUE)
-    s = MemoryCell()
-    l = MemoryCell()
-    r = MemoryCell()
-    for i in mrange(n):
-        for j in mrange(i, n):
-            s.set(0)
-            for k in mrange(i, j):
-                s += z[k]
-            if s > m:
-                m.set(s)
-                l.set(i)
-                r.set(j)
-    return m, l, r
-
-def max_sequence_2(z: MemoryArray):
-    n = z.length()
-    m = MemoryCell(MIN_VALUE)
-    s = MemoryCell()
-    l = MemoryCell()
-    r = MemoryCell()
-    for i in mrange(n):
-        s.set(0)
-        for j in mrange(i, n):
-            s += z[j]
-            if s > m:
-                m.set(s)
-                l.set(i)
-                r.set(j)
-    return m, l, r
-
-def _max_sequence_3_sub(z: MemoryArray, l: Literal, m: Literal, r: Literal):
-    # find max-sum from Middle to left
-    linksMax = MemoryCell(MIN_VALUE)
-    sum = MemoryCell(0)
-    links = MemoryCell(l)
-    rechts = MemoryCell(l)
-    for i in mrange(m, MemoryCell(l)-Literal(1), -1):
-        sum += z[i]
-        if sum > linksMax :
-            linksMax.set(sum)
-            links.set(i)
-        
-    # find max-sum from Middle to right 
-    rechtsMax = MemoryCell(MIN_VALUE)
-    sum.set(0);
-    # MRange is exclusive
-    startRight = MemoryCell(1) + m
-    for i in mrange(startRight, MemoryCell(1) + r):
-        sum += z[i]
-        if sum > rechtsMax:
-            rechtsMax.set(sum)
-            rechts.set(i)
-    return (linksMax + rechtsMax), links, rechts
-
-def _max_sequence_3(z: MemoryArray, l: Literal, r: Literal):
-    # Calc-Vars -> illegal to use Literal(0) here? Probably
-    # CAN ALLLL BE LITERALS
-    linksMax = MemoryCell()
-    linksL = MemoryCell()
-    linksR = MemoryCell()
-    rechtsMax = MemoryCell()
-    rechtsL = MemoryCell()
-    rechtsR = MemoryCell()
-    zwiMax = MemoryCell()
-    zwiL = MemoryCell()
-    zwiR = MemoryCell()
-    # Middle
-    m = MemoryCell() 
-    # Rec-Term - Reached subarray of size 1
-    if l == r:
-        return (z[l], l, r)
-    # calc middle
-    m.set(MemoryCell(l) + r)
-    # Use cutoff/floor here, did not check
-    m //= Literal(2);
-    # get maxLeft, then maxRight and then cross them (rec)
-    (linksMax, linksL, linksR) = _max_sequence_3(z, l, m)
-    startRight = MemoryCell(1) + m
-    (rechtsMax, rechtsL, rechtsR) = _max_sequence_3(z, startRight, r)
-    (zwiMax, zwiL, zwiR) = _max_sequence_3_sub(z, l, m, r)
-
-    if linksMax >= rechtsMax and linksMax >= zwiMax:
-        return (linksMax, linksL, linksR)
-
-    if rechtsMax >= linksMax and rechtsMax >= zwiMax:
-        return (rechtsMax, rechtsL, rechtsR)
-
-    return (zwiMax, zwiL, zwiR)
-
-# Wrapper for Seq DivAndConquer to keep call/teststructure possible
-def max_sequence_3(z: MemoryArray):
-    # Start with full range
-    lstart = Literal(0)
-    rend = Literal(len(z) - 1)
-    return _max_sequence_3(z, lstart, rend)
-
-def max_sequence_4(z: MemoryArray):
-    n = z.length()
-    max = MemoryCell(MIN_VALUE)
-    aktLinks = MemoryCell()
-    links = MemoryCell()
-    rechts = MemoryCell()
-    aktSum = MemoryCell()
-    for i in mrange(n):
-        aktSum += z[i]
-        if aktSum > max:
-            max.set(aktSum)
-            links.set(aktLinks)
-            rechts.set(i)
-        # if negative we start new Sum -> Restart must be better than continue
-        if aktSum < Literal(0):
-            aktSum.set(0)
-            aktLinks.set(MemoryCell(1) + i)
-    return (max, links, rechts)
-
-def example(max_sequence_func):
-    l = [-59, 52, 46, 14, -50, 58, -87, -77, 34, 15]
-    print(l)
-    z = MemoryArray(l)
-    m, l, r = max_sequence_func(z)
-    print(m, l, r)
-    assert(m == Literal(120))
-
-
-def seq(filename, max_sequence_func):
-    z = MemoryArray.create_array_from_file(filename)
-    m, l, r = max_sequence_func(z)
-    print(m, l, r)
-
-
-def analyze_complexity(max_sequence_func, sizes):
-    """
-    Analysiert die Komplexität einer maximalen Teilfolgenfunktion.
-
-    :param max_sequence_func: Die Funktion, die analysiert wird.
-    :param sizes: Eine Liste von Eingabegrößen für die Analyse.
-    """
-    for size in sizes:
-        MemoryManager.purge()  # Speicher zurücksetzen
-        random_array = MemoryArray.create_random_array(size, -100, 100)
-        max_sequence_func(random_array)
-        MemoryManager.save_stats(size)
-
-    MemoryManager.plot_stats(["cells", "adds"])
-
-
-if __name__ == '__main__':
-    # fn = max_sequence_4
-    for fn in [max_sequence_1, max_sequence_2, max_sequence_3, max_sequence_4]:
-        example(fn)
-        # for filename in ["data/seq0.txt", "data/seq1.txt", "data/seq2.txt", "data/seq3.txt"]:
-        for filename in ["data/seq0.txt", "data/seq1.txt"]:
-            print(filename)
-            seq(filename, fn)
-        analyze_complexity(fn, [10, 20, 30, 40, 50, 60, 70, 80, 90, 100])

schoeffelbe/pr02.py

@@ -1,125 +0,0 @@
-import logging
-logger = logging.getLogger(__name__)
-# logging.basicConfig(level=logging.DEBUG)
-
-import time
-
-def timeMS(func, *args, **kwargs):
-    startTime = time.perf_counter()
-    result = func(*args, **kwargs)
-    endTime = time.perf_counter()
-    elapsedMS = (endTime - startTime) * 1000  # Convert to milliseconds
-    print(f"{func.__name__} took {elapsedMS:.2f} ms")
-    return result
-
-from utils.memory_array import MemoryArray
-from utils.memory_cell import MemoryCell
-from utils.literal import Literal
-from utils.constants import MIN_VALUE
-from utils.memory_manager import MemoryManager
-from utils.memory_range import mrange
-
-def example():
-    initial = [6, 5, 3, 8, 1, 7, 2, 4]
-    # initial = [-6, -5, -3, -8, 1, 7, 2, 4]
-    toSort = MemoryArray(initial)
-    # init_from_size not accessible?
-    sorted = MemoryArray([-1] * len(initial))
-    mergeSort(toSort, sorted)
-    logger.debug(f"sorted {sorted} vs initial {initial}")
-    assert all(sorted[Literal(i)] == Literal(i+1) for i in range(len(initial))), "Array not sorted correctly"
-
-    analyze_complexity(mergeSort, [10, 20, 30, 40, 50, 60, 70, 80, 90, 100])
-
-def merge(left: MemoryArray, right: MemoryArray, sort: MemoryArray):
-    pointerLeft = MemoryCell(0)
-    pointerRight = MemoryCell(0)
-    pointerSort = MemoryCell(0)
-
-    compare = lambda x, y: x <= y
-
-    logger.debug(f"Merging left {left} with right {right} in sort {sort}")
-
-    while pointerLeft < left.length() and pointerRight < right.length():
-        if compare(left[pointerLeft], right[pointerRight]):
-            sort[pointerSort] = left[pointerLeft]
-            pointerLeft += Literal(1)
-        else:
-            sort[pointerSort] = right[pointerRight]
-            pointerRight += Literal(1)
-
-        logger.debug(f"Now are at sort {sort} with {pointerLeft} (l) and {pointerRight} (r)")
-        pointerSort += Literal(1)
-
-    # Consume remaining elements
-    while pointerLeft < left.length():
-        logger.debug(f"Consuming left {left} from {pointerSort} at {pointerLeft}")
-        sort[pointerSort] = left[pointerLeft]
-        pointerLeft += Literal(1)
-        pointerSort += Literal(1)
-
-    while pointerRight < right.length():
-        logger.debug(f"Consuming right {right} from {pointerSort} at {pointerRight}")
-        sort[pointerSort] = right[pointerRight]
-        pointerRight += Literal(1)
-        pointerSort += Literal(1)
-
-# Sort the array passed as "toSort" and place the result in array "sort"
-# Does not change the original Array
-def mergeSort(toSort: MemoryArray, sort: MemoryArray):
-    logger.debug(toSort)
-    toSortLength = MemoryCell(toSort.length())
-
-    # Splitting
-    # Rec-Term -> Reached single Element. Single Element is already sorted so we place it! 
-    if toSortLength <= Literal(1):
-        # still working for empty array
-        if toSortLength == Literal(1):
-            sort[Literal(0)] = toSort[Literal(0)]
-        return
-
-    # TODO - Use a global var or a reference to an array passed as argument for this
-    # TODO - Tried non-temp-array approach with alternating Work-Arrays passed to the function, but made code really unreadable. Decided not worth it for now
-    # Temporary Arrays to hold the split arrays
-    mid : Literal = toSortLength // Literal(2)
-    left : MemoryArray = MemoryArray([toSort[i] for i in mrange(mid)])
-    right : MemoryArray = MemoryArray([toSort[i] for i in mrange(mid, toSortLength)])
-
-    # Temporary arrays for sorted halves
-    leftSort = MemoryArray([-1] * mid.get())
-    rightSort = MemoryArray([-1] * (toSortLength - mid).get())
-
-    # Split further
-    mergeSort(left, leftSort)
-    mergeSort(right, rightSort)
-
-    # Recreate the array from the seperated parts 
-    merge(leftSort, rightSort, sort)
-
-def analyze_complexity(fn, sizes):
-    """
-    Analysiert die Komplexität einer maximalen Teilfolgenfunktion.
-
-    :param max_sequence_func: Die Funktion, die analysiert wird.
-    :param sizes: Eine Liste von Eingabegrößen für die Analyse.
-    """
-    for size in sizes:
-        MemoryManager.purge()  # Speicher zurücksetzen
-        random_array = MemoryArray.create_random_array(size, -100, 100)
-        other_array = MemoryArray([-1] * size)
-        fn(random_array, other_array)
-        MemoryManager.save_stats(size)
-
-    MemoryManager.plot_stats(["cells", "adds", "compares"])
-
-
-if __name__ == '__main__':
-    # For debug, assert if working and complexity-analysis
-    # example()
-
-    for filename in ["data/seq0.txt", "data/seq1.txt", "data/seq2.txt", "data/seq3.txt"]:
-        print(filename)
-        toSort = MemoryArray.create_array_from_file(filename)
-        sorted = MemoryArray([-1] * toSort.length().get())
-        timeMS(mergeSort, toSort, sorted)
-        # print(sorted)

schoeffelbe/pr03.py

@@ -1,190 +0,0 @@
-import logging
-logger = logging.getLogger(__name__)
-# logging.basicConfig(level=logging.DEBUG)
-
-import time
-
-def timeMS(func, *args, **kwargs):
-    startTime = time.perf_counter()
-    result = func(*args, **kwargs)
-    endTime = time.perf_counter()
-    elapsedMS = (endTime - startTime) * 1000  # Convert to milliseconds
-    print(f"{func.__name__} took {elapsedMS:.2f} ms")
-    return result
-
-
-from utils.memory_array import MemoryArray
-from utils.memory_cell import MemoryCell
-from utils.literal import Literal
-from utils.constants import MIN_VALUE
-from utils.memory_manager import MemoryManager
-from utils.memory_range import mrange
-
-def example():
-    initial = [6, 5, 3, 8, 1, 7, 2, 4]
-    # initial = [-6, -5, -3, -8, 1, 7, 2, 4]
-    toSort = MemoryArray(initial)
-    quickSortIterative(toSort, Literal(0), toSort.length().pred())
-    logger.debug(f"sorted {toSort} vs initial {initial}")
-    assert all(toSort[Literal(i)] == Literal(i+1) for i in range(len(initial))), "Array not sorted correctly"
-
-    # analyze_complexity(quickSort, [10, 20, 30, 40, 50, 60, 70, 80, 90, 100])
-
-def getPivot(z: MemoryArray, l: Literal, r: Literal, mode) -> Literal:
-    if mode == 0:
-        return r
-    else:
-        mid_offset = r.value - l.value
-        mid_offset = mid_offset // 2
-        mid = Literal(l.value + mid_offset)
-    
-        # Return median of left, middle, and right elements
-        if ((z[l] <= z[mid] and z[mid] <= z[r]) or 
-            (z[r] <= z[mid] and z[mid] <= z[l])):
-            return mid
-        elif ((z[mid] <= z[l] and z[l] <= z[r]) or 
-              (z[r] <= z[l] and z[l] <= z[mid])):
-            return l
-        else:
-            return r
-
-
-def swap(z: MemoryArray, i: int, j: int):
-    tmp = z[Literal(i)].value
-    z[Literal(i)] = z[Literal(j)]
-    z[Literal(j)].set(tmp)
-
-# toSort[] --> Array to be sorted,
-# left     --> Starting index,
-# right    --> Ending index
-# adapted from https://stackoverflow.com/questions/68524038/is-there-a-python-implementation-of-quicksort-without-recursion
-def quickSortIterative(toSort : MemoryArray, left : Literal, right : Literal, mode=0):
-    # Create a manually managed stack and avoid pythons recursion-limit
-    size = right.value - left.value + 1
-    stack : MemoryArray = MemoryArray([0] * size)
-    top : MemoryCell = MemoryCell(-1)
-
-    # push initial values of l and h to stack
-    top += Literal(1)
-    stack[top] = left
-    top += Literal(1)
-    stack[top] = right
-  
-    # Keep popping from stack until its empty
-    while top >= Literal(0):
-        logger.debug(f"size {size}, stack {stack}, right {right} and left {left}, top {top}") 
-
-        # Pop h and l - Ensure we are not getting them by Ref, this will produce weird "JUST A LITTLE OF" Results
-        right = Literal(stack[top].get())
-        top -= Literal(1)
-        left = Literal(stack[top].get())
-        top -= Literal(1)
-  
-        # Set pivot element at its correct position in sorted array
-        p = partitionIterative(toSort, left, right, mode)
-  
-        # If there are elements on left side of pivot, then push left side to stack
-        if p.pred() > left:
-            top += Literal(1)
-            stack[top] = left
-            top += Literal(1)
-            stack[top] = p.pred()
-  
-        # If there are elements on right side of pivot, then push right side to stack
-        if p.succ() < right:
-            top += Literal(1)
-            stack[top] = p.succ()
-            top += Literal(1)
-            stack[top] = right
-
-def partitionIterative(arr : MemoryArray, l : Literal, h : Literal, mode=0):
-    logger.debug(f"Partitioning {arr}, {l} and {h}")
-    pivot_idx : Literal = getPivot(arr, l, h, mode)
-
-    # If pivot isn't at the high end, swap it there
-    if pivot_idx != h:
-        swap(arr, int(pivot_idx), int(h))
-
-    # Carefull that we do not use a reference. I suppose python would return one here if we just assign without value>Literal cast.
-    # At least this helped fix weird issue
-    pivotValue : Literal = arr[h]
-    i : MemoryCell = MemoryCell(l.pred())
-  
-    for j in mrange(l, h):
-        if arr[j] <= pivotValue:
-            i += Literal(1)                 # increment index of smaller element
-            swap(arr, int(i), int(j))
-  
-    swap(arr, i.succ().value, h.value)
-    return i.succ()
-
-def LEGACY_quickSort(z: MemoryArray, l: Literal = Literal(0), r: Literal = Literal(-1), mode=0):
-    if r == Literal(-1):
-        r = z.length().pred();
-    if l < r:
-        q = LEGACY_partition(z, l, r, mode)
-        LEGACY_quickSort(z, l, q.pred())
-        LEGACY_quickSort(z, q.succ(), r)
-
-def LEGACY_partition(z: MemoryArray, l: Literal, r: Literal, mode):
-    # Get pivot
-    pivot_idx = getPivot(z, l, r, mode)
-    
-    # If pivot is not already at the right end, swap it there
-    if pivot_idx != r:
-        swap(z, int(pivot_idx), int(r))
-
-    with MemoryCell(z[r]) as pivot, MemoryCell(l) as i, MemoryCell(r.pred()) as j:
-        while i < j:
-            while z[i] < pivot:
-                i.set(i.succ())
-            while j > l and z[j] >= pivot:
-                j.set(j.pred())
-            if i < j:
-                swap(z, int(i), int(j))
-                i.set(i.succ())
-                j.set(j.pred())
-        if i == j and z[i] < pivot:
-            i.set(i.succ())
-        if z[i] != pivot:
-            swap(z, int(i), int(r))
-        return Literal(i)
-
-
-def analyze_complexity(fn, sizes):
-    """
-    Analysiert die Komplexität einer maximalen Teilfolgenfunktion.
-
-    :param max_sequence_func: Die Funktion, die analysiert wird.
-    :param sizes: Eine Liste von Eingabegrößen für die Analyse.
-    """
-    for size in sizes:
-        MemoryManager.purge()  # Speicher zurücksetzen
-        random_array = MemoryArray.create_random_array(size, -100, 100)
-        fn(random_array, Literal(0), random_array.length().pred())
-        MemoryManager.save_stats(size)
-
-    MemoryManager.plot_stats(["cells", "adds", "compares", "reads", "writes"])
-
-
-if __name__ == '__main__':
-    # For debug, assert if working and complexity-analysis
-    example()
-
-    print("I ran into a MaxRecursionDepth Error. From what I read on the Internet python does not do Tailcall Optimizations")
-    print("Increasing recursion-limit seems like a poor Idea, therefore tried an iterative approach with manual stack-keeping")
-
-    toSort = MemoryArray.create_array_from_file("data/seq0.txt")
-    print(toSort)
-    quickSortIterative(toSort, Literal(0), toSort.length().pred())
-    print(toSort)
-
-    # analyze_complexity(quickSortIterative, [10, 20, 30, 40, 50, 60, 70, 80, 90, 100])
-    for filename in ["data/seq0.txt", "data/seq1.txt", "data/seq2.txt" ,"data/seq3.txt"]:
-    # for filename in [ "data/seq1.txt"]:
-        print(filename)
-        toSort = MemoryArray.create_array_from_file(filename)
-        timeMS(quickSortIterative, toSort, Literal(0), toSort.length().pred(), mode=1)
-        print(toSort)
-
-    print("Kann durch die Modifikation eine besser Laufzeit als nlog(n) erreicht werden? Nein! nlog(n) ist das Minimum. Durch die Änderung kann aber der Worst-Case fall von n^2 für z.B. bereits vorsortierte Arrays oder Arrays mit vielen Duplikaten vermieden werden.")

schoeffelbe/pr04.py

@@ -1,293 +0,0 @@
-import logging
-logger = logging.getLogger(__name__)
-# logging.basicConfig(level=logging.DEBUG)
-
-import time
-
-def timeMS(func, *args, **kwargs):
-    startTime = time.perf_counter()
-    result = func(*args, **kwargs)
-    endTime = time.perf_counter()
-    elapsedMS = (endTime - startTime) * 1000  # Convert to milliseconds
-    print(f"{func.__name__} took {elapsedMS:.2f} ms")
-    return result
-
-
-from utils.memory_array import MemoryArray
-from utils.memory_cell import MemoryCell
-from utils.literal import Literal
-from utils.constants import MAX_VALUE
-from utils.memory_manager import MemoryManager
-from utils.memory_range import mrange
-
-# Impl of MemoryArray says we cant add our own Datatypes beside Literal and List
-# BUUUUT we can just wrap our Datatype in a List :-)
-# We store them in a MemoryArray internaly tho anyhow so we increment our Counters for the RAM
-class HeapEntry:
-    def __init__(self, item, priority=1):
-        self.data = MemoryArray(Literal(2))
-        # 0: Content, 1: Prio
-        self.data[Literal(0)] = Literal(item)
-        self.data[Literal(1)] = Literal(priority)
-    
-    def getItem(self):
-        return self.data[Literal(0)]
-    
-    def getPriority(self):
-        return self.data[Literal(1)]
-    
-    def setPriority(self, priority):
-        self.data[Literal(1)] = Literal(priority)
-    
-    def __lt__(self, other):
-        if other is None:
-            return True 
-        if isinstance(other, (int, float)):
-            return self.getPriority().value > other
-        return self.getPriority() > other.getPriority()
-    
-    def __gt__(self, other):
-        if other is None:
-            return False 
-        if isinstance(other, (int, float)):
-            return self.getPriority().value < other
-        return self.getPriority() < other.getPriority()
-    
-    def __eq__(self, other):
-        return self.getPriority() == other.getPriority()
-    
-    def __str__(self):
-        return f"({self.getItem()}, prio={self.getPriority()})"
-
-class PriorityQueue:
-    def __init__(self, max_size : Literal = Literal(100)):
-        self.heap = MemoryArray(max_size) 
-        # Add uninitialized HeapEntry Values so the Adds/Compares do not fail on emtpy stack. 
-        # Would have to switch to MIN_VALUE if we switch what is a "Higher" Prio
-        for i in mrange(max_size.value):
-            self.heap[i].set([HeapEntry(MAX_VALUE, MAX_VALUE)])
-        self.size = MemoryCell(0)
-    
-    def parent(self, i: Literal) -> Literal:
-        return MemoryCell(i.pred()) // Literal(2)
-    
-    def leftChild(self, i: Literal) -> Literal:
-        return MemoryCell(MemoryCell(2) * i) + Literal(1)
-    
-    def rightChild(self, i: Literal) -> Literal:
-        return MemoryCell(MemoryCell(2) * i) + Literal(2)
-    
-    # Swap the Lists -> Therefore get the value which is the List and then Set it again
-    def swap(self, i: Literal, j: Literal):
-        tmp_i = self.heap[i].value
-        tmp_j = self.heap[j].value
-        self.heap[i].set(tmp_j)
-        self.heap[j].set(tmp_i)
-    
-    def maxHeapify(self, i: Literal):
-        left = self.leftChild(i)
-        right = self.rightChild(i)
-        largest = i
-        
-        if left < Literal(self.size.value) and self.heap[left].value[0] > self.heap[largest].value[0]:
-            largest = left
-        
-        if right < Literal(self.size.value) and self.heap[right].value[0] > self.heap[largest].value[0]:
-            largest = right
-        
-        if largest != i:
-            self.swap(i, largest)
-            self.maxHeapify(largest)
-    
-    def insert(self, entry : HeapEntry):
-        if self.size >= self.heap.length():
-            raise IndexError("Heap full")
-        
-        i = self.size
-        self.heap[i].set([entry])
-        
-        while i > Literal(0) and self.heap[self.parent(i)].value[0] < self.heap[i].value[0]:
-            self.swap(i, self.parent(i))
-            i = self.parent(i)
-
-        self.size += Literal(1)
-    
-    def pop(self):
-        if self.isEmpty():
-            raise IndexError("Queue is empty!")
-        
-        max_item = self.heap[Literal(0)].value[0]
-        
-        self.heap[Literal(0)] = self.heap[self.size - Literal(1)]
-        self.size -= Literal(1)
-        
-        self.maxHeapify(Literal(0))
-        
-        return max_item
-    
-    def peek(self):
-        if self.isEmpty():
-            raise IndexError("Queue is empty")
-        return self.heap[Literal(0)].value[0]
-    
-    def isEmpty(self):
-        return self.size == Literal(0)
-    
-    def __len__(self):
-        return self.size
-
-    def __str__(self):
-        entries = []
-        for i in mrange(self.size.value):
-            entry = self.heap[i].value[0]
-            if entry.getItem() != MAX_VALUE:
-                entries.append(str(entry))
-        return "[" + ", ".join(entries) + "]"
-
-# Insert here so we dont run into import problems, but can deliver this file Standalone
-class BinaryTreeNode(MemoryCell):
-    def __init__(self, value):
-        super().__init__(value)
-        self.left = None
-        self.right = None
-
-    def __repr__(self):
-        return f"BinaryTreeNode(value={self.value}, left={self.left}, right={self.right})"
-
-    def __str__(self):
-        return str(self.value)
-
-class BinaryTree:
-    def __init__(self): 
-        self.root: BinaryTreeNode | None = None
-    
-    def insert(self, value: BinaryTreeNode):
-        # Insert at Leaf, if smaller then left one, otherwise right one
-        def _insert(node: BinaryTreeNode | None, value) -> BinaryTreeNode:
-            if node is None:
-                return BinaryTreeNode(value)
-            if value < node:
-                node.left = _insert(node.left, value)                                 # type: ignore -> Ignoring pywright errors
-            else:
-                node.right = _insert(node.right, value)                               # type: ignore -> Ignoring pywright errors
-            return node
-
-        self.root = _insert(self.root, value)
-    
-    def traverse(self, mode="in", visual=False):
-        mode = mode.lower()
-        # Have internal depth counting
-        def InternalTraverse(node, prefix="", is_left=True, depth=0):
-            if node is None:
-                return [] if not visual else []
-    
-            result = []
-            node_str = str(node)
-
-            prefixAcc = prefix + ("|   " if is_left and depth > 0 else "   ")
-    
-            if visual:
-                connector = "+-- " if is_left else "L-- "
-                line = prefix + connector + node_str if depth > 0 else node_str
-                result.append(line)
-            else:
-                result.append(node_str)
-
-            if mode == "pre":
-                result += InternalTraverse(node.left, prefixAcc, True, depth + 1)
-                result += InternalTraverse(node.right, prefixAcc, False, depth + 1)
-            elif mode == "in":
-                result += InternalTraverse(node.left, prefixAcc, True, depth + 1)
-                result += InternalTraverse(node.right, prefixAcc, False, depth + 1)
-            elif mode == "post":
-                result += InternalTraverse(node.left, prefixAcc, True, depth + 1)
-                result += InternalTraverse(node.right, prefixAcc, False, depth + 1)
-    
-            return result
-    
-        if self.root is None:
-            return "(empty tree)" if visual else []
-    
-        result = InternalTraverse(self.root)
-        return "\n".join(result) if visual else result
-
-    
-    def levelOrderWithPriorityQueue(self):
-        if not self.root:
-            return []
-        
-        # Create a priority queue, using a reduced prio for every new entry -> behaviour as regular queue FIFO
-        pq = PriorityQueue(Literal(1000))
-
-        # Again we cannot create a MemoryArray of dynamic sizes and also cannot create a string as MemoryCell does not like it
-        # Again we just create a list holding a single dummy Entry (to set its size to 1) and then just use this "list" as our string
-        # Appending to it is easy as it is just a regular list and in the end we return it
-        # Like MemoryCell("").value.append("STRING") will fail. But list-wrap works. 
-        #
-        # Sorry for Syntax, dont know any better way to have everything as RAM-Managed memory:-(
-        result = MemoryArray(["MYSTRING"])
-        result[Literal(0)].set([]);
-
-        counter = MemoryCell(0)
-        def nextPriority():
-            val = counter.value
-            counter.set(Literal(val + 1))
-            return val
-        pq.insert(HeapEntry([self.root], nextPriority()))  
-        
-        while not pq.isEmpty():
-            entry = pq.pop()
-            node = entry.getItem().value
-            
-            result[Literal(0)].value.append(str(node[0]))
-            
-            if node[0].left:
-                pq.insert(HeapEntry([node[0].left], nextPriority()))
-            if node[0].right:
-                pq.insert(HeapEntry([node[0].right], nextPriority()))
-        
-        return result[Literal(0)]
-
-
-    def __str__(self):
-        return str(self.traverse(mode="PrE", visual=True))
-
-def analyze_complexity(fn, sizes):
-    """
-    Analysiert die Komplexität einer maximalen Teilfolgenfunktion.
-
-    :param max_sequence_func: Die Funktion, die analysiert wird.
-    :param sizes: Eine Liste von Eingabegrößen für die Analyse.
-    """
-    for size in sizes:
-        MemoryManager.purge()  # Speicher zurücksetzen
-        random_array = MemoryArray.create_random_array(size, -100, 100)
-        fn(random_array, Literal(0), random_array.length().pred())
-        MemoryManager.save_stats(size)
-
-    MemoryManager.plot_stats(["cells", "adds", "compares", "reads", "writes"])
-
-
-if __name__ == '__main__':
-    # For debug, assert if working and complexity-analysis
-    # example()
-
-    print("Sorry for the Syntax and the large file, tried to keep everything as a standalone file to help make it \" download and run \".\n \
-          Also did - once again - not find a better way to have a queue managed by the RAM contain the values of non-integer-attributes I \n\
-          needed it to. Therefore i reused my Priorityqueue and its accesses via the unspecified wrapped list.");
-
-    # for filename in ["data/seq0.txt", "data/seq1.txt", "data/seq2.txt" ,"data/seq3.txt"]:
-    for filename in [ "data/seq0.txt"]:
-        print(filename)
-        binTreeData = MemoryArray.create_array_from_file(filename)
-        binTree = BinaryTree()
-        for value in binTreeData:
-            binTree.insert(BinaryTreeNode(value))
-
-        # Print overlaoded InOrder traversal
-        print(binTree)
-        # print(binTree.traverse(mode="pre", visual=False))
-        # print(binTree.traverse(mode="in", visual=False))
-        # print(binTree.traverse(mode="post", visual=False))
-        # Print Levelorder traversal:
-        print(binTree.levelOrderWithPriorityQueue())

schoeffelbe/pr05.py

@@ -1,246 +0,0 @@
-import logging
-logger = logging.getLogger(__name__)
-# logging.basicConfig(level=logging.DEBUG)
-
-import time
-
-def timeMS(func, *args, **kwargs):
-    startTime = time.perf_counter()
-    result = func(*args, **kwargs)
-    endTime = time.perf_counter()
-    elapsedMS = (endTime - startTime) * 1000  # Convert to milliseconds
-    print(f"{func.__name__} took {elapsedMS:.2f} ms")
-    return result
-
-
-from utils.memory_array import MemoryArray
-from utils.literal import Literal
-from utils.memory_manager import MemoryManager
-from vorlesung.L05_binaere_baeume.bin_tree import BinaryTree
-from vorlesung.L05_binaere_baeume.bin_tree_node import BinaryTreeNode
-
-def analyze_complexity(fn, sizes):
-    """
-    Analysiert die Komplexität einer maximalen Teilfolgenfunktion.
-
-    :param max_sequence_func: Die Funktion, die analysiert wird.
-    :param sizes: Eine Liste von Eingabegrößen für die Analyse.
-    """
-    for size in sizes:
-        MemoryManager.purge()  # Speicher zurücksetzen
-        random_array = MemoryArray.create_random_array(size, -100, 100)
-        fn(random_array, Literal(0), random_array.length().pred())
-        MemoryManager.save_stats(size)
-
-    MemoryManager.plot_stats(["cells", "adds", "compares", "reads", "writes"])
-
-lineAccumulator = []
-
-# Returnvalue does not get forwarded so we can not work with return. 
-# Will try glob vars to append the string
-# Signature: def print_node(node, indent=0, line=None):
-def clbk_graphvizify(toDecorate : BinaryTreeNode, indent=0, line=None):
-    global lineAccumulator
-
-    if isinstance(toDecorate, AVLTreeNode):
-        lineAccumulator.append(f'n_{id(toDecorate)} [label=<{toDecorate.value}<BR/><FONT COLOR="RED" POINT-SIZE="10.0" FACE="ambrosia">B: {toDecorate.balanceFactor}</FONT>>]')
-    else:
-        lineAccumulator.append(f"n_{id(toDecorate)} [label={toDecorate.value}]")
-
-    # Create edges for nodes with Child (use l - r)
-    if toDecorate.left is not None:
-        lineAccumulator.append(f"n_{id(toDecorate)} -> n_{id(toDecorate.left)}")
-    
-    if toDecorate.right is not None:
-        lineAccumulator.append(f"n_{id(toDecorate)} -> n_{id(toDecorate.right)}")
-
-
-def graphvizify() -> str:
-    # Header
-    result = "digraph {\n\t"
-    # Body
-    result += ('\n\t'.join(str(item) for item in lineAccumulator))
-    # Footer
-    result += "\n}"
-    return result
-
-class AVLTreeNode(BinaryTreeNode):
-    def __init__(self, value):
-        super().__init__(value)
-        self.parentRef = None
-        # Start balanced as we probably have no children right after insert
-        self.balanceFactor = Literal(0)
-
-    def rightRotate(self, node) -> 'AVLTreeNode|None':
-        if node is None:
-            return None
-        
-        oLeft = node.left;
-        oLeft.parentRef = node.parentRef;
-        node.left = oLeft.right;
-
-        if node.left is not None:
-            node.left.parentRef = node;
-
-        oLeft.right = node;
-        node.parentRef = oLeft;
-
-        if oLeft.parentRef is not None:
-            if oLeft.parentRef.right is node:
-                oLeft.parentRef.right = oLeft;
-            elif oLeft.parentRef.left is node:
-                oLeft.parentRef.left = oLeft;
-    
-        node.getSetBalanceFactor()
-        oLeft.getSetBalanceFactor()
-
-        return oLeft
-
-    def leftRotate(self, node) -> 'AVLTreeNode|None':
-        if node is None:
-            return None
-        
-        oRight = node.right
-        oRight.parentRef = node.parentRef
-        node.right = oRight.left
-
-        if node.right is not None:
-            node.right.parentRef = node
-
-        oRight.left = node
-        node.parentRef = oRight
-
-        if oRight.parentRef is not None:
-            if oRight.parentRef.right is node:
-                oRight.parentRef.right = oRight
-            elif oRight.parentRef.left is node:
-                oRight.parentRef.left = oRight
-
-        node.getSetBalanceFactor()
-        oRight.getSetBalanceFactor()
-
-        return oRight
-
-    def getSetBalanceFactor(self) -> Literal:
-        leftHeight = self.left.height() if self.left else 0
-        rightHeight = self.right.height() if self.right else 0
-        self.balanceFactor = Literal(rightHeight - leftHeight)
-        return self.balanceFactor
-
-    def rightLeftRotate(self, node) -> 'AVLTreeNode|None':
-        node.right = self.rightRotate(node.right)
-        return self.leftRotate(node)
-
-    def leftRightRotate(self, node) -> 'AVLTreeNode|None':
-        node.left = self.leftRotate(node.left)
-        return self.rightRotate(node)
-
-
-def debugTraverse(node, source=1):
-    if node is None:
-        return None
-    logger.debug(f"{node.value} {node.getSetBalanceFactor()} {source}")
-    debugTraverse(node.left, 10);
-    debugTraverse(node.right, 20);
-
-
-class AVLTree(BinaryTree):
-    # @override
-    def new_node(self, value) -> AVLTreeNode:
-        return AVLTreeNode(value)
-
-    def balanceAVLTree(self, node : AVLTreeNode):
-        # balance < -1 means imbalance to the left, > 1 means imbalance to the right
-        logger.debug("in")
-        if node is None:
-            return None
-        logger.debug("out")
-        
-        node.getSetBalanceFactor()
-        logger.debug(f"Parent Balancing for {node.value} -> {node.balanceFactor} {node.left.height() if node.left else None} and {node.right.height() if node.right else None}")
-        
-        # imbalance to left -> If we enter this we cannot LOGICALLY have a left=None node -> No need to chekc
-        if node.balanceFactor < Literal(-1):
-            # Left-Left
-            if node.left.balanceFactor <= Literal(0):   # type: ignore -> Ignoring pywright error, see comment above
-                # Wow, this syntax is sketchy ^^
-                # TODO Maybe declare as static if python supports this? Or just leaf param be?
-                logger.debug("rr")
-                node = node.rightRotate(node)
-            # Left-Right
-            else:
-                # TODO Maybe declare as static if python supports this? Or just leaf param be?
-                logger.debug("lrr")
-                node = node.leftRightRotate(node)
-        
-        # Right heavy
-        # imbalance to right -> If we enter this we cannot LOGICALLY have a right=None node -> No need to chekc
-        if node.balanceFactor > Literal(1):
-            # Right-Right case
-            if node.right.balanceFactor >= Literal(0):   # type: ignore -> Ignoring pywright error, see comment above
-                # TODO Maybe declare as static if python supports this? Or just leaf param be?
-                logger.debug("lr")
-                node = node.leftRotate(node)
-            # Right-Left case
-            else:
-                # TODO Maybe declare as static if python supports this? Or just leaf param be?
-                logger.debug("rlr")
-                node = node.rightLeftRotate(node)
-        
-        logger.debug(f"Reached {node.parentRef}")
-        if node.parentRef is not None:
-            logger.debug(f"Calling again for {node.parentRef.value}");
-            self.balanceAVLTree(node.parentRef);
-        else:
-            self.root = node;
-
-        # Node is balanced
-        return node
-
-    # @override
-    def insert(self, value):
-        node, parent = super().insert(value)
-        # NOTE Python does not have a Problem with NOT tellin us that we override something important
-        # or something that does not exist.... This Makes for AWESOME debugging .... ... ...
-        node.parentRef = parent
-
-        if parent:
-            node = self.balanceAVLTree(node.parentRef)
-
-        return node, parent
-
-if __name__ == '__main__':
-    tree = AVLTree()
-
-    ### Force RR
-    # testData = [30, 20, 10];
-    # for value in testData:
-    #     tree.insert(MemoryCell(value));
-
-    ### Force LR
-    # testData = [10, 20, 30];
-    # for value in testData:
-    #     tree.insert(MemoryCell(value));
-
-    ### Force LRR
-    # testData = [30, 10, 20]
-    # for value in testData:
-    #     tree.insert(MemoryCell(value))
-
-    ### Force RLR
-    # testData = [10, 30, 20]
-    # for value in testData:
-    #     tree.insert(MemoryCell(value))
-
-    # Force rebuild of our balanceFactor indices... 
-    # debugTraverse(tree.root)
-
-    binTreeData = MemoryArray.create_array_from_file("data/seq0.txt")
-    for value in binTreeData:
-        tree.insert(value)
-
-
-    lineAccumulator.clear();
-    tree.in_order_traversal(clbk_graphvizify)
-    # tree.tree_structure_traversal(clbk_graphvizify)
-    print(graphvizify())

schoeffelbe/priorityQueue.py

@@ -1,193 +0,0 @@
-from utils.memory_array import MemoryArray
-from utils.memory_cell import MemoryCell
-from utils.literal import Literal
-from utils.constants import MIN_VALUE
-from utils.memory_range import mrange
-
-# Impl of MemoryArray says we cant add our own Datatypes beside Literal and List
-# BUUUUT we can just wrap our Datatype in a List :-)
-# We store them in a MemoryArray internaly tho anyhow so we increment our Counters for the RAM
-class HeapEntry:
-    def __init__(self, item, priority=1):
-        self.data = MemoryArray(Literal(2))
-        # 0: Content, 1: Prio
-        self.data[Literal(0)] = Literal(item)
-        self.data[Literal(1)] = Literal(priority)
-    
-    def getItem(self):
-        return self.data[Literal(0)]
-    
-    def getPriority(self):
-        return self.data[Literal(1)]
-    
-    def setPriority(self, priority):
-        self.data[Literal(1)] = Literal(priority)
-    
-    def __lt__(self, other):
-        if other is None:
-            return True 
-        if isinstance(other, (int, float)):
-            return self.getPriority().value > other
-        return self.getPriority() < other.getPriority()
-    
-    def __gt__(self, other):
-        if other is None:
-            return False 
-        if isinstance(other, (int, float)):
-            return self.getPriority().value < other
-        return self.getPriority() > other.getPriority()
-    
-    def __eq__(self, other):
-        return self.getPriority() == other.getPriority()
-    
-    def __str__(self):
-        return f"({self.getItem()}, prio={self.getPriority()})"
-
-class PriorityQueue:
-    def __init__(self, max_size : Literal = Literal(100)):
-        self.heap = MemoryArray(max_size) 
-        # Add uninitialized HeapEntry Values so the Adds/Compares do not fail on emtpy stack. 
-        # Would have to switch to MIN_VALUE if we switch what is a "Higher" Prio
-        for i in mrange(max_size.value):
-            self.heap[i].set([HeapEntry(MIN_VALUE, MIN_VALUE)])
-        self.size = MemoryCell(0)
-    
-    def parent(self, i: Literal) -> Literal:
-        return MemoryCell(i.pred()) // Literal(2)
-    
-    def leftChild(self, i: Literal) -> Literal:
-        return MemoryCell(MemoryCell(2) * i) + Literal(1)
-    
-    def rightChild(self, i: Literal) -> Literal:
-        return MemoryCell(MemoryCell(2) * i) + Literal(2)
-    
-    # Swap the Lists -> Therefore get the value which is the List and then Set it again
-    def swap(self, i: Literal, j: Literal):
-        tmp_i = self.heap[i].value
-        tmp_j = self.heap[j].value
-        self.heap[i].set(tmp_j)
-        self.heap[j].set(tmp_i)
-    
-    def maxHeapify(self, i: Literal):
-        left = self.leftChild(i)
-        right = self.rightChild(i)
-        largest = i
-        
-        if left < Literal(self.size.value) and self.heap[left].value[0] > self.heap[largest].value[0]:
-            largest = left
-        
-        if right < Literal(self.size.value) and self.heap[right].value[0] > self.heap[largest].value[0]:
-            largest = right
-        
-        if largest != i:
-            self.swap(i, largest)
-            self.maxHeapify(largest)
-    
-    def insert(self, entry : HeapEntry):
-        if self.size >= self.heap.length():
-            raise IndexError("Heap full")
-        
-        i = self.size
-        self.heap[i].set([entry])
-        
-        while i > Literal(0) and self.heap[self.parent(i)].value[0] < self.heap[i].value[0]:
-            self.swap(i, self.parent(i))
-            i = self.parent(i)
-
-        self.size += Literal(1)
-    
-    def pop(self):
-        if self.isEmpty():
-            raise IndexError("Queue is empty!")
-        
-        max_item = self.heap[Literal(0)].value[0]
-        
-        self.heap[Literal(0)] = self.heap[self.size - Literal(1)]
-        self.size -= Literal(1)
-        
-        self.maxHeapify(Literal(0))
-        
-        return max_item
-    
-    def peek(self):
-        if self.isEmpty():
-            raise IndexError("Queue is empty")
-        return self.heap[Literal(0)].value[0]
-    
-    def isEmpty(self):
-        return self.size == Literal(0)
-    
-    def __len__(self):
-        return self.size
-
-    def __str__(self):
-        entries = []
-        for i in mrange(self.size.value):
-            entry = self.heap[i].value[0]
-            if entry.getItem() != MIN_VALUE:
-                entries.append(str(entry))
-        return "[" + ", ".join(entries) + "]"
-
-def testQueueRandom(number: int):
-    import random
-    import string
-
-    pq = PriorityQueue(Literal(number))
-
-    entries = []
-    for _ in range(number):
-        value = ''.join(random.choices(string.ascii_uppercase + string.digits, k=3))
-        priority = random.randint(1, 100)
-        entry = HeapEntry(value, priority)
-        entries.append(entry)
-        pq.insert(entry)
-
-    print(pq)
-    for entry in entries:
-        print(f"Unprioritized: {entry}")
-
-    while not pq.isEmpty(): 
-        print(pq.pop())
-
-
-if __name__ == '__main__':
-    # Proof of Concept
-    testEntry = HeapEntry("A", 2)
-    print(testEntry)
-    testArray = MemoryArray([testEntry])
-    print(testArray)
-    print(testArray[Literal(0)])
-
-    # Queue Testing
-    pq = PriorityQueue()
-    try:
-        pq.pop()
-        assert False, "Queue should be empty"
-    except IndexError:
-        pass  
-    assert(pq.isEmpty() and pq.size == Literal(0))
-    entry = HeapEntry("A", 1)
-    pq.insert(entry)
-    assert(not pq.isEmpty() and pq.size == Literal(1))
-    pq.peek()
-    assert(not pq.isEmpty())
-    assert(pq.pop() == HeapEntry("A", 1))
-    assert(pq.isEmpty())
-    pq.insert(HeapEntry("C", 3))
-    pq.insert(HeapEntry("B", 2))
-    pq.insert(HeapEntry("A", 1))
-    assert(pq.size == Literal(3))
-    assert(pq.pop() == HeapEntry("C", 3))
-    assert(pq.pop() == HeapEntry("B", 2))
-    assert(pq.pop() == HeapEntry("A", 1))
-    pq.insert(HeapEntry("A", 1))
-    pq.insert(HeapEntry("C", 3))
-    pq.insert(HeapEntry("B", 2))
-    pq.insert(HeapEntry(42, 4))
-    pq.insert(HeapEntry(42, 1))
-    pq.insert(HeapEntry("C", 2))
-    print(pq)
-    while not pq.isEmpty(): 
-        print(pq.pop())
-
-    testQueueRandom(100)

utils/priority_queue.py

@@ -0,0 +1,40 @@
+import heapq
+
+class PriorityQueue:
+    def __init__(self):
+        self.heap = []
+        self.entry_finder = {}  # map: item -> [priority, item]
+        self.REMOVED = '<removed>'
+        self.counter = 0  # unique sequence count to break ties
+
+    def add_or_update(self, item, priority):
+        if item in self.entry_finder:
+            self.remove(item)
+        count = self.counter
+        entry = [priority, count, item]
+        self.entry_finder[item] = entry
+        heapq.heappush(self.heap, entry)
+        self.counter += 1
+
+    def remove(self, item):
+        entry = self.entry_finder.pop(item)
+        entry[-1] = self.REMOVED  # mark as removed
+
+    def pop(self):
+        while self.heap:
+            priority, count, item = heapq.heappop(self.heap)
+            if item != self.REMOVED:
+                del self.entry_finder[item]
+                return item, priority
+        return None
+
+if __name__ == "__main__":
+    pq = PriorityQueue()
+    pq.add_or_update('task1', 1)
+    pq.add_or_update('task2', float('inf'))
+    pq.add_or_update('task3', float('inf'))
+
+    print(pq.pop())  # Should print ('task1', 1)
+    pq.add_or_update('task2', 0)  # Update priority of 'task1'
+    print(pq.pop())  # Should print ('task2', 0)
+    print(pq.pop())  # Should print ('task3', 3)

vorlesung/L05_binaere_baeume/analyze_avl_tree.py

@@ -0,0 +1,26 @@
+from utils.memory_manager import MemoryManager
+from utils.memory_array import MemoryArray
+from utils.literal import Literal
+from vorlesung.L05_binaere_baeume.avl_tree import AVLTree
+
+def analyze_complexity(sizes):
+    """
+    Analysiert die Komplexität
+
+    :param sizes: Eine Liste von Eingabegrößen für die Analyse.
+    """
+    for size in sizes:
+        MemoryManager.purge()  # Speicher zurücksetzen
+        tree = AVLTree()
+        random_array = MemoryArray.create_random_array(size, -100, 100)
+        for i in range(size-1):
+            tree.insert(int(random_array[Literal(i)]))
+        MemoryManager.reset()
+        tree.insert(int(random_array[Literal(size-1)]))
+        MemoryManager.save_stats(size)
+
+    MemoryManager.plot_stats(["cells", "compares"])
+
+if __name__ == "__main__":
+    sizes = range(1, 1001, 2)
+    analyze_complexity(sizes)

vorlesung/L05_binaere_baeume/avl_tree.py

@@ -0,0 +1,94 @@
+from utils.memory_array import MemoryArray
+from vorlesung.L05_binaere_baeume.avl_tree_node import AVLTreeNode
+from vorlesung.L05_binaere_baeume.bin_tree import BinaryTree
+import logging
+
+class AVLTree(BinaryTree):
+
+    def __init__(self):
+        super().__init__()
+
+    def new_node(self, value):
+        return AVLTreeNode(value)
+
+
+    def balance(self, node: AVLTreeNode):
+        node.update_balance()
+        if node.balance == -2:
+            if node.left.balance <= 0:
+                node = node.right_rotate()
+            else:
+                node = node.left_right_rotate()
+        elif node.balance == 2:
+            if node.right.balance >= 0:
+                node = node.left_rotate()
+            else:
+                node = node.right_left_rotate()
+        if node.parent:
+            self.balance(node.parent)
+        else:
+            self.root = node
+
+    def insert(self, value):
+        insert_generator = self.insert_stepwise(value)
+        node, parent = None, None
+        while True:
+            try:
+                node, parent = next(insert_generator)
+            except StopIteration:
+                break
+        return node, parent
+
+    def insert_stepwise(self, value):
+        node, parent = super().insert(value)
+        yield None, None
+        node.parent = parent
+        if parent:
+            self.balance(parent)
+        return node, parent
+
+
+    def delete(self, value):
+        node, parent = super().delete(value)
+        if node:
+            node.parent = parent
+        if parent:
+            self.balance(parent)
+
+    def graph_filename(self):
+        return "AVLTree"
+
+if __name__ == "__main__":
+
+    def print_node(node, indent=0, level=0):
+        print((indent * 3) * " ", node.value)
+
+    tree = AVLTree()
+    #values = [5, 3, 7, 2, 4, 6, 5, 8]
+    values = MemoryArray.create_array_from_file("data/seq2.txt")
+
+    for value in values:
+        tree.insert(value)
+
+
+    print("In-order traversal:")
+    tree.in_order_traversal(print_node)
+    print("\nLevel-order traversal:")
+    tree.level_order_traversal(print_node)
+    print("\nTree structure traversal:")
+    tree.tree_structure_traversal(print_node)
+    print("\nGraph traversal:")
+    tree.graph_traversal()
+
+    tree.insert(9)
+    tree.graph_traversal()
+
+    print("\nDeleting 5:")
+    tree.delete(5)
+
+    print("In-order traversal after deletion:")
+    tree.in_order_traversal(print_node)
+    print("\nLevel-order traversal after deletion:")
+    tree.level_order_traversal(print_node)
+    print("\nTree structure traversal after deletion:")
+    tree.tree_structure_traversal(print_node)

vorlesung/L05_binaere_baeume/avl_tree_game.py

@@ -0,0 +1,59 @@
+import random
+import pygame
+from utils.game import Game
+from avl_tree import AVLTree
+
+WHITE = (255, 255, 255)
+BLUE = (0, 0, 255)
+BLACK = (0, 0, 0)
+WIDTH = 800
+HEIGHT = 400
+MARGIN = 20
+
+class AVLTreeGame(Game):
+
+    def __init__(self):
+        super().__init__("AVLTree Game", fps=10, size=(WIDTH, HEIGHT))
+        random.seed()
+        self.z = list(range(1, 501))
+        random.shuffle(self.z)
+        self.finished = False
+        self.tree = AVLTree()
+        self.tree.get_height = lambda node: 0 if node is None else 1 + max(self.tree.get_height(node.left), self.tree.get_height(node.right))
+        self.height = self.tree.get_height(self.tree.root)
+        self.generator = None
+
+    def update_game(self):
+        if not self.finished:
+            if self.generator is None:
+                self.generator = self.tree.insert_stepwise(self.z.pop())
+            try:
+                next(self.generator)
+            except StopIteration:
+                self.generator = None
+            if self.generator is None and len(self.z) == 0:
+                self.finished = True
+            self.height = self.tree.get_height(self.tree.root)
+        return True
+
+    def draw_game(self):
+        self.screen.fill(WHITE)
+        if self.height > 0:
+            self.draw_tree(self.tree.root, WIDTH // 2, MARGIN, WIDTH // 4 - MARGIN)
+        super().draw_game()
+
+    def draw_tree(self, node, x, y, x_offset):
+        y_offset = (HEIGHT - (2 * MARGIN)) / self.height
+        if node is not None:
+            pygame.draw.circle(self.screen, BLUE, (x, y), 2)
+            if node.left is not None:
+                pygame.draw.line(self.screen, BLACK, (x, y), (x - x_offset, y + y_offset))
+                self.draw_tree(node.left, x - x_offset, y + y_offset, x_offset // 2)
+            if node.right is not None:
+                pygame.draw.line(self.screen, BLACK, (x, y), (x + x_offset, y + y_offset))
+                self.draw_tree(node.right, x + x_offset, y + y_offset, x_offset // 2)
+
+if __name__ == "__main__":
+    tree_game = AVLTreeGame()
+    tree_game.run()
+

vorlesung/L05_binaere_baeume/avl_tree_node.py

@@ -0,0 +1,61 @@
+from vorlesung.L05_binaere_baeume.bin_tree_node import BinaryTreeNode
+
+class AVLTreeNode(BinaryTreeNode):
+    def __init__(self, value):
+        super().__init__(value)
+        self.parent = None
+        self.balance = 0
+
+    def __repr__(self):
+        return f"TreeNode(id={id(self)} value={self.value}, left={self.left}, right={self.right})"
+
+    def graphviz_rep(self, row, col, dot):
+        dot.node(str(id(self)), label=str(self.value), pos=f"{col},{-row}!", xlabel=str(self.balance))
+
+    def update_balance(self):
+        left_height = self.left.height() if self.left else 0
+        right_height = self.right.height() if self.right else 0
+        self.balance = right_height - left_height
+
+    def right_rotate(self):
+        new_root = self.left
+        new_root.parent = self.parent
+        self.left = new_root.right
+        if self.left:
+            self.left.parent = self
+        new_root.right = self
+        self.parent = new_root
+        if new_root.parent:
+            if new_root.parent.left is self:
+                new_root.parent.left = new_root
+            else:
+                new_root.parent.right = new_root
+        self.update_balance()
+        new_root.update_balance()
+        return new_root
+
+    def left_rotate(self):
+        new_root = self.right
+        new_root.parent = self.parent
+        self.right = new_root.left
+        if self.right:
+            self.right.parent = self
+        new_root.left = self
+        self.parent = new_root
+        if new_root.parent:
+            if new_root.parent.left is self:
+                new_root.parent.left = new_root
+            else:
+                new_root.parent.right = new_root
+        self.update_balance()
+        new_root.update_balance()
+        return new_root
+
+    def right_left_rotate(self):
+        self.right = self.right.right_rotate()
+        return self.left_rotate()
+
+    def left_right_rotate(self):
+        self.left = self.left.left_rotate()
+        return self.right_rotate()
+

vorlesung/L05_binaere_baeume/bin_tree.py

@@ -1,8 +1,7 @@
 from vorlesung.L05_binaere_baeume.bin_tree_node import BinaryTreeNode
-from utils.memory_manager import MemoryManager
-from utils.memory_array import MemoryArray
 from utils.project_dir import get_path
 from datetime import datetime
+import graphviz
 
 
 class BinaryTree:
@@ -69,7 +68,7 @@ class BinaryTree:
                 break
         else:
             # Wert nicht gefunden
-            return
+            return None, None
         return self.delete_node(current, parent)
 
     def delete_node(self, current, parent):
@@ -144,37 +143,35 @@ class BinaryTree:
         line = 0
         tree_structure_traversal_recursive(callback, self.root, 0)
 
+    def graph_filename(self):
+        return "BinaryTree"
 
     def graph_traversal(self):
-
         def define_node(node, level, line):
-            nonlocal file
+            nonlocal dot
             if node is not None:
-                file.write(node.gv_rep(level, line))
+                node.graphviz_rep(level, line, dot)
 
         def graph_traversal_recursive(current):
-            nonlocal file
+            nonlocal dot
             if current is not None:
                 if current.left:
-                    file.write(f"{id(current)} -> {id(current.left)}; \n")
+                    dot.edge(str(id(current)), str(id(current.left)))
                     graph_traversal_recursive(current.left)
                 if current.right:
-                    file.write(f"{id(current)} -> {id(current.right)}; \n")
+                    dot.edge(str(id(current)), str(id(current.right)))
                     graph_traversal_recursive(current.right)
 
-        timestamp = datetime.now().strftime("%Y%m%d_%H:%M:%S")
+        dot = graphviz.Digraph( name="BinaryTree",
-        filename = f"graph_{timestamp}.gv"
+                                engine="neato",
-        filename = get_path(filename)
+                                node_attr={"shape": "circle", "fontname": "Arial"},
-        with open(filename, "w") as file:
+                                format="pdf" )
-            file.write("digraph BST {\n")
-            file.write("layout=neato;\n")
-            file.write("node [shape=circle, fontname=\"Arial\"];\n")
         self.tree_structure_traversal(define_node)
         graph_traversal_recursive(self.root)
-            file.write("}")
+        timestamp = datetime.now().strftime("%Y%m%d_%H%M%S")
-
+        filename = f"{self.graph_filename()}_{timestamp}.gv"
-
+        filename = get_path(filename)
-
+        dot.render(filename)
 
 if __name__ == "__main__":
     tree = BinaryTree()

vorlesung/L05_binaere_baeume/bin_tree_game.py

@@ -0,0 +1,54 @@
+import random
+import pygame
+from utils.game import Game
+from bin_tree import BinaryTree
+
+WHITE = (255, 255, 255)
+BLUE = (0, 0, 255)
+BLACK = (0, 0, 0)
+WIDTH = 800
+HEIGHT = 400
+MARGIN = 20
+
+class BinTreeGame(Game):
+
+    def __init__(self):
+        super().__init__("BinTree Game", fps=10, size=(WIDTH, HEIGHT))
+        random.seed()
+        self.z = list(range(1, 101))
+        random.shuffle(self.z)
+        self.finished = False
+        self.tree = BinaryTree()
+        self.tree.get_height = lambda node: 0 if node is None else 1 + max(self.tree.get_height(node.left), self.tree.get_height(node.right))
+        self.height = self.tree.get_height(self.tree.root)
+
+    def update_game(self):
+        if not self.finished:
+            i = self.z.pop()
+            self.tree.insert(i)
+            self.height = self.tree.get_height(self.tree.root)
+            if len(self.z) == 0:
+                self.finished = True
+        return True
+
+    def draw_game(self):
+        self.screen.fill(WHITE)
+        if self.height > 0:
+            self.draw_tree(self.tree.root, WIDTH // 2, MARGIN, WIDTH // 4 - MARGIN)
+        super().draw_game()
+
+    def draw_tree(self, node, x, y, x_offset):
+        y_offset = (HEIGHT - (2 * MARGIN)) / self.height
+        if node is not None:
+            pygame.draw.circle(self.screen, BLUE, (x, y), 2)
+            if node.left is not None:
+                pygame.draw.line(self.screen, BLACK, (x, y), (x - x_offset, y + y_offset))
+                self.draw_tree(node.left, x - x_offset, y + y_offset, x_offset // 2)
+            if node.right is not None:
+                pygame.draw.line(self.screen, BLACK, (x, y), (x + x_offset, y + y_offset))
+                self.draw_tree(node.right, x + x_offset, y + y_offset, x_offset // 2)
+
+if __name__ == "__main__":
+    tree_game = BinTreeGame()
+    tree_game.run()
+

vorlesung/L05_binaere_baeume/bin_tree_node.py

@@ -18,7 +18,5 @@ class BinaryTreeNode(MemoryCell):
     def __str__(self):
         return str(self.value)
 
-    def gv_rep(self, row, col):
+    def graphviz_rep(self, row, col, dot):
-        """Returns the graphviz representation of the node."""
+        dot.node(str(id(self)), label=str(self.value), pos=f"{col},{-row}!")
-        return f"{id(self)} [label=\"{self.value}\", pos=\"{col},{-row}!\"];\n"
-

vorlesung/L06_b_baeume/analyze_b_tree.py

@@ -0,0 +1,58 @@
+from utils.memory_manager import MemoryManager
+from utils.memory_array import MemoryArray
+from utils.literal import Literal
+from b_tree import BTree
+from b_tree_node import BTreeNode
+
+class MemoryManagerBTree(MemoryManager):
+    """
+    Diese Klasse erweitert den MemoryManager, um spezifische Statistiken für B-Bäume zu speichern.
+    """
+
+    @staticmethod
+    def count_loads():
+        return sum([cell.loaded_count for cell in MemoryManager().cells if isinstance(cell, BTreeNode)])
+
+    @staticmethod
+    def count_saves():
+        return sum([cell.saved_count for cell in MemoryManager().cells if isinstance(cell, BTreeNode)])
+
+    @staticmethod
+    def save_stats(count):
+        data = {    "cells": MemoryManager.count_cells(),
+                    "reads": MemoryManager.count_reads(),
+                    "writes": MemoryManager.count_writes(),
+                    "compares": MemoryManager.count_compares(),
+                    "adds": MemoryManager.count_adds(),
+                    "subs": MemoryManager.count_subs(),
+                    "muls": MemoryManager.count_muls(),
+                    "divs": MemoryManager.count_divs(),
+                    "bitops": MemoryManager.count_bitops(),
+                    "loads": MemoryManagerBTree.count_loads(),
+                    "saves": MemoryManagerBTree.count_saves()  }
+        MemoryManager.stats[count] = data
+
+
+
+
+def analyze_complexity(sizes):
+    """
+    Analysiert die Komplexität
+
+    :param sizes: Eine Liste von Eingabegrößen für die Analyse.
+    """
+    for size in sizes:
+        MemoryManager.purge()  # Speicher zurücksetzen
+        tree = BTree(5)
+        random_array = MemoryArray.create_random_array(size, -100, 100)
+        for i in range(size-1):
+            tree.insert(int(random_array[Literal(i)]))
+        MemoryManager.reset()
+        tree.insert(int(random_array[Literal(size-1)]))
+        MemoryManagerBTree.save_stats(size)
+
+    MemoryManager.plot_stats(["cells", "compares", "loads", "saves"])
+
+if __name__ == "__main__":
+    sizes = range(1, 1001, 2)
+    analyze_complexity(sizes)

vorlesung/L06_b_baeume/b_tree.py

@@ -0,0 +1,120 @@
+from utils.literal import Literal
+from utils.memory_cell import MemoryCell
+from utils.memory_array import MemoryArray
+from b_tree_node import BTreeNode
+
+class BTree:
+    def __init__(self, m: int):
+        self.m = m
+        self.root = BTreeNode(m)
+
+    def search(self, value, start: BTreeNode = None) -> BTreeNode | None:
+        if not start:
+            start = self.root
+        start.load()
+        i = 0
+        if not isinstance(value, MemoryCell):
+            value = MemoryCell(value)
+        while i < start.n and value > start.value[Literal(i)]:
+            i += 1
+        if i < start.n and value == start.value[Literal(i)]:
+            return start
+        if start.leaf:
+            return None
+        return self.search(value, start.children[i])
+
+    def split_child(self, parent: BTreeNode, i: int):
+        child = parent.children[i]
+        child.load()
+        h = BTreeNode(self.m)
+        h.leaf = child.leaf
+        h.n = self.m - 1
+        for j in range(self.m - 1):
+            h.value[Literal(j)] = child.value[Literal(j + self.m)]
+        if not h.leaf:
+            for j in range(self.m):
+                h.children[j] = child.children[j + self.m]
+            for j in range(self.m, child.n + 1):
+                child.children[j] = None
+        child.n = self.m - 1
+        child.save()
+        h.save()
+        for j in range(parent.n, i, -1):
+            parent.children[j + 1] = parent.children[j]
+            parent.value[Literal(j)] = parent.value[Literal(j - 1)]
+        parent.children[i + 1] = h
+        parent.value[Literal(i)] = child.value[Literal(self.m - 1)]
+        parent.n += 1
+        parent.save()
+
+    def insert(self, value):
+        if not isinstance(value, MemoryCell):
+            value = MemoryCell(value)
+        r = self.root
+        if r.n == 2 * self.m - 1:
+            h = BTreeNode(self.m)
+            self.root = h
+            h.leaf = False
+            h.n = 0
+            h.children[0] = r
+            self.split_child(h, 0)
+            self.insert_in_node(h, value)
+        else:
+            self.insert_in_node(r, value)
+
+    def insert_in_node(self, start: BTreeNode, value):
+        start.load()
+        i = start.n
+        if start.leaf:
+            while i >= 1 and value < start.value[Literal(i-1)]:
+                start.value[Literal(i)] = start.value[Literal(i-1)]
+                i -= 1
+            start.value[Literal(i)].set(value)
+            start.n += 1
+            start.save()
+        else:
+            j = 0
+            while j < start.n and value > start.value[Literal(j)]:
+                j += 1
+            if start.children[j].n == 2 * self.m - 1:
+                self.split_child(start, j)
+                if value > start.value[Literal(j)]:
+                    j += 1
+            self.insert_in_node(start.children[j], value)
+
+    def traversal(self, callback):
+        def traversal_recursive(node, callback):
+            i = 0
+            while i < node.n:
+                if not node.leaf:
+                    traversal_recursive(node.children[i], callback)
+                callback(node.value[Literal(i)])
+                i += 1
+            if not node.leaf:
+                traversal_recursive(node.children[i], callback)
+
+        traversal_recursive(self.root, callback)
+
+    def walk(self):
+        def print_key(key):
+            print(key, end=" ")
+
+        self.traversal(print_key)
+
+    def height(self, start: BTreeNode = None):
+        if not start:
+            start = self.root
+        if start.leaf:
+            return 0
+        return 1 + self.height(start.children[0])
+
+
+if __name__ == "__main__":
+    a = MemoryArray.create_array_from_file("data/seq3.txt")
+    tree = BTree(3)
+    for cell in a:
+        tree.insert(cell)
+    print(f"Height: {tree.height()}")
+    tree.walk()
+    s = tree.search(0)
+    print(f"\nKnoten mit 0: {str(s)}")

vorlesung/L06_b_baeume/b_tree_node.py

@@ -0,0 +1,29 @@
+from utils.literal import Literal
+from utils.memory_cell import MemoryCell
+from utils.memory_array import MemoryArray
+
+class BTreeNode(MemoryCell):
+
+    def __init__(self, m: int):
+        super().__init__()
+        self.m = m
+        self.n = 0
+        self.leaf = True
+        self.value = MemoryArray(Literal(2 * m - 1))
+        self.children = [None] * (2 * m)
+        self.loaded_count = 0
+        self.saved_count = 0
+
+    def reset_counters(self):
+        super().reset_counters()
+        self.loaded_count = 0
+        self.saved_count = 0
+
+    def load(self):
+        self.loaded_count += 1
+
+    def save(self):
+        self.saved_count += 1
+
+    def __str__(self):
+        return "(" + " ".join([str(self.value[Literal(i)]) for i in range(self.n)]) + ")"

vorlesung/L07_hashtable/analyze_hashtable.py

@@ -0,0 +1,60 @@
+import math
+import random
+from utils.literal import Literal
+from utils.memory_cell import MemoryCell
+from utils.memory_array import MemoryArray
+from utils.memory_manager import MemoryManager
+from vorlesung.L07_hashtable.hashtable import HashTableOpenAddressing
+
+#Goldener Schnitt
+a = Literal((math.sqrt(5) - 1) / 2)
+
+# Hashfunktion nach multiplikativer Methode
+def h(x: MemoryCell, m: Literal) -> Literal:
+    with MemoryCell(int(x * a)) as integer_part, MemoryCell(x * a) as full_product:
+        with MemoryCell(full_product - integer_part) as fractional_part:
+            return Literal(abs(int(fractional_part * m)))
+
+# Quadratische Sondierung
+def f(x: MemoryCell, i: Literal, m: Literal) -> Literal:
+    c1 = 1
+    c2 = 5
+    with MemoryCell(h(x, m)) as initial_hash, MemoryCell(c2 * int(i) * int(i)) as quadratic_offset:
+        with MemoryCell(initial_hash + quadratic_offset) as probe_position:
+            probe_position += Literal(c1 * int(i)) # Linear component
+            return probe_position % m
+
+# Symmetrische quadratische Sondierung
+def fs(x: MemoryCell, i: Literal, m: Literal) -> Literal:
+    with MemoryCell(h(x, m)) as base_hash, MemoryCell(int(i) * int(i)) as square:
+        if int(i) % 2 == 0:  # gerades i: Vorwärtssondierung
+            with MemoryCell(base_hash + square) as position:
+                return position % m
+        else:  # ungerades i: Rückwärtssondierung
+            with MemoryCell(base_hash - square) as position:
+                return position % m
+
+
+def analyze_complexity(sizes):
+    """
+    Analysiert die Komplexität
+
+    :param sizes: Eine Liste von Eingabegrößen für die Analyse.
+    """
+    for size in sizes:
+        MemoryManager.purge()  # Speicher zurücksetzen
+        ht = HashTableOpenAddressing(size, f)
+        random_array = MemoryArray.create_random_array(size, -100, 100)
+        for cell in random_array:
+            ht.insert(cell)
+        MemoryManager.reset()
+        cell = random.choice(random_array.cells)
+        ht.search(cell)
+        MemoryManager.save_stats(size)
+
+    MemoryManager.plot_stats(["cells", "compares"])
+
+
+if __name__ == "__main__":
+    sizes = range(1, 1001, 10)
+    analyze_complexity(sizes)

vorlesung/L07_hashtable/hashtable.py

@@ -0,0 +1,76 @@
+from collections.abc import Callable
+from utils.literal import Literal
+from utils.memory_array import MemoryArray
+from utils.memory_cell import MemoryCell
+from utils.memory_range import mrange
+
+
+UNUSED_MARK = "UNUSED"
+DELETED_MARK = "DELETED"
+
+class HashTableOpenAddressing:
+    def __init__(self, m: Literal, f: Callable[[MemoryCell, Literal, Literal], Literal]):
+        if not isinstance(m, Literal):
+            m = Literal(m)
+        self.m = m
+        self.f = f
+        self.table = MemoryArray(m)
+        for i in mrange(m):
+            self.table[i].value = UNUSED_MARK
+
+    def insert(self, x: MemoryCell):
+        with MemoryCell(0) as i:
+            while i < self.m:
+                j = self.f(x, i, self.m)
+                if self.is_free(j):
+                    self.table[j].set(x)
+                    return True
+                i.set(i.succ())
+        return False
+
+    def search(self, x: MemoryCell):
+        with MemoryCell(0) as i:
+            while i < self.m:
+                j = self.f(x, i, self.m)
+                if self.is_unused(j):
+                    return False
+                if self.table[j] == x:
+                    return True
+                i.set(i.succ())
+        return False
+
+    def delete(self, x: MemoryCell):
+        with MemoryCell(0) as i:
+            while i < self.m:
+                j = self.f(x, i, self.m)
+                if self.is_unused(j):
+                    return False
+                if self.table[j] == x:
+                    self.table[j].value = DELETED_MARK
+                    return True
+                i.set(i.succ())
+        return False
+
+    def __str__(self):
+        return str(self.table)
+
+    def alpha(self):
+        with MemoryCell(0) as i:
+            used = 0
+            while i < self.m:
+                used += 0 if self.is_free(i) else 1
+                i.set(i.succ())
+        return used / int(self.m)
+
+    def is_unused(self, i: Literal):
+        if self.table[i].value == UNUSED_MARK:
+            return True
+        return False
+
+    def is_deleted(self, i: Literal):
+        if self.table[i].value == DELETED_MARK:
+            return True
+        return False
+
+    def is_free(self, i: Literal):
+        return self.is_unused(i) or self.is_deleted(i)

vorlesung/L08_graphen/aoc2212.py

@@ -0,0 +1,45 @@
+from vorlesung.L08_graphen.graph import Graph, AdjacencyMatrixGraph
+from utils.project_dir import get_path
+
+graph = AdjacencyMatrixGraph()
+start = ""
+end = ""
+
+def read_file(filename: str = "data/aoc2212.txt"):
+    """Read a file and return the content as a string."""
+
+    def adjust_char(char):
+        """Adjust character for comparison."""
+        if char == 'S':
+            return 'a'
+        elif char == 'E':
+            return 'z'
+        return char
+
+    global start, end
+    with open(get_path(filename), "r") as file:
+        quest = file.read().strip().splitlines()
+    for row, line in enumerate(quest):
+        for col, char in enumerate(line):
+            label = f"{row},{col}"
+            graph.insert_vertex(label)
+            if char == "S":
+                start = label
+            if char == "E":
+                end = label
+    for row, line in enumerate(quest):
+        for col, char in enumerate(line):
+            for neighbor in [(row - 1, col), (row, col - 1), (row + 1, col), (row, col + 1)]:
+                if 0 <= neighbor[0] < len(quest) and 0 <= neighbor[1] < len(line):
+                    if ord(adjust_char(quest[neighbor[0]][neighbor[1]])) <= ord(adjust_char(char)) + 1:
+                        label1 = f"{row},{col}"
+                        label2 = f"{neighbor[0]},{neighbor[1]}"
+                        graph.connect(label1, label2)
+
+
+# Lösung des Adventskalenders 2022, Tag 12
+read_file("data/aoc2212test.txt")
+graph.graph()
+distance_map, predecessor_map = graph.bfs(start)
+print(distance_map[graph.get_vertex(end)])
+print(graph.path(end, predecessor_map))

vorlesung/L08_graphen/graph.py

@@ -0,0 +1,366 @@
+from collections import deque
+from typing import List
+from enum import Enum
+import graphviz
+import math
+import heapq
+from datetime import datetime
+from utils.project_dir import get_path
+from utils.priority_queue import PriorityQueue
+from vorlesung.L09_mst.disjoint import DisjointValue
+
+
+class NodeColor(Enum):
+    """Enumeration for node colors in a graph traversal."""
+    WHITE = 1       # WHITE: not visited
+    GRAY = 2        # GRAY: visited but not all neighbors visited
+    BLACK = 3       # BLACK: visited and all neighbors visited
+
+
+class Vertex:
+    """A vertex in a graph."""
+    def __init__(self, value):
+        self.value = value
+
+    def __str__(self):
+        return str(self.value)
+
+    def __repr__(self):
+        return f"Vertex({self.value})"
+
+
+
+class Graph:
+    """A graph."""
+    def insert_vertex(self, name: str):
+        raise NotImplementedError("Please implement this method in subclass")
+
+    def connect(self, name1: str, name2: str, weight: float = 1):
+        raise NotImplementedError("Please implement this method in subclass")
+
+    def all_vertices(self) -> List[Vertex]:
+        raise NotImplementedError("Please implement this method in subclass")
+
+    def get_vertex(self, name: str) -> Vertex:
+        raise NotImplementedError("Please implement this method in subclass")
+
+    def get_adjacent_vertices(self, name: str) -> List[Vertex]:
+        raise NotImplementedError("Please implement this method in subclass")
+
+    def get_adjacent_vertices_with_weight(self, name: str) -> List[tuple[Vertex, float]]:
+        raise NotImplementedError("Please implement this method in subclass")
+
+    def all_edges(self) -> List[tuple[str, str, float]]:
+        raise NotImplementedError("Please implement this method in subclass")
+
+    def bfs(self, start_name: str):
+        """
+        Perform a breadth-first search starting at the given vertex.
+        :param start_name: the name of the vertex to start at
+        :return: a tuple of two dictionaries, the first mapping vertices to distances from the start vertex,
+                 the second mapping vertices to their predecessors in the traversal tree
+        """
+
+        color_map = {}                  # maps vertices to their color
+        distance_map = {}               # maps vertices to their distance from the start vertex
+        predecessor_map = {}            # maps vertices to their predecessor in the traversal tree
+
+        # Initialize the maps
+        for vertex in self.all_vertices():
+            color_map[vertex] = NodeColor.WHITE
+            distance_map[vertex] = None
+            predecessor_map[vertex] = None
+
+        # Start at the given vertex
+        start_node = self.get_vertex(start_name)
+        color_map[start_node] = NodeColor.GRAY
+        distance_map[start_node] = 0
+
+        # Initialize the queue with the start vertex
+        queue = deque()
+        queue.append(start_node)
+
+        # Process the queue
+        while len(queue) > 0:
+            vertex = queue.popleft()
+            for dest in self.get_adjacent_vertices(vertex.value):
+                if color_map[dest] == NodeColor.WHITE:
+                    color_map[dest] = NodeColor.GRAY
+                    distance_map[dest] = distance_map[vertex] + 1
+                    predecessor_map[dest] = vertex
+                    queue.append(dest)
+            color_map[vertex] = NodeColor.BLACK
+
+        # Return the distance and predecessor maps
+        return distance_map, predecessor_map
+
+    def dfs(self):
+        """
+        Perform a depth-first search starting at the first vertex.
+        :return: a tuple of two dictionaries, the first mapping vertices to distances from the start vertex,
+                 the second mapping vertices to their predecessors in the traversal tree
+        """
+        color_map : dict[Vertex, NodeColor]= {}
+        enter_map : dict[Vertex, int] = {}
+        leave_map : dict[Vertex, int] = {}
+        predecessor_map : dict[Vertex, Vertex | None] = {}
+        white_vertices = set(self.all_vertices())
+        time_counter = 0
+
+        def dfs_visit(vertex):
+            nonlocal time_counter
+            color_map[vertex] = NodeColor.GRAY
+            white_vertices.remove(vertex)
+            time_counter += 1
+            enter_map[vertex] = time_counter
+            for dest in self.get_adjacent_vertices(vertex.value):
+                if color_map[dest] == NodeColor.WHITE:
+                    predecessor_map[dest] = vertex
+                    dfs_visit(dest)
+            color_map[vertex] = NodeColor.BLACK
+            time_counter += 1
+            leave_map[vertex] = time_counter
+
+        # Initialize the maps
+        for vertex in self.all_vertices():
+            color_map[vertex] = NodeColor.WHITE
+            predecessor_map[vertex] = None
+
+        while white_vertices:
+            v = white_vertices.pop()
+            dfs_visit(v)
+
+        return enter_map, leave_map, predecessor_map
+
+
+    def path(self, destination, map):
+        """
+        Compute the path from the start vertex to the given destination vertex.
+        The map parameter is the predecessor map
+        """
+        path = []
+        destination_node = self.get_vertex(destination)
+        while destination_node is not None:
+            path.insert(0, destination_node.value)
+            destination_node = map[destination_node]
+        return path
+
+    def graph(self, filename: str = "Graph"):
+        dot = graphviz.Digraph( name=filename,
+                                node_attr={"fontname": "Arial"},
+                                format="pdf" )
+        for vertex in self.all_vertices():
+            dot.node(str(id(vertex)), label=str(vertex.value))
+        for edge in self.all_edges():
+            dot.edge(str(id(self.get_vertex(edge[0]))), str(id(self.get_vertex(edge[1]))), label=str(edge[2]))
+        timestamp = datetime.now().strftime("%Y%m%d_%H%M%S")
+        filename = f"{filename}_{timestamp}.gv"
+        filename = get_path(filename)
+        dot.render(filename)
+
+    def dijkstra(self, start_name: str) -> tuple[dict[Vertex, float], dict[Vertex, Vertex | None]]:
+        """
+        Führt den Dijkstra-Algorithmus für kürzeste Pfade durch, implementiert mit Knotenfarben.
+
+        Args:
+            start_name: Name des Startknotens
+
+        Returns:
+            Ein Tupel aus zwei Dictionaries:
+            - distance_map: Abbildung von Knoten auf ihre kürzeste Distanz vom Startknoten
+            - predecessor_map: Abbildung von Knoten auf ihre Vorgänger im kürzesten Pfad
+        """
+
+        def relax(vertex, dest, weight):
+            """
+            Entspannt die Kante zwischen vertex und dest.
+            Aktualisiert die Distanz und den Vorgänger, wenn ein kürzerer Pfad gefunden wird.
+            """
+            if distance_map[vertex] + weight < distance_map[dest]:
+                distance_map[dest] = distance_map[vertex] + weight
+                predecessor_map[dest] = vertex
+                queue.add_or_update(dest, distance_map[dest])
+
+        # Initialisierung der Maps
+        distance_map = {}  # Speichert kürzeste Distanzen
+        predecessor_map = {}  # Speichert Vorgänger
+
+        # Initialisiere alle Knoten
+        queue = PriorityQueue()
+        for vertex in self.all_vertices():
+            distance_map[vertex] = float('inf')  # Initiale Distanz unendlich
+            predecessor_map[vertex] = None  # Initialer Vorgänger None
+            queue.add_or_update(vertex, distance_map[vertex])  # Füge Knoten zur Prioritätswarteschlange hinzu
+
+
+
+        # Setze Startknoten
+        start_node = self.get_vertex(start_name)
+        distance_map[start_node] = 0
+        queue.add_or_update(start_node, distance_map[start_node])
+
+        while True:
+            entry = queue.pop()
+            if entry is None:
+                break
+            vertex = entry[0]
+            for dest, weight in self.get_adjacent_vertices_with_weight(vertex.value):
+                relax(vertex, dest, weight)
+        return distance_map, predecessor_map
+
+    def mst_prim(self, start_name: str = None):
+        """ Compute the minimum spanning tree of the graph using Prim's algorithm. """
+
+        distance_map = {}   # maps vertices to their current distance from the spanning tree
+        parent_map = {}     # maps vertices to their predecessor in the spanning tree
+
+        Vertex.__lt__ = lambda self, other: distance_map[self] < distance_map[other]
+
+        queue = []
+
+        if start_name is None:
+            start_name = self.all_vertices()[0].value
+
+        # Initialize the maps
+        for vertex in self.all_vertices():
+            distance_map[vertex] = 0 if vertex.value == start_name else math.inf
+            parent_map[vertex] = None
+            queue.append(vertex)
+
+        heapq.heapify(queue)    # Convert the list into a heap
+
+        # Process the queue
+        cost = 0 # The cost of the minimum spanning tree
+        while len(queue) > 0:
+            vertex = heapq.heappop(queue)
+            cost += distance_map[vertex] # Add the cost of the edge to the minimum spanning tree
+            for (dest, w) in self.get_adjacent_vertices_with_weight(vertex.value):
+                if dest in queue and distance_map[dest] > w:
+                    # Update the distance and parent maps
+                    queue.remove(dest)
+                    distance_map[dest] = w
+                    parent_map[dest] = vertex
+                    queue.append(dest)      # Add the vertex back to the queue
+                    heapq.heapify(queue)    # Re-heapify the queue
+
+        # Return the distance and predecessor maps
+        return parent_map, cost
+
+    def mst_kruskal(self, start_name: str = None):
+        """ Compute the minimum spanning tree of the graph using Kruskal's algorithm. """
+
+        cost = 0
+        result = []
+        edges = self.all_edges()
+
+        # Create a disjoint set for each vertex
+        vertex_map = {v.value: DisjointValue(v) for v in self.all_vertices()}
+
+        # Sort the edges by weight
+        edges.sort(key=lambda edge: edge[2])
+
+        # Process the edges
+        for edge in edges:
+            start_name, end_name, weight = edge
+            # Check if the edge creates a cycle
+            if not vertex_map[start_name].same_set(vertex_map[end_name]):
+                result.append(edge)
+                vertex_map[start_name].union(vertex_map[end_name])
+                cost += weight
+
+        return result, cost
+
+
+class AdjacencyListGraph(Graph):
+    """A graph implemented as an adjacency list."""
+    def __init__(self):
+        self.adjacency_map = {}     # maps vertex names to lists of adjacent vertices
+        self.vertex_map = {}        # maps vertex names to vertices
+
+    def insert_vertex(self, name: str):
+        if name not in self.vertex_map:
+            self.vertex_map[name] = Vertex(name)
+        if name not in self.adjacency_map:
+            self.adjacency_map[name] = []
+
+    def connect(self, name1: str, name2: str, weight: float = 1):
+        adjacency_list = self.adjacency_map[name1]
+        dest = self.vertex_map[name2]
+        adjacency_list.append((dest, weight))
+
+    def all_vertices(self) -> List[Vertex]:
+        return list(self.vertex_map.values())
+
+    def get_vertex(self, name: str) -> Vertex:
+        return self.vertex_map[name]
+
+    def get_adjacent_vertices(self, name: str) -> List[Vertex]:
+        return list(map(lambda x: x[0], self.adjacency_map[name]))
+
+    def get_adjacent_vertices_with_weight(self, name: str) -> List[tuple[Vertex, float]]:
+        return self.adjacency_map[name]
+
+    def all_edges(self) -> List[tuple[str, str, float]]:
+        result = []
+        for name in self.adjacency_map:
+            for (dest, weight) in self.adjacency_map[name]:
+                result.append((name, dest.value, weight))
+        return result
+
+
+class AdjacencyMatrixGraph(Graph):
+    """A graph implemented as an adjacency matrix."""
+    def __init__(self):
+        self.index_map = {}         # maps vertex names to indices
+        self.vertex_list = []       # list of vertices
+        self.adjacency_matrix = []  # adjacency matrix
+
+    def insert_vertex(self, name: str):
+        if name not in self.index_map:
+            self.index_map[name] = len(self.vertex_list)
+            self.vertex_list.append(Vertex(name))
+            for row in self.adjacency_matrix:   # add a new column to each row
+                row.append(None)
+            self.adjacency_matrix.append([None] * len(self.vertex_list)) # add a new row
+
+    def connect(self, name1: str, name2: str, weight: float = 1):
+        index1 = self.index_map[name1]
+        index2 = self.index_map[name2]
+        self.adjacency_matrix[index1][index2] = weight
+
+
+    def all_vertices(self) -> List[Vertex]:
+        return self.vertex_list
+
+    def get_vertex(self, name: str) -> Vertex:
+        index = self.index_map[name]
+        return self.vertex_list[index]
+
+    def get_adjacent_vertices(self, name: str) -> List[Vertex]:
+        index = self.index_map[name]
+        result = []
+        for i in range(len(self.vertex_list)):
+            if self.adjacency_matrix[index][i] is not None:
+                name = self.vertex_list[i].value
+                result.append(self.get_vertex(name))
+        return result
+
+    def get_adjacent_vertices_with_weight(self, name: str) -> List[tuple[Vertex, float]]:
+        index = self.index_map[name]
+        result = []
+        for i in range(len(self.vertex_list)):
+            if self.adjacency_matrix[index][i] is not None:
+                name = self.vertex_list[i].value
+                result.append((self.get_vertex(name), self.adjacency_matrix[index][i]))
+        return result
+
+    def all_edges(self) -> List[tuple[str, str, float]]:
+        result = []
+        for i in range(len(self.vertex_list)):
+            for j in range(len(self.vertex_list)):
+                if self.adjacency_matrix[i][j] is not None:
+                    result.append((self.vertex_list[i].value, self.vertex_list[j].value, self.adjacency_matrix[i][j]))
+        return result
+
+
+

vorlesung/L09_mst/disjoint.py

@@ -0,0 +1,18 @@
+
+
+class DisjointValue():
+
+    def __init__(self, value):
+        self.value = value
+        self.parent = None
+
+    def canonical(self):
+        if self.parent:
+            return self.parent.canonical()
+        return self
+
+    def same_set(self, other):
+        return self.canonical() == other.canonical()
+
+    def union(self, other):
+        self.canonical().parent = other.canonical()