stundenplan

Hong-Phuc Bui

2 days ago e5c3b094424194754630d1b08db9f3e668c0fd8b

stundenplan

 stundenplan/Readme.md

New file
@@ -0,0 +1,21 @@
# Beispielanwendung von Graph

## Installation

Installation das Projekt auf einem virtuellen Python-Umgebung:

````shell
pip install -e .
````

## Run Unittest

```shell
python3 -m unittest discover --pattern *tests.py
```

## Run programm

```shell
echo "TODO: to be done by student"
```

 stundenplan/pyproject.toml

New file
@@ -0,0 +1,17 @@
[build-system]
requires = ["setuptools"]
build-backend = "setuptools.build_meta"

[project]
name = "stundenplan"
version = "0.0.1"

[tool.setuptools.packages.find]
# All the following settings are optional:
where = ["src"]

# [project.scripts]
# To be done
# studenplan = "TODO: to-be-done"



 stundenplan/src/pygraph/__init__.py

 stundenplan/src/pygraph/graphdemo.py

New file
@@ -0,0 +1,117 @@
from typing import Any, Callable


class Graph:
    """
    represents an undirected and unweighted Graph
    """
    def __init__(self):
        self._adjacent: dict[int, set] = {}
        self._vertex_attribute: dict[int, dict] = {}

    def add_vertex(self, vertex:int):
        if vertex not in self._adjacent:
            if not isinstance(vertex, int):
                raise TypeError(f"Argument {vertex} is not a valid vertex")
            self._adjacent[vertex] = set()
            self._vertex_attribute[vertex] = {}
        pass

    def add_edge(self, u: int, v: int):
        self.add_vertex(u)
        self.add_vertex(v)
        v_neighbor = self._adjacent[v]
        if u not in v_neighbor:
            v_neighbor.add(u)
        u_neighbor = self._adjacent[u]
        if v not in u_neighbor:
            u_neighbor.add(v)
        pass

    def add_edges(self, u: int, adjacent: list[int]):
        for v in adjacent:
            self.add_edge(u, v)
        pass

    def merge_attribute(self, vertex: int, properties: dict):
        """
        merge a dict of attribute to a vertex. Usage example:
        ```
        g = Graph();
        g.add_vertex(1);
        g.mergeAttribute(1, {'color': 0});
        ```
        :param vertex:
        :param properties:
        :return: self
        """
        if vertex not in self._adjacent:
            raise ValueError(f"Graph does not include vertex {vertex}")
        old_attributes = self._vertex_attribute[vertex]
        self._vertex_attribute[vertex] = old_attributes | properties
        return self
        pass

    def get_attribute(self, vertex: int):
        if vertex in self._adjacent:
            return self._vertex_attribute[vertex]
        else:
            raise ValueError(f"Graph does not include vertex {vertex}")
        pass

    def vertices(self):
        """
        returns the set of vertices in not defined order.
        :return:
        """
        return self._adjacent.keys()

    def for_each_vertices(self, action: Callable[[int], Any]):
        """
        iterates over all vertices in this graph in ascending order.
        :param action:
        :return:
        """
        for v in sorted( self.vertices() ):
            action(v)

    def adjacent_of(self, vertex: int):
        if vertex not in self._adjacent:
            raise ValueError(f"Graph does not include vertex {vertex}")
        return sorted( self._adjacent[vertex] )

    def for_each_edges(self, action: Callable[[int, int], Any]):
        """
        iterates over all edges of the graph, executes the action on each edge.
        :param action: a binary function, its parameters are start and end vertices of the visited edges
        """
        visited_edges: dict[int, set] = {}
        for start in sorted( self.vertices() ):
            for end in self.adjacent_of(start):
                (first, second) = (start, end) if (start >= end) else (end, start)
            if first in visited_edges:
                #visited_adjacent = visited_edges.get(first)
                visited_adjacent = visited_edges[first]
                if second not in visited_adjacent:
                    visited_adjacent.add(second)
                    action(start, end)
            else:
                adjacent: set[int] = set()
                visited_edges[first] = adjacent
                adjacent.add(second)
                action(start, end)



    def __repr__(self):
        text = ""
        sorted_key = sorted(self._adjacent.keys())
        last_key = sorted_key.pop()
        def adjacent_fn(vertex): return "[" + ", ".join([str(v) for v in self._adjacent[vertex]]) + "]"
        for key in sorted_key:
            text += f"{key} → {adjacent_fn(key)}\n"
        text += f"{last_key} → {adjacent_fn(last_key)}"
        return text

    def to_dot(self) -> str:
        pass

 stundenplan/src/pygraph/shortestpath.py

