From 273021dcef9c23610790e47a109fcbf476b829ec Mon Sep 17 00:00:00 2001
From: Hong-Phuc Bui <hong-phuc.bui@htwsaar.de>
Date: Sun, 25 Aug 2024 19:11:08 +0200
Subject: [PATCH] example about graph
---
.gitignore | 3 -
num-int/src/numint/mainwindow.ui | 2
stundenplan/src/pygraph/graphdemo.py | 30 ++++++++++++---
stundenplan/src/pygraph/shortestpath.py | 28 ++++++++++++++
stundenplan/tests/pygraph/shortestpath_tests.py | 26 +++++++++++++
5 files changed, 79 insertions(+), 10 deletions(-)
diff --git a/.gitignore b/.gitignore
index 6f12ec8..e019710 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,7 +1,4 @@
-sandbox*
-queens*
*.venv*
__pycache__/
.idea/
-htw-python-kurs-2024-mmb/
*.egg-info/
\ No newline at end of file
diff --git a/num-int/src/numint/mainwindow.ui b/num-int/src/numint/mainwindow.ui
index 8f1f47f..e8f8a18 100644
--- a/num-int/src/numint/mainwindow.ui
+++ b/num-int/src/numint/mainwindow.ui
@@ -11,7 +11,7 @@
</rect>
</property>
<property name="windowTitle">
- <string>Riemann Sum</string>
+ <string>Riemann Sums</string>
</property>
<widget class="QWidget" name="centralwidget">
<layout class="QHBoxLayout" name="horizontalLayout_2">
diff --git a/stundenplan/src/pygraph/graphdemo.py b/stundenplan/src/pygraph/graphdemo.py
index c0e3df9..2a6cf7d 100644
--- a/stundenplan/src/pygraph/graphdemo.py
+++ b/stundenplan/src/pygraph/graphdemo.py
@@ -6,7 +6,7 @@
self._adjacent: dict[int, set] = {}
self._vertex_attribute: dict[int, dict] = {}
- def add_vertex(self, vertex):
+ 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")
@@ -14,7 +14,7 @@
self._vertex_attribute[vertex] = {}
pass
- def add_edge(self, u, v):
+ def add_edge(self, u: int, v: int):
self.add_vertex(u)
self.add_vertex(v)
v_neighbor = self._adjacent[v]
@@ -25,6 +25,11 @@
u_neighbor.add(v)
pass
+ def add_edges(self, u: int, adjacent:[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:
@@ -39,7 +44,7 @@
"""
if vertex not in self._adjacent:
raise ValueError(f"Graph does not include vertex {vertex}")
- old_attributes = self._vertex_attribute.get[vertex]
+ old_attributes = self._vertex_attribute.get(vertex)
self._vertex_attribute[vertex] = old_attributes | properties
return self
pass
@@ -52,20 +57,33 @@
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]):
- for v in self.vertices():
+ """
+ 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 self._adjacent.get(vertex)
+ return sorted( self._adjacent.get(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 self.vertices():
+ 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:
diff --git a/stundenplan/src/pygraph/shortestpath.py b/stundenplan/src/pygraph/shortestpath.py
new file mode 100644
index 0000000..4426f95
--- /dev/null
+++ b/stundenplan/src/pygraph/shortestpath.py
@@ -0,0 +1,28 @@
+import collections
+
+from pygraph.graphdemo import Graph
+
+
+def bfs(g: Graph, start: int) -> {int:int|None}:
+ """
+
+ :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
diff --git a/stundenplan/tests/pygraph/shortestpath_tests.py b/stundenplan/tests/pygraph/shortestpath_tests.py
new file mode 100644
index 0000000..6b9b2de
--- /dev/null
+++ b/stundenplan/tests/pygraph/shortestpath_tests.py
@@ -0,0 +1,26 @@
+import unittest
+
+from pygraph.graphdemo import Graph
+from pygraph.shortestpath import bfs
+
+
+class ShortestPathTestCase(unittest.TestCase):
+ def test_bfs(self):
+ g = Graph()
+ g.add_edges(0, [1, 2])
+ g.add_edges(1, [0, 3, 4])
+ g.add_edges(2, [0, 4, 6, 7])
+ g.add_edges(3, [1])
+ g.add_edges(4, [1, 2, 5])
+ g.add_edges(5, [4])
+ g.add_edges(6, [2])
+ g.add_edges(7, [2])
+ #print(g)
+ # self.assertEqual(True, False) # add assertion here
+
+ tree = bfs(g, 0)
+ print(tree)
+
+
+if __name__ == '__main__':
+ unittest.main()
--
Gitblit v1.10.0-SNAPSHOT