dsa.graph

  1""" Module containing graph classes. """
  2
  3from dsa.queue import Queue
  4
  5class AdjacencyMatrixGraph:
  6    """ 
  7    An unweighted adjacency matrix graph implementation.
  8    
  9    This class allows either directed or undirected representation of a graph.
 10    Vertex labels are string types.
 11    """
 12    def __init__(self, labels: list[str]):
 13        """ 
 14        Initialize the graph with a list of vertex labels.
 15
 16        Args:
 17            labels (list[str]): List of labels for each vertex.
 18        """
 19        self.labels = labels
 20        self.label_index = { label: index for index, label  in enumerate(labels) }
 21
 22        node_count = len(self.labels)
 23        self.array = [[None for i in range(node_count)] for j in range(node_count)]
 24
 25    def add_edge(self, start_label: str, end_label: str, directed=False):
 26        """ 
 27        Add an edge in the graph.
 28        
 29        Args:
 30            start_label (str): Starting vertex label.
 31            end_label (str): Ending vertex label.
 32            directed (bool): Whether the edge is directed.
 33        """
 34        a = self.label_index[start_label]
 35        b = self.label_index[end_label]
 36        self.array[a][b] = True
 37        if not directed:
 38            self.array[b][a] = True
 39
 40    def add_vertex(self, label: str):
 41        """ 
 42        Add a vertex to the graph.
 43        
 44        Args:
 45            label (str): The vertex label to add.
 46        """
 47        self.labels.append(label)
 48        self.label_index[label] = len(self.labels) - 1
 49        for row in self.array:
 50            row.append(None)
 51        self.array.append([None for i in range(len(self.labels))])
 52
 53    def delete_vertex(self, label: str):
 54        """ 
 55        Delete a vertex from the graph.
 56        
 57        Args:
 58            label (str): The vertex label to delete.
 59        """
 60        index = self.label_index[label]
 61        self.labels.pop(index)
 62        self.label_index = { label: index for index, label in enumerate(self.labels) }
 63        self.array.pop(index)
 64        for row in self.array:
 65            row.pop(index)
 66
 67    def delete_edge(self, start_label: str, end_label: str, directed=False):
 68        """ 
 69        Delete an edge in the graph.
 70        
 71        Args:
 72            start_label (str): Starting vertex label.
 73            end_label (str): Ending vertex label.
 74            directed (bool): Whether the edge is directed.
 75        """
 76        a = self.label_index[start_label]
 77        b = self.label_index[end_label]
 78        if self.array[a][b] is None:
 79            raise KeyError(f"Edge {start_label} to {end_label} does not exist")
 80
 81        self.array[a][b] = None
 82        if not directed:
 83            if self.array[b][a] is None:
 84                raise KeyError(f"Edge {end_label} to {start_label} does not exist")
 85            self.array[b][a] = None
 86
 87    def dfs_traverse(self, start_label: str):
 88        """ 
 89        Perform depth first traversal in an adjacency matrix
 90 
 91        Args:
 92            start_label (str): Starting vertex label.
 93        
 94        Returns:
 95            Array with depth first order traversal.
 96        """
 97        return self._df_rec_traverse(start_label, set(), [])
 98        
 99    def _df_rec_traverse(self, start_label: str, visited, dfs):
100        """ 
101        Helper method for depth first recursive traversal
102        """
103        start_index = self.label_index[start_label]
104        visited.add(start_label)
105        dfs.append(self.labels[start_index])
106
107        for adj_index, is_connected in enumerate(self.array[start_index]):
108            adj_label = self.labels[adj_index]
109            if is_connected and adj_label not in visited:
110                self._df_rec_traverse(adj_label, visited, dfs)
111
112        return dfs
113
114    def bfs_traverse(self, start_label: str):
115        """ 
116        Perform breadth first traversal in an adjacency matrix.
117 
118        Args:
119            start_label (str): Starting vertex label.
120        
121        Returns:
122            Array with breadth first order traversal.
123        """
124        bfs = []
125        q = Queue()
126        visited = set()
127
128        start_index = self.label_index[start_label]
129        q.enqueue(start_index)
130        bfs.append(self.labels[start_index])
131        while not q.is_empty():
132            current = q.dequeue()
133            for i in range(len(self.array)):
134                if start_index != i and self.array[current][i] and (i not in visited):
135                    visited.add(i)
136                    q.enqueue(i)
137                    bfs.append(self.labels[i])
138        return bfs
139    
140    def vertices(self) -> list:
141        """
142        Return a list of vertex labels of the graph
143        """
144        return self.labels
145    
146    def edges(self) -> list:
147        """ 
148        Return a list of edges in the graph. Each edge is represented by a tuple (start, end)
149        """
150        edges = []
151        vertex_count = len(self.labels)
152        for i in range(vertex_count):
153            for j in range(vertex_count):
154                if self.array[i][j] and i != j:  
155                    edges.append((self.labels[i], self.labels[j]))
156    
157        return edges
158
159    def undirected_edges(self) -> list:
160        """ 
161        Return a list of undirected edges in the graph. Each edge is represented by a tuple (start, end)
162        """
163        edges = []
164        vertex_count = len(self.labels)
165        for i in range(vertex_count):
166            for j in range(vertex_count):
167                if self.array[i][j] and i != j and (self.labels[j], self.labels[i]) not in edges:  
168                    edges.append((self.labels[i], self.labels[j]))
169    
170        return edges
171
172    def is_edge(self, start_label: str, end_label: str) -> bool:
173        """ 
174        Return boolean if an edge exists.
175
176        Args:
177            start_label (str): starting vertex label
178            end_label (str): starting vertex label
179        
180        Returns:0
181            A boolean of whether there is an edge from start to end.
182        """
183        start_index = self.label_index[start_label]
184        end_index = self.label_index[end_label]
185
186        return self.array[start_index][end_index] is not None
187
188    def __getitem__(self, vertex: str) -> list:
189        """ 
190        Args:
191            vertex (str): The vertex label.
192        Returns:
193            A list of adjacent vertex labels.
194        """
195        index = self.label_index[vertex]
196        return [self.labels[i] for i in range(len(self.array[index])) if self.array[index][i]]
197    
198    def print_graph(self):
199        """ 
200        Print the contents of the graph.
201        """
202        print("   |", end="")
203        for label in self.labels:
204            print(f"{label:^3}", end=" ")
205        print()
206        print("----" * (len(self.array) + 1))
207        for r, row in enumerate(self.array):
208            label = self.labels[r]
209            print(f"{label:^3}|", end="")
210            for col in row:
211                b = " T " if col else "   "
212                print(b, end=" ")
213            print()
214            
215class AdjacencyMatrixWeightedGraph(AdjacencyMatrixGraph):
216    """ 
217    A weighted adjacency matrix graph implementation
218    (allows either directed or undirected representation)
219    vertex labels are string types
220    """
221    def __init__(self, labels):
222        """ 
223        Args:
224            labels: list of labels for each vertex (string types)
225        """
226        super().__init__(labels)
227
228    def add_edge(self, start_label: str, end_label: str, weight, directed=False):
229        """ 
230        Add an edge to the graph.
231
232        Args:
233            start_label (str): The starting vertex label.
234            end_label (str): The ending vertex label.
235            weight: The weight of the vertex.
236            directed: Whether the edge is directed.
237        """
238        a = self.label_index[start_label]
239        b = self.label_index[end_label]
240
241        self.array[a][b] = weight
242        self.array[a][a] = 0
243        self.array[b][b] = 0
244
245        if not directed:
246            self.array[b][a] = weight
247        
248    def print_graph(self):
249        """ 
250        Print the contents of the graph.
251        """
252        print("   |", end="")
253        for label in self.labels:
254            print(f"{label:>3}", end=" ")
255        print()
256        print("----" * (len(self.array) + 1))
257        for r, row in enumerate(self.array):
258            label = self.labels[r]
259            print(f"{label:^3}|", end="")
260            for col in row:
261                w = f"{col:3}" if col is not None else "   "
262                print(w, end=" ")
263            print()
264
265    def edges(self) -> list:
266        """ 
267        Return a list of edges in the graph. Each edge is represented by a tuple (start, end, weight).
268        """
269        edges = []
270        vertex_count = len(self.labels)
271        for i in range(vertex_count):
272            for j in range(vertex_count):
273                weight = self.array[i][j]
274                if weight and i != j:  
275                    edges.append((self.labels[i], self.labels[j], weight))
276    
277        return edges
278    
279    def undirected_edges(self) -> list:
280        """ 
281        Return a list of undirected edges in the graph. Each edge is represented by a tuple (start, end, weight).
282        """
283        edges = []
284        vertex_count = len(self.labels)
285        for i in range(vertex_count):
286            for j in range(vertex_count):
287                weight = self.array[i][j]
288                if weight and i != j and (self.labels[j], self.labels[i], weight) not in edges:  
289                    edges.append((self.labels[i], self.labels[j], weight))
290    
291        return edges
292
293    def is_edge(self, start_label: str, end_label: str) -> bool:
294        """ 
295        Return boolean if an edge exists.
296
297        
298        Args:
299            start_label (str): Starting vertex label.
300            end_label (str): Ending vertex label.
301        
302        Returns:
303            A boolean of whether there is an edge from start to end.
304        """
305        return super().is_edge(start_label, end_label)
306    
307    def weightx(self, start: str, end: str) -> bool:
308        """ 
309        Return weight of an edge (is this used???)
310        Args:
311            start_label: starting vertex label
312            end_label: starting vertex label
313        
314        Returns:
315            weight value of an edge from start to end
316        """
317        return super().is_edge(start, end)
318
319    def __getitem__(self, vertex: str) -> dict:
320        """ 
321        Args:
322            vertex: vertex label
323        Returns:
324            a dictionary of adjacent vertex labels and weights
325        """
326        index = self.label_index[vertex]
327        return {self.labels[i] : self.array[index][i] for i in range(len(self.array[index])) if self.array[index][i]}
328
329class AdjacencyListGraph:
330    """ 
331    A unweighted adjacency list vertex implementation
332    (allows either directed or undirected representation)
333    vertex labels are string types
334    """
335    def __init__(self):
336        #: hash table of vertices in graph
337        self._adjacents = {}
338        
339    def add_edge(self, start_label: str, end_label: str, directed=False):
340        """ 
341        Add an edge to the graph.
342
343        Args:
344            start_label (str): The label of the starting vertex.
345            end_label (str): The label of the ending vertex.
346            directed (bool): Whether the edge is directed.
347        """
348        self.add_directed_edge(start_label, end_label)
349        if not directed:
350            self.add_directed_edge(end_label, start_label)
351                
352    def add_directed_edge(self, start_label: str, end_label: str):
353        """ 
354        Add a directed edge to the graph.
355
356        Args:
357            start_label (str): The label of the starting vertex.
358            end_label (str): The label of the ending vertex.
359        """
360        if start_label not in self._adjacents:
361            self._adjacents[start_label] = [end_label]
362        else:
363            if end_label not in self._adjacents[start_label]:
364                self._adjacents[start_label].append(end_label)
365        if end_label not in self._adjacents:
366            self._adjacents[end_label] = []
367
368    def delete_edge(self, start_label: str, end_label: str, directed=False):
369        """ 
370        Delete an edge in the graph.
371        
372        Args:
373            start_label (str): Starting vertex label.
374            end_label (str): Ending vertex label.
375            directed (bool): Whether the edge is directed.
376        Raises:
377            KeyError: If the edge does exist.
378        """
379        if start_label not in self._adjacents:
380            raise KeyError(f"Vertex {start_label} does not exist")
381        if end_label not in self._adjacents[start_label]:
382            raise KeyError(f"Vertex {end_label} does not exist")
383        self._adjacents[start_label].remove(end_label)
384        if not directed:
385            if end_label not in self._adjacents:
386                raise KeyError(f"Vertex {end_label} does not exist")
387            if start_label not in self._adjacents[end_label]:
388                raise KeyError(f"Vertex {start_label} does not exist")
389            self._adjacents[end_label].remove(start_label)
390
391    def vertices(self) -> list:
392        """
393        Return a list of vertex labels of the graph
394        """
395        return list(self._adjacents.keys())
396  
397    def adjacents(self, vertex: str) -> list:
398        """
399        Return a list of adjacents of a given vertex
400
401        Args:
402            vertex (str): The label of the vertex.
403        """
404        return self._adjacents[vertex]
405
406    def dfs_traverse(self, start_label: str):
407        """
408        Return a list of vertices through depth first traversal starting at a given vertex.
409
410        Args:
411            start_label (str): The starting vertex label.
412        Returns:
413            A list of vertex labels.
414        """
415        return self._df_rec_traverse(start_label, set(), [])
416
417    def _df_rec_traverse(self, start_label: str, visited, dflist):
418        """
419        Helper depth first traversal recursive function.
420        """
421        visited.add(start_label)
422        dflist.append(start_label)
423        
424        for v in self[start_label]:
425            if v not in visited:
426                self._df_rec_traverse(v, visited, dflist)
427        return dflist
428    
429    def bfs_traverse(self, start_label: str):
430        """
431        Return a list of vertices through breadth first traversal starting at a given vertex
432        Args:
433            start_label (str): The starting vertex label.
434        Returns:
435            A list of vertex labels.
436        """
437        visited = set()
438        q = Queue()
439        bflist = []
440
441        q.enqueue(start_label)
442        visited.add(start_label)
443        bflist.append(start_label)
444
445        while len(q) > 0:
446            current = q.dequeue()
447
448            for v in self[current]:
449                if v not in visited:               
450                    visited.add(v)
451                    q.enqueue(v)
452                    bflist.append(v)
453        return bflist
454        
455    def dfs(self, start_label:str, end_label:str) -> str:
456        """ 
457        Recursive depth first search.
458
459        Args:
460            start_label (str): The starting vertex label.
461            end_label (str): The vertex label to search for.
462
463        Returns:
464            A vertex in the graph if found, None otherwise.
465        """
466        def dfs_rec(current: str, end: str, visited):
467            if current == end:
468                return current
469
470            visited.add(current)
471
472            for v in self.adjacents(current):
473                if v not in visited:
474                    result = dfs_rec(v, end, visited)
475                    if result is not None:
476                        return result
477            
478            return None
479        
480        return dfs_rec(start_label, end_label, set())
481    
482    def bfs(self, start_label: str, end_label: str) -> str:
483        """ 
484        Breadth first search.
485
486        Args:
487            start_label (str): The starting vertex label.
488            end_label (str): The vertex label to search for.
489
490        Returns:
491            A vertex in the graph if found, None otherwise.
492        """
493        visited = set()
494        queue = Queue()
495        
496        visited.add(start_label)
497        queue.enqueue(start_label)
498
499        while len(queue) > 0:
500            current = queue.dequeue()
501            
502            if current == end_label:
503                return current
504            
505            for v in self[current]:
506                if v not in visited:               
507                    visited.add(v)
508                    queue.enqueue(v)
509        
510        return None
511    
512    def __getitem__(self, label: str):
513        """ 
514        Args:
515            vertex: vertex label
516        Returns:
517            a list of adjacent vertex labels
518        """
519
520        return self._adjacents[label]
521
522    def is_edge(self, start_label: str, end_label: str) -> bool:
523        """ 
524        Return boolean if an edge exists
525        Args:
526            start_label (str): The starting vertex label.
527            end_label (str): The ending vertex label.
528        
529        Returns:
530            A boolean of whether there is an edge from start to end
531        """
532        return end_label in self[start_label]
533
534    def __len__(self):
535        """
536        Return the number of nodes in the graph.
537        Returns:
538            int: The number of nodes in the graph.
539        """
540        return len(self._adjacents)
541
542    def edges(self) -> list:
543        """ 
544        Return a list of edges in the graph. Each edge is represented by a tuple (start, end)
545        """
546        edges = []
547        for start in self._adjacents.keys():
548            for end in self.adjacents(start):
549                if start != end:  
550                    edges.append((start, end))
551        return edges
552
553    def undirected_edges(self) -> list:
554        """ 
555        Return a list of undirected edges in the graph. Each edge is represented by a tuple (start, end)
556        """
557        edges = []
558        for start in self._adjacents.keys():
559            for end in self.adjacents(start):
560                if start != end and (end, start) not in edges:  
561                    edges.append((start, end))
562        return edges
563
564class AdjacencyListWeightedGraph(AdjacencyListGraph):
565    """ 
566    A weighted adjacency list vertex implementation in Python
567    (allows either directed or undirected representation)
568    """
569    def __init__(self):
570        #: hash table of vertices in graph
571        self._adjacents = {}
572        
573    def add_edge(self, start_label: str, end_label: str, weight, directed=False):
574        """ 
575        Add an edge to the graph.
576
577        Args:
578            start_label: The starting vertex label. 
579            end_label: The ending vertex label. 
580            weight: The edge weight.
581            directed: Whether the edge is directed.
582        """
583        if start_label not in self._adjacents:
584            self._adjacents[start_label] = {}
585            
586        self._adjacents[start_label][end_label] = weight
587
588        if not directed:
589            if end_label not in self._adjacents:
590                self._adjacents[end_label] = {}
591            self._adjacents[end_label][start_label] = weight
592
593    def delete_edge(self, start_label: str, end_label: str, directed=False):
594        """ 
595        Delete an edge in the graph.
596        
597        Args:
598            start_label (str): Starting vertex label.
599            end_label (str): Ending vertex label.
600            directed (bool): Whether the edge is directed.
601
602        Raises:
603            KeyError: If the edge does exist.
604        """
605        if start_label not in self._adjacents:
606            raise KeyError(f"Vertex {start_label} does not exist")
607        if end_label not in self._adjacents[start_label]:
608            raise KeyError(f"Vertex {end_label} does not exist") 
609        del self._adjacents[start_label][end_label]
610        if not directed:
611            if end_label not in self._adjacents:
612                raise KeyError(f"Vertex {end_label} does not exist")
613            if start_label not in self._adjacents[end_label]:
614                raise KeyError(f"Vertex {start_label} does not exist") 
615            del self._adjacents[end_label][start_label]
616
617    def adjacents(self, vertex: str) -> list:
618        """
619        Return a list of adjacents of a given vertex
620        Args:
621            vertex: starting vertex label 
622        """
623        return self._adjacents[vertex]
624
625    def dfs_traverse(self):
626        """
627        Perform depth first traversal.
628        """
629        return self._df_traverse_rec(self, set())
630
631    def _df_traverse_rec(self, vertex, visited=None):
632        """
633        helper depth first traversal recursive function
634        """
635        visited.add(vertex)
636        
637        for v in vertex.adjacents:
638            if v not in visited:
639                v._df_traverse_rec(v, visited)
640            
641    def bfs_traverse(self):
642        """
643        Perform breadth first traversal.
644        """
645        start = self
646        visited = set()
647        queue = Queue()
648        
649        queue.enqueue(start)
650
651        while len(queue) > 0:
652            current = queue.dequeue()
653            
654            if current not in visited:               
655                visited.add(current)
656        
657                for v in current.adjacents:
658                    queue.enqueue(v)
659        
660    def dfs(self, start_label: str, end_label: str) -> str:
661        """ 
662        Recursive depth first search.
663
664        Args:
665            start_label: The starting vertex label. 
666            end_label: The vertex label to search for. 
667        Returns:
668            vertex in the graph
669            none if not found.
670        """
671        return self.dfs_rec(start_label, end_label, set())
672        
673    def dfs_rec(self, current, end_label, visited=None):
674        """
675        Helper depth-first search recursive function.
676
677        Args:
678            current: Current vertex
679            end_label: Target vertex label
680            visited: Set of visited vertices 
681
682        Returns:
683            vertex in the graph if found, None otherwise.
684        """
685        if visited is None:
686            visited = set()
687        
688        if current == end_label:
689            return current
690
691        visited.add(current)
692        
693        for v in self.adjacents(current):
694            if v not in visited:
695                result = self.dfs_rec(v, end_label, visited)
696                if result is not None:
697                    return result
698        
699        return None
700
701
702    def bfs(self, start_label: str, end_label: str) -> str:
703        """ 
704        Recursive breadth first search.
705
706        Args:
707            end: vertex to search for
708
709        Returns:
710            vertex in the graph
711            None if not found.
712        """
713        visited = set()
714        queue = Queue()
715        
716        visited.add(start_label)
717        queue.enqueue(start_label)
718
719        while not queue.is_empty():
720            current = queue.dequeue()
721            
722            if current == end_label:
723                return current
724            
725            for v in self[current]:
726                if v not in visited:
727                    visited.add(v)
728                    queue.enqueue(v)
729        
730        return None
731
732    def __getitem__(self, vertex: str) -> dict:
733        """
734        Args:
735            vertex: vertex label
736        Returns:
737        Return a hashtable of adjacent vertices
738        """
739        if vertex not in self._adjacents:
740            return {}
741        return self._adjacents[vertex]
742
743    def __len__(self):
744        """
745        Return the number of nodes in the graph.
746
747        Returns:
748            int: The number of nodes in the graph.
749        """
750        return len(self._adjacents)
751
752    def edges(self) -> list:
753        """ 
754        Return a list of edges in the graph. Each edge is represented by a tuple (start, end, weight)
755        """
756        edges = []
757        for start in self._adjacents.keys():
758            for end in self.adjacents(start):
759                weight = self[start][end]
760                if start != end:  
761                    edges.append((start, end, weight))
762        return edges
763
764    def undirected_edges(self) -> list:
765        """ 
766        Return a list of undirected edges in the graph. Each edge is represented by a tuple (start, end, weight)
767        """
768        edges = []
769        for start in self._adjacents.keys():
770            for end in self.adjacents(start):
771                weight = self[start][end]
772                if start != end and (end, start, weight) not in edges:  
773                    edges.append((start, end, weight))
774        return edges
775
776    def is_edge(self, start_label: str, end_label: str) -> bool:
777        """ 
778        Return boolean if an edge exists
779        Args:
780            start_label (str): starting vertex label
781            end_label (str): starting vertex label
782        
783        Returns:
784            A boolean of whether there is an edge from start to end.
785        """
786        return end_label in self[start_label]
787
788
789
790__pdoc__ = {
791    'AdjacencyMatrixGraph.add_vertex': False,
792    'AdjacencyMatrixGraph.delete_vertex': False,
793    'AdjacencyListGraph.add_directed_edge': False,
794}