From e5c3b094424194754630d1b08db9f3e668c0fd8b Mon Sep 17 00:00:00 2001
From: Hong-Phuc Bui <hong-phuc.bui@htwsaar.de>
Date: Tue, 24 Jun 2025 10:16:54 +0200
Subject: [PATCH] stundenplan
---
stundenplan/src/pygraph/__init__.py | 0
stundenplan/src/pygraph/graphdemo.py | 117 ++++++++++++++++
stundenplan/tests/pygraph/__init__.py | 0
stundenplan/tests/pygraph/graphdemo_tests.py | 88 ++++++++++++
stundenplan/src/stundenplan.egg-info/top_level.txt | 1
stundenplan/tests/__init__.py | 0
stundenplan/src/stundenplan.egg-info/PKG-INFO | 3
stundenplan/src/stundenplan.egg-info/dependency_links.txt | 1
stundenplan/src/pygraph/shortestpath.py | 79 +++++++++++
stundenplan/tests/pygraph/shortestpath_tests.py | 57 ++++++++
stundenplan/pyproject.toml | 17 ++
stundenplan/Readme.md | 21 +++
stundenplan/src/stundenplan.egg-info/SOURCES.txt | 8 +
13 files changed, 392 insertions(+), 0 deletions(-)
diff --git a/stundenplan/Readme.md b/stundenplan/Readme.md
new file mode 100644
index 0000000..00ba398
--- /dev/null
+++ b/stundenplan/Readme.md
@@ -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"
+```
\ No newline at end of file
diff --git a/stundenplan/pyproject.toml b/stundenplan/pyproject.toml
new file mode 100644
index 0000000..8fd56e0
--- /dev/null
+++ b/stundenplan/pyproject.toml
@@ -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"
+
+
diff --git a/stundenplan/src/pygraph/__init__.py b/stundenplan/src/pygraph/__init__.py
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/stundenplan/src/pygraph/__init__.py
diff --git a/stundenplan/src/pygraph/graphdemo.py b/stundenplan/src/pygraph/graphdemo.py
new file mode 100644
index 0000000..d8669be
--- /dev/null
+++ b/stundenplan/src/pygraph/graphdemo.py
@@ -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
diff --git a/stundenplan/src/pygraph/shortestpath.py b/stundenplan/src/pygraph/shortestpath.py
new file mode 100644
index 0000000..5d3e2af
--- /dev/null
+++ b/stundenplan/src/pygraph/shortestpath.py
@@ -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
\ No newline at end of file
diff --git a/stundenplan/src/stundenplan.egg-info/PKG-INFO b/stundenplan/src/stundenplan.egg-info/PKG-INFO
new file mode 100644
index 0000000..121e906
--- /dev/null
+++ b/stundenplan/src/stundenplan.egg-info/PKG-INFO
@@ -0,0 +1,3 @@
+Metadata-Version: 2.1
+Name: stundenplan
+Version: 0.0.1
diff --git a/stundenplan/src/stundenplan.egg-info/SOURCES.txt b/stundenplan/src/stundenplan.egg-info/SOURCES.txt
new file mode 100644
index 0000000..a47d17f
--- /dev/null
+++ b/stundenplan/src/stundenplan.egg-info/SOURCES.txt
@@ -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
\ No newline at end of file
diff --git a/stundenplan/src/stundenplan.egg-info/dependency_links.txt b/stundenplan/src/stundenplan.egg-info/dependency_links.txt
new file mode 100644
index 0000000..8b13789
--- /dev/null
+++ b/stundenplan/src/stundenplan.egg-info/dependency_links.txt
@@ -0,0 +1 @@
+
diff --git a/stundenplan/src/stundenplan.egg-info/top_level.txt b/stundenplan/src/stundenplan.egg-info/top_level.txt
new file mode 100644
index 0000000..ba98b63
--- /dev/null
+++ b/stundenplan/src/stundenplan.egg-info/top_level.txt
@@ -0,0 +1 @@
+pygraph
diff --git a/stundenplan/tests/__init__.py b/stundenplan/tests/__init__.py
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/stundenplan/tests/__init__.py
diff --git a/stundenplan/tests/pygraph/__init__.py b/stundenplan/tests/pygraph/__init__.py
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/stundenplan/tests/pygraph/__init__.py
diff --git a/stundenplan/tests/pygraph/graphdemo_tests.py b/stundenplan/tests/pygraph/graphdemo_tests.py
new file mode 100644
index 0000000..d8d1ba5
--- /dev/null
+++ b/stundenplan/tests/pygraph/graphdemo_tests.py
@@ -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()
diff --git a/stundenplan/tests/pygraph/shortestpath_tests.py b/stundenplan/tests/pygraph/shortestpath_tests.py
new file mode 100644
index 0000000..dc914a1
--- /dev/null
+++ b/stundenplan/tests/pygraph/shortestpath_tests.py
@@ -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()
--
Gitblit v1.10.0