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 __contains__(self, label: str) -> bool:
199        """ 
200        Args:
201            label (str): The vertex label.
202        Returns:
203            A boolean indicating if the vertex is in the graph.
204        """
205        return label in self.label_index
206    
207    def print_graph(self):
208        """ 
209        Print the contents of the graph.
210        """
211        print("   |", end="")
212        for label in self.labels:
213            print(f"{label:^3}", end=" ")
214        print()
215        print("----" * (len(self.array) + 1))
216        for r, row in enumerate(self.array):
217            label = self.labels[r]
218            print(f"{label:^3}|", end="")
219            for col in row:
220                b = " T " if col else "   "
221                print(b, end=" ")
222            print()
223            
224class AdjacencyMatrixWeightedGraph(AdjacencyMatrixGraph):
225    """ 
226    A weighted adjacency matrix graph implementation
227    (allows either directed or undirected representation)
228    vertex labels are string types
229    """
230    def __init__(self, labels):
231        """ 
232        Args:
233            labels: list of labels for each vertex (string types)
234        """
235        super().__init__(labels)
236
237    def add_edge(self, start_label: str, end_label: str, weight, directed=False):
238        """ 
239        Add an edge to the graph.
240
241        Args:
242            start_label (str): The starting vertex label.
243            end_label (str): The ending vertex label.
244            weight: The weight of the vertex.
245            directed: Whether the edge is directed.
246        """
247        a = self.label_index[start_label]
248        b = self.label_index[end_label]
249
250        self.array[a][b] = weight
251        self.array[a][a] = 0
252        self.array[b][b] = 0
253
254        if not directed:
255            self.array[b][a] = weight
256        
257    def print_graph(self):
258        """ 
259        Print the contents of the graph.
260        """
261        print("   |", end="")
262        for label in self.labels:
263            print(f"{label:>3}", end=" ")
264        print()
265        print("----" * (len(self.array) + 1))
266        for r, row in enumerate(self.array):
267            label = self.labels[r]
268            print(f"{label:^3}|", end="")
269            for col in row:
270                w = f"{col:3}" if col is not None else "   "
271                print(w, end=" ")
272            print()
273
274    def edges(self) -> list:
275        """ 
276        Return a list of edges in the graph. Each edge is represented by a tuple (start, end, weight).
277        """
278        edges = []
279        vertex_count = len(self.labels)
280        for i in range(vertex_count):
281            for j in range(vertex_count):
282                weight = self.array[i][j]
283                if weight and i != j:  
284                    edges.append((self.labels[i], self.labels[j], weight))
285    
286        return edges
287    
288    def undirected_edges(self) -> list:
289        """ 
290        Return a list of undirected edges in the graph. Each edge is represented by a tuple (start, end, weight).
291        """
292        edges = []
293        vertex_count = len(self.labels)
294        for i in range(vertex_count):
295            for j in range(vertex_count):
296                weight = self.array[i][j]
297                if weight and i != j and (self.labels[j], self.labels[i], weight) not in edges:  
298                    edges.append((self.labels[i], self.labels[j], weight))
299    
300        return edges
301
302    def is_edge(self, start_label: str, end_label: str) -> bool:
303        """ 
304        Return boolean if an edge exists.
305
306        
307        Args:
308            start_label (str): Starting vertex label.
309            end_label (str): Ending vertex label.
310        
311        Returns:
312            A boolean of whether there is an edge from start to end.
313        """
314        return super().is_edge(start_label, end_label)
315    
316    def weightx(self, start: str, end: str) -> bool:
317        """ 
318        Return weight of an edge (is this used???)
319        Args:
320            start_label: starting vertex label
321            end_label: starting vertex label
322        
323        Returns:
324            weight value of an edge from start to end
325        """
326        return super().is_edge(start, end)
327
328    def __getitem__(self, vertex: str) -> dict:
329        """ 
330        Args:
331            vertex: vertex label
332        Returns:
333            a dictionary of adjacent vertex labels and weights
334        """
335        index = self.label_index[vertex]
336        return {self.labels[i] : self.array[index][i] for i in range(len(self.array[index])) if self.array[index][i]}
337
338class AdjacencyListGraph:
339    """ 
340    A unweighted adjacency list vertex implementation
341    (allows either directed or undirected representation)
342    vertex labels are string types
343    """
344    def __init__(self):
345        #: hash table of vertices in graph
346        self._adjacents = {}
347        
348    def add_edge(self, start_label: str, end_label: str, directed=False):
349        """ 
350        Add an edge to the graph.
351
352        Args:
353            start_label (str): The label of the starting vertex.
354            end_label (str): The label of the ending vertex.
355            directed (bool): Whether the edge is directed.
356        """
357        self.add_directed_edge(start_label, end_label)
358        if not directed:
359            self.add_directed_edge(end_label, start_label)
360                
361    def add_directed_edge(self, start_label: str, end_label: str):
362        """ 
363        Add a directed edge to the graph.
364
365        Args:
366            start_label (str): The label of the starting vertex.
367            end_label (str): The label of the ending vertex.
368        """
369        if start_label not in self._adjacents:
370            self._adjacents[start_label] = [end_label]
371        else:
372            if end_label not in self._adjacents[start_label]:
373                self._adjacents[start_label].append(end_label)
374        if end_label not in self._adjacents:
375            self._adjacents[end_label] = []
376
377    def delete_edge(self, start_label: str, end_label: str, directed=False):
378        """ 
379        Delete an edge in the graph.
380        
381        Args:
382            start_label (str): Starting vertex label.
383            end_label (str): Ending vertex label.
384            directed (bool): Whether the edge is directed.
385        Raises:
386            KeyError: If the edge does exist.
387        """
388        if start_label not in self._adjacents:
389            raise KeyError(f"Vertex {start_label} does not exist")
390        if end_label not in self._adjacents[start_label]:
391            raise KeyError(f"Vertex {end_label} does not exist")
392        self._adjacents[start_label].remove(end_label)
393        if not directed:
394            if end_label not in self._adjacents:
395                raise KeyError(f"Vertex {end_label} does not exist")
396            if start_label not in self._adjacents[end_label]:
397                raise KeyError(f"Vertex {start_label} does not exist")
398            self._adjacents[end_label].remove(start_label)
399
400    def vertices(self) -> list:
401        """
402        Return a list of vertex labels of the graph
403        """
404        return list(self._adjacents.keys())
405  
406    def adjacents(self, vertex: str) -> list:
407        """
408        Return a list of adjacents of a given vertex
409
410        Args:
411            vertex (str): The label of the vertex.
412        """
413        return self._adjacents[vertex]
414
415    def dfs_traverse(self, start_label: str):
416        """
417        Return a list of vertices through depth first traversal starting at a given vertex.
418
419        Args:
420            start_label (str): The starting vertex label.
421        Returns:
422            A list of vertex labels.
423        """
424        return self._df_rec_traverse(start_label, set(), [])
425
426    def _df_rec_traverse(self, start_label: str, visited, dflist):
427        """
428        Helper depth first traversal recursive function.
429        """
430        visited.add(start_label)
431        dflist.append(start_label)
432        
433        for v in self[start_label]:
434            if v not in visited:
435                self._df_rec_traverse(v, visited, dflist)
436        return dflist
437    
438    def bfs_traverse(self, start_label: str):
439        """
440        Return a list of vertices through breadth first traversal starting at a given vertex
441        Args:
442            start_label (str): The starting vertex label.
443        Returns:
444            A list of vertex labels.
445        """
446        visited = set()
447        q = Queue()
448        bflist = []
449
450        q.enqueue(start_label)
451        visited.add(start_label)
452        bflist.append(start_label)
453
454        while len(q) > 0:
455            current = q.dequeue()
456
457            for v in self[current]:
458                if v not in visited:               
459                    visited.add(v)
460                    q.enqueue(v)
461                    bflist.append(v)
462        return bflist
463        
464    def dfs(self, start_label:str, end_label:str) -> str:
465        """ 
466        Recursive depth first search.
467
468        Args:
469            start_label (str): The starting vertex label.
470            end_label (str): The vertex label to search for.
471
472        Returns:
473            A vertex in the graph if found, None otherwise.
474        """
475        def dfs_rec(current: str, end: str, visited):
476            if current == end:
477                return current
478
479            visited.add(current)
480
481            for v in self.adjacents(current):
482                if v not in visited:
483                    result = dfs_rec(v, end, visited)
484                    if result is not None:
485                        return result
486            
487            return None
488        
489        return dfs_rec(start_label, end_label, set())
490    
491    def bfs(self, start_label: str, end_label: str) -> str:
492        """ 
493        Breadth first search.
494
495        Args:
496            start_label (str): The starting vertex label.
497            end_label (str): The vertex label to search for.
498
499        Returns:
500            A vertex in the graph if found, None otherwise.
501        """
502        visited = set()
503        queue = Queue()
504        
505        visited.add(start_label)
506        queue.enqueue(start_label)
507
508        while len(queue) > 0:
509            current = queue.dequeue()
510            
511            if current == end_label:
512                return current
513            
514            for v in self[current]:
515                if v not in visited:               
516                    visited.add(v)
517                    queue.enqueue(v)
518        
519        return None
520    
521    def __getitem__(self, label: str):
522        """ 
523        Args:
524            vertex: vertex label
525        Returns:
526            a list of adjacent vertex labels
527        """
528
529        return self._adjacents[label]
530
531    def is_edge(self, start_label: str, end_label: str) -> bool:
532        """ 
533        Return boolean if an edge exists
534        Args:
535            start_label (str): The starting vertex label.
536            end_label (str): The ending vertex label.
537        
538        Returns:
539            A boolean of whether there is an edge from start to end
540        """
541        return end_label in self[start_label]
542
543    def __len__(self):
544        """
545        Return the number of nodes in the graph.
546        Returns:
547            int: The number of nodes in the graph.
548        """
549        return len(self._adjacents)
550
551    def __contains__(self, label: str) -> bool:
552        """ 
553        Args:
554            label (str): The vertex label.
555        Returns:
556            A boolean indicating if the vertex is in the graph.
557        """
558        return label in self._adjacents
559
560    def edges(self) -> list:
561        """ 
562        Return a list of edges in the graph. Each edge is represented by a tuple (start, end)
563        """
564        edges = []
565        for start in self._adjacents.keys():
566            for end in self.adjacents(start):
567                if start != end:  
568                    edges.append((start, end))
569        return edges
570
571    def undirected_edges(self) -> list:
572        """ 
573        Return a list of undirected edges in the graph. Each edge is represented by a tuple (start, end)
574        """
575        edges = []
576        for start in self._adjacents.keys():
577            for end in self.adjacents(start):
578                if start != end and (end, start) not in edges:  
579                    edges.append((start, end))
580        return edges
581
582class AdjacencyListWeightedGraph(AdjacencyListGraph):
583    """ 
584    A weighted adjacency list vertex implementation in Python
585    (allows either directed or undirected representation)
586    """
587    def __init__(self):
588        #: hash table of vertices in graph
589        self._adjacents = {}
590        
591    def add_edge(self, start_label: str, end_label: str, weight, directed=False):
592        """ 
593        Add an edge to the graph.
594
595        Args:
596            start_label: The starting vertex label. 
597            end_label: The ending vertex label. 
598            weight: The edge weight.
599            directed: Whether the edge is directed.
600        """
601        if start_label not in self._adjacents:
602            self._adjacents[start_label] = {}
603            
604        self._adjacents[start_label][end_label] = weight
605
606        if not directed:
607            if end_label not in self._adjacents:
608                self._adjacents[end_label] = {}
609            self._adjacents[end_label][start_label] = weight
610
611    def delete_edge(self, start_label: str, end_label: str, directed=False):
612        """ 
613        Delete an edge in the graph.
614        
615        Args:
616            start_label (str): Starting vertex label.
617            end_label (str): Ending vertex label.
618            directed (bool): Whether the edge is directed.
619
620        Raises:
621            KeyError: If the edge does exist.
622        """
623        if start_label not in self._adjacents:
624            raise KeyError(f"Vertex {start_label} does not exist")
625        if end_label not in self._adjacents[start_label]:
626            raise KeyError(f"Vertex {end_label} does not exist") 
627        del self._adjacents[start_label][end_label]
628        if not directed:
629            if end_label not in self._adjacents:
630                raise KeyError(f"Vertex {end_label} does not exist")
631            if start_label not in self._adjacents[end_label]:
632                raise KeyError(f"Vertex {start_label} does not exist") 
633            del self._adjacents[end_label][start_label]
634
635    def adjacents(self, vertex: str) -> list:
636        """
637        Return a list of adjacents of a given vertex
638        Args:
639            vertex: starting vertex label 
640        """
641        return self._adjacents[vertex]
642
643    def dfs_traverse(self):
644        """
645        Perform depth first traversal.
646        """
647        return self._df_traverse_rec(self, set())
648
649    def _df_traverse_rec(self, vertex, visited=None):
650        """
651        helper depth first traversal recursive function
652        """
653        visited.add(vertex)
654        
655        for v in vertex.adjacents:
656            if v not in visited:
657                v._df_traverse_rec(v, visited)
658            
659    def bfs_traverse(self):
660        """
661        Perform breadth first traversal.
662        """
663        start = self
664        visited = set()
665        queue = Queue()
666        
667        queue.enqueue(start)
668
669        while len(queue) > 0:
670            current = queue.dequeue()
671            
672            if current not in visited:               
673                visited.add(current)
674        
675                for v in current.adjacents:
676                    queue.enqueue(v)
677        
678    def dfs(self, start_label: str, end_label: str) -> str:
679        """ 
680        Recursive depth first search.
681
682        Args:
683            start_label: The starting vertex label. 
684            end_label: The vertex label to search for. 
685        Returns:
686            vertex in the graph
687            none if not found.
688        """
689        return self.dfs_rec(start_label, end_label, set())
690        
691    def dfs_rec(self, current, end_label, visited=None):
692        """
693        Helper depth-first search recursive function.
694
695        Args:
696            current: Current vertex
697            end_label: Target vertex label
698            visited: Set of visited vertices 
699
700        Returns:
701            vertex in the graph if found, None otherwise.
702        """
703        if visited is None:
704            visited = set()
705        
706        if current == end_label:
707            return current
708
709        visited.add(current)
710        
711        for v in self.adjacents(current):
712            if v not in visited:
713                result = self.dfs_rec(v, end_label, visited)
714                if result is not None:
715                    return result
716        
717        return None
718
719
720    def bfs(self, start_label: str, end_label: str) -> str:
721        """ 
722        Recursive breadth first search.
723
724        Args:
725            end: vertex to search for
726
727        Returns:
728            vertex in the graph
729            None if not found.
730        """
731        visited = set()
732        queue = Queue()
733        
734        visited.add(start_label)
735        queue.enqueue(start_label)
736
737        while not queue.is_empty():
738            current = queue.dequeue()
739            
740            if current == end_label:
741                return current
742            
743            for v in self[current]:
744                if v not in visited:
745                    visited.add(v)
746                    queue.enqueue(v)
747        
748        return None
749
750    def __getitem__(self, vertex: str) -> dict:
751        """
752        Args:
753            vertex: vertex label
754        Returns:
755        Return a hashtable of adjacent vertices
756        """
757        if vertex not in self._adjacents:
758            return {}
759        return self._adjacents[vertex]
760
761    def __len__(self):
762        """
763        Return the number of nodes in the graph.
764
765        Returns:
766            int: The number of nodes in the graph.
767        """
768        return len(self._adjacents)
769
770    def edges(self) -> list:
771        """ 
772        Return a list of edges in the graph. Each edge is represented by a tuple (start, end, weight)
773        """
774        edges = []
775        for start in self._adjacents.keys():
776            for end in self.adjacents(start):
777                weight = self[start][end]
778                if start != end:  
779                    edges.append((start, end, weight))
780        return edges
781
782    def undirected_edges(self) -> list:
783        """ 
784        Return a list of undirected edges in the graph. Each edge is represented by a tuple (start, end, weight)
785        """
786        edges = []
787        for start in self._adjacents.keys():
788            for end in self.adjacents(start):
789                weight = self[start][end]
790                if start != end and (end, start, weight) not in edges:  
791                    edges.append((start, end, weight))
792        return edges
793
794    def is_edge(self, start_label: str, end_label: str) -> bool:
795        """ 
796        Return boolean if an edge exists
797        Args:
798            start_label (str): starting vertex label
799            end_label (str): starting vertex label
800        
801        Returns:
802            A boolean of whether there is an edge from start to end.
803        """
804        return end_label in self[start_label]
805
806
807
808__pdoc__ = {
809    'AdjacencyMatrixGraph.add_vertex': False,
810    'AdjacencyMatrixGraph.delete_vertex': False,
811    'AdjacencyListGraph.add_directed_edge': False,
812}