New file
@@ -0,0 +1,79 @@
import collections
from typing import Mapping

from pygraph.graphdemo import Graph


def bfs(g: Graph, start: int) -> Graph:
    """

    :param g:
    :param start:
    :return:
    """
    tree = Graph()
    queue = collections.deque()
    VISITED = "visited"
    not_visited = {VISITED: False}
    visited = {VISITED: True}
    g.for_each_vertices(lambda v : g.merge_attribute(v, not_visited))
    queue.append(start)  # append() is the enqueue() operation of a Queue
    g.merge_attribute(start, visited)
    while queue:
        u = queue.popleft()  # popleft() is the dequeue() operation of a Queue
        for v in g.adjacent_of(u):
            if not g.get_attribute(v)[VISITED]:
                tree.add_edge(u, v)
                g.merge_attribute(v, visited)
                queue.append(v)
    return tree


def bfs_dict(g: Graph, start: int) -> Mapping[int, int|None]:
    tree = {start:None}
    queue = collections.deque()
    VISITED = "visited"
    not_visited = {VISITED: False}
    visited = {VISITED: True}
    g.for_each_vertices(lambda v : g.merge_attribute(v, not_visited))
    queue.append(start)  # append() is the enqueue() operation of a Queue
    g.merge_attribute(start, visited)
    while queue:
        u = queue.popleft()  # popleft() is the dequeue() operation of a Queue
        for v in g.adjacent_of(u):
            if not g.get_attribute(v)[VISITED]:
                tree[v] = u
                g.merge_attribute(v, visited)
                queue.append(v)
    return tree
    pass


def find_path(g: Graph, u: int, v: int) -> list[int]:
    tree = bfs_dict(g, v)
    path = [u]
    while (current := path[-1]) != v:
        precedent = tree[current]
        path.append(precedent)
    return path


def find_path_gpt(g: Graph, u: int, v: int) -> list[int]:
    # Erstelle einen BFS-Baum, beginnend bei Knoten v
    bfs_tree = bfs_dict(g, v)

    # Wenn u nicht in bfs_tree ist, gibt es keinen Pfad von u nach v
    if u not in bfs_tree:
        return []  # Kein Pfad gefunden

    # Den Pfad von u nach v rekonstruieren
    path = []
    current = u
    while current is not None:
        path.append(current)
        current = bfs_tree[current]

    # Den Pfad umkehren, da wir rückwärts von u nach v gehen
    path.reverse()

    return path

 stundenplan/src/stundenplan.egg-info/PKG-INFO

New file
@@ -0,0 +1,3 @@
Metadata-Version: 2.1
Name: stundenplan
Version: 0.0.1

 stundenplan/src/stundenplan.egg-info/SOURCES.txt

New file
@@ -0,0 +1,8 @@
pyproject.toml
src/pygraph/__init__.py
src/pygraph/graphdemo.py
src/pygraph/shortestpath.py
src/stundenplan.egg-info/PKG-INFO
src/stundenplan.egg-info/SOURCES.txt
src/stundenplan.egg-info/dependency_links.txt
src/stundenplan.egg-info/top_level.txt

 stundenplan/src/stundenplan.egg-info/dependency_links.txt

New file
@@ -0,0 +1 @@


 stundenplan/src/stundenplan.egg-info/top_level.txt

New file
@@ -0,0 +1 @@
pygraph

 stundenplan/tests/__init__.py

 stundenplan/tests/pygraph/__init__.py

 stundenplan/tests/pygraph/graphdemo_tests.py

New file
@@ -0,0 +1,88 @@
import unittest

from pygraph.graphdemo import Graph


