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 --- stundenplan/src/pygraph/graphdemo.py | 30 ++++++++++++++++++++++++------ 1 files changed, 24 insertions(+), 6 deletions(-) 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: -- Gitblit v1.10.0-SNAPSHOT