ImplementationoftheAlgorithms
                inPython                                                                                         A
                A.1 Introduction
                This appendix assumes a basic knowledge of programming using the Python pro-
                gramminglanguage,includingconceptssuchasmutableandimmutableobjects,and
                local, global, and nonlocal declarations. See, for example, [3–6, 10] for an introduc-
                tion to programming in Python, [9] for an introduction to the Python programming
                language, [1, 8] for more advanced aspects of the Python programming language,
                and [7] for the implementation of data structures and algorithms in Python.
                   ThefollowingdeclarationisneededforthefunctionannotationsusedinthePython
                code throughout this appendix.
                 Typehints
                   from typing import Iterator, Dict, List, Set, Tuple
                A.1.1     BasicDataStructures
                 Representation of stacks
                   class Stack:
                         def __init__(self) -> None:
                               self.data = list()
                         def empty(self) -> bool:
                               return self.size() == 0
                ©TheEditor(s) (if applicable) and The Author(s), under exclusive license                   287
                to Springer Nature Switzerland AG 2021
                G. Valiente, Algorithms on Trees and Graphs, Texts in Computer Science,
                https://doi.org/10.1007/978-3-030-81885-2
       288                 A:ImplementationoftheAlgorithmsinPython
           def size(self) -> int:
             return len(self.data)
           def top(self):
             if self.empty():
                return None
             else:
                return self.data[-1]
           def push(self, x) -> None:
             self.data.append(x)
           def pop(self):
             return self.data.pop()
       Representation of queues
        from collections import deque
        class Queue:
           def __init__(self) -> None:
             self.data = deque()
           def empty(self) -> bool:
             return self.size() == 0
           def size(self) -> int:
             return len(self.data)
           def front(self):
             if self.empty():
                return None
             else:
                return self.data[0]
           def enqueue(self, x) -> None:
             self.data.append(x)
           def dequeue(self):
             return self.data.popleft()
             A:ImplementationoftheAlgorithmsinPython                                      289
              Representation of priority queues
                import heapq
                class PriorityQueue:
                     def __init__(self) -> None:
                          self.data = list()
                     def empty(self) -> bool:
                          return self.size() == 0
                     def size(self) -> int:
                          return len(self.data)
                     def front(self):
                          if self.empty():
                               return None
                          else:
                               return self.data[0]
                     def enqueue(self, x) -> None:
                          heapq.heappush(self.data, x)
                     def dequeue(self):
                          return heapq.heappop(self.data)
             A.1.2    RepresentationofTreesandGraphs
             The following class implements the adjacency map representation of a graph, us-
             ing Python lists, dictionaries, and iterators over the lists of vertices, edges, in-
             coming edges, and outgoing edges, borrowing ideas from [12]. Let G = (V, E)
             be a graph with n vertices and m edges. Operations G.vertices(), G.incoming(),
             G.outgoing(), G.adjacent(v,w), G.source(e), G.target(e), and G.opposite(v,e)
             take O(1) time. Operations G.first_vertex(), G.first_edge(), G.first_in_edge(v),
             G.first_adj_edge(v), G.new_vertex(), G.new_edge(v,w), and G.del_edge(e) al-
             so take O(1) time. Operations G.indeg(v), G.last_in_edge(v), G.in_pred(e), and
             G.in_succ(e) take O(indeg(v)) time, where e = (v,w). Operations G.outdeg(v),
             G.last_adj_edge(v), G.adj_pred(e), and G.adj_succ(e) take O(outdeg(v)) time,
             where e = (v,w). Operation G.del_vertex(v), takes O(deg(v)) time. Operations
             G.number_of_vertices(),G.last_vertex(),G.pred_vertex(v),andG.succ_vertex(v)
             takeO(n)time.Finally,operationsG.edges(),G.number_of_edges(),G.last_edge(),
             G.pred_edge(e), and G.succ_edge(e) take O(m) time. These are all expected time
             bounds.
       290                 A:ImplementationoftheAlgorithmsinPython
       Representation of graphs
        class Graph:
           class Vertex:
             def __init__(self, label) -> None:
                self._label = label
             def label(self):
                return self._label
             def __str__(self) -> str:
                return str(self._label)
             def __hash__(self) -> int:
                return hash(id(self))
             def __lt__(self, other) -> bool:
                return hash(self) < hash(other)
           class Edge:
             def __init__(
                  self,
                  source: ’Vertex’,
                  target: ’Vertex’,
                  label) -> None:
                self._source = source
                self._target = target
                self._label = label
             def source(self) -> ’Vertex’:
                return self._source
             def target(self) -> ’Vertex’:
                return self._target
             def label(self):
                return self._label
             def __str__(self) -> str:
                return str(self._label)
             def __hash__(self) -> int:
                return hash(
                  (id(self._source), id(self._target)))
             def opposite(self, v) -> ’Vertex’:
                if v is self._source: