From cba010a56235c1c55976ca1986bbf982933619c2 Mon Sep 17 00:00:00 2001
From: hbui <hong-phuc.bui@htwsaar.de>
Date: Wed, 17 Jul 2024 11:50:17 +0200
Subject: [PATCH] graph demo
---
stundenplan/tests/__init__.py | 0
stundenplan/src/pygraph/__init__.py | 0
stundenplan/src/pygraph/graphdemo.py | 88 +++++++++++++++++++++++++++++
stundenplan/tests/pygraph/__init__.py | 0
stundenplan/tests/pygraph/graphdemo.tests.py | 40 +++++++++++++
stundenplan/pyproject.toml | 16 +++++
stundenplan/Readme.md | 1
7 files changed, 145 insertions(+), 0 deletions(-)
diff --git a/stundenplan/Readme.md b/stundenplan/Readme.md
new file mode 100644
index 0000000..fa3014b
--- /dev/null
+++ b/stundenplan/Readme.md
@@ -0,0 +1 @@
+Beispielanwendung von Graph
diff --git a/stundenplan/pyproject.toml b/stundenplan/pyproject.toml
new file mode 100644
index 0000000..60a79dd
--- /dev/null
+++ b/stundenplan/pyproject.toml
@@ -0,0 +1,16 @@
+[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
+# ttgeo = "turtlegeo.main:main"
+
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..202e779
--- /dev/null
+++ b/stundenplan/src/pygraph/graphdemo.py
@@ -0,0 +1,88 @@
+class Graph:
+ def __init__(self):
+ self.adjacent: dict[int, set] = {}
+ self.vertex_attribute: dict[int, dict] = {}
+
+ def add_vertex(self, vertex):
+ 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()
+
+ pass
+
+ def add_edge(self, u, v):
+ 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 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):
+ if vertex in self.adjacent:
+ return self.vertex_attribute[vertex]
+ else:
+ raise ValueError(f"Graph does not include vertex {vertex}")
+ pass
+
+ def vertices(self):
+ return self.adjacent.keys()
+
+ def for_each_vertices(self, action):
+ for v in self.vertices():
+ action(v)
+
+ def adjacent_of(self, vertex):
+ if vertex not in self.adjacent:
+ raise ValueError(f"Graph does not include vertex {vertex}")
+ return self.adjacent.get(vertex)
+
+ def for_each_edges(self, action):
+ visited_edges: dict[int, set] = {}
+ for start in 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)
+ if second not in visited_adjacent:
+ visited_adjacent.add(second)
+ action(start, end)
+ else:
+ adjacent = 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
+
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..164c4ac
--- /dev/null
+++ b/stundenplan/tests/pygraph/graphdemo.tests.py
@@ -0,0 +1,40 @@
+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)
+
+
+if __name__ == '__main__':
+ unittest.main()
--
Gitblit v1.10.0-SNAPSHOT