example about graph

Hong-Phuc Bui

2024-08-25 273021dcef9c23610790e47a109fcbf476b829ec

example about graph

 .gitignore

@@ -1,7 +1,4 @@
sandbox*
queens*
*.venv*
__pycache__/
.idea/
htw-python-kurs-2024-mmb/
*.egg-info/

 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">

 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:

 stundenplan/src/pygraph/shortestpath.py

New file
@@ -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

 stundenplan/tests/pygraph/shortestpath_tests.py

New file
@@ -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()