class GraphTestCase(unittest.TestCase):
    def test_construct_a_graph(self):
        g = Graph()
        g.add_edge(1, 2)
        g.add_edge(1, 3)
        g.add_edge(2, 3)
        g.add_edge(2, 4)
        txt = str(g)
        expected = '''1 → [2, 3]
2 → [1, 3, 4]
3 → [1, 2]
4 → [2]'''
        self.assertEqual(expected, txt)
        vertices = [1, 2, 3, 4]
        # def action(v): self.assertTrue(v in vertices)
        g.for_each_vertices(lambda v : self.assertTrue(v in vertices))

    def test_iterate_all_edges(self):
        g = Graph()
        g.add_edge(1, 2)
        g.add_edge(1, 3)
        g.add_edge(2, 3)
        g.add_edge(2, 4)
        edges = [
            "1-2", "1-3", "2-3", "2-4"
        ]
        def action(a, b):
            (s,e) = (a,b) if a < b else (b,a)
            edge = f"{s}-{e}"
            self.assertTrue(edge in edges)
        g.for_each_edges(action)

    def test_iterate_all_vertices(self):
        g = Graph()
        g.add_edge(1, 2)
        g.add_edge(1, 3)
        g.add_edge(2, 3)
        g.add_edge(2, 4)
        vertices = []
        for v in g.vertices():
            vertices.append(v)
        expected = [1, 2, 3, 4]
        self.assertListEqual(sorted(vertices), expected)
        pass

    def test_iterate_neighbor_vertex(self):
        g = Graph()
        g.add_edge(1, 2)
        g.add_edge(1, 3)
        g.add_edge(2, 3)
        g.add_edge(2, 4)
        g.add_edge(4, 1)
        vertices = []
        for v in g.adjacent_of(1):
            vertices.append(v)
        expected = [2, 3, 4]
        self.assertListEqual(sorted(vertices), expected)
        pass

    def test_not_add_float_to_vertex(self):
        g = Graph()
        try:
            g.add_vertex(1.2)
            pass
        except TypeError as ex:
            expected_msg = "Argument 1.2 is not a valid vertex"
            self.assertEqual(str(ex), expected_msg)
            pass
        pass

    def test_not_add_string_to_vertex(self):
        g = Graph()
        try:
            g.add_vertex("add")
        except TypeError as ex:
            expected_msg = 'Argument add is not a valid vertex'
            self.assertEqual(str(ex), expected_msg)
            pass
        pass


if __name__ == '__main__':
    unittest.main()

 stundenplan/tests/pygraph/shortestpath_tests.py

New file
@@ -0,0 +1,57 @@
import unittest

from pygraph.graphdemo import Graph
from pygraph.shortestpath import bfs, bfs_dict, find_path, find_path_gpt


class ShortestPathTestCase(unittest.TestCase):
    def test_bfs(self):
        g = Graph()
        g.add_edges(0, [1, 2])
        g.add_edges(1, [3, 4])
        g.add_edges(2, [4, 6, 7])
        g.add_edges(4, [5])
        print(g)
        print("#")
        tree = bfs(g, 0)
        print(tree)

    def test_bfs_dict(self):
        g = Graph()
        g.add_edges(0, [1, 2])
        g.add_edges(1, [3, 4])
        g.add_edges(2, [4, 6, 7])
        g.add_edges(4, [5])
        print(g)
        tree = bfs_dict(g, 6)
        print("Tree from Vertex 6")
        print(tree)

    def test_find_path(self):
        g = Graph()
        g.add_edges(0, [1, 2])
        g.add_edges(1, [3, 4])
        g.add_edges(2, [4, 6, 7])
        g.add_edges(4, [5])
        print(g)
        (u, v) = (6, 5)
        path = find_path(g, 6, 5)
        print(f"path from {u} to {v}")
        print(path)

    def test_find_path_gpt(self):
        g = Graph()
        g.add_edges(0, [1, 2])
        g.add_edges(1, [3, 4])
        g.add_edges(2, [4, 6, 7])
        g.add_edges(4, [5])
        print(g)
        (u, v) = (6, 5)
        path = find_path_gpt(g, 6, 5)
        print(f"path from {u} to {v}")
        print(path)



if __name__ == '__main__':
    unittest.main()