!usrbinenv python3 Author: OMKAR PATHAK, Nwachukwu Chidiebere Use a Python dictionary to construct the graph. Adjacency List type Graph Data Structure that accounts for directed and undirected Graphs.  Initialize graph object indicating whether it's directed or undirected. Directed graph example:  dgraph  GraphAdjacencyList  printdgraph   dgraph.addedge0, 1 0: 1, 1:   dgraph.addedge1, 2.addedge1, 4.addedge1, 5 0: 1, 1: 2, 4, 5, 2: , 4: , 5:   dgraph.addedge2, 0.addedge2, 6.addedge2, 7 0: 1, 1: 2, 4, 5, 2: 0, 6, 7, 4: , 5: , 6: , 7:   dgraph 0: 1, 1: 2, 4, 5, 2: 0, 6, 7, 4: , 5: , 6: , 7:   printreprdgraph 0: 1, 1: 2, 4, 5, 2: 0, 6, 7, 4: , 5: , 6: , 7:  Undirected graph example:  ugraph  GraphAdjacencyListdirectedFalse  ugraph.addedge0, 1 0: 1, 1: 0  ugraph.addedge1, 2.addedge1, 4.addedge1, 5 0: 1, 1: 0, 2, 4, 5, 2: 1, 4: 1, 5: 1  ugraph.addedge2, 0.addedge2, 6.addedge2, 7 0: 1, 2, 1: 0, 2, 4, 5, 2: 1, 0, 6, 7, 4: 1, 5: 1, 6: 2, 7: 2  ugraph.addedge4, 5 0: 1, 2, 1: 0, 2, 4, 5, 2: 1, 0, 6, 7, 4: 1, 5, 5: 1, 4, 6: 2, 7: 2  printugraph 0: 1, 2, 1: 0, 2, 4, 5, 2: 1, 0, 6, 7, 4: 1, 5, 5: 1, 4, 6: 2, 7: 2  printreprugraph 0: 1, 2, 1: 0, 2, 4, 5, 2: 1, 0, 6, 7, 4: 1, 5, 5: 1, 4, 6: 2, 7: 2  chargraph  GraphAdjacencyListdirectedFalse  chargraph.addedge'a', 'b' 'a': 'b', 'b': 'a'  chargraph.addedge'b', 'c'.addedge'b', 'e'.addedge'b', 'f' 'a': 'b', 'b': 'a', 'c', 'e', 'f', 'c': 'b', 'e': 'b', 'f': 'b'  chargraph 'a': 'b', 'b': 'a', 'c', 'e', 'f', 'c': 'b', 'e': 'b', 'f': 'b' Parameters: directed: bool Indicates if graph is directed or undirected. Default is True. Connects vertices together. Creates and Edge from source vertex to destination vertex. Vertices will be created if not found in graph if both source vertex and destination vertex are both present in the adjacency list, add destination vertex to source vertex list of adjacent vertices and add source vertex to destination vertex list of adjacent vertices. if only source vertex is present in adjacency list, add destination vertex to source vertex list of adjacent vertices, then create a new vertex with destination vertex as key and assign a list containing the source vertex as it's first adjacent vertex. if only destination vertex is present in adjacency list, add source vertex to destination vertex list of adjacent vertices, then create a new vertex with source vertex as key and assign a list containing the source vertex as it's first adjacent vertex. if both source vertex and destination vertex are not present in adjacency list, create a new vertex with source vertex as key and assign a list containing the destination vertex as it's first adjacent vertex also create a new vertex with destination vertex as key and assign a list containing the source vertex as it's first adjacent vertex. if both source vertex and destination vertex are present in adjacency list, add destination vertex to source vertex list of adjacent vertices. if only source vertex is present in adjacency list, add destination vertex to source vertex list of adjacent vertices and create a new vertex with destination vertex as key, which has no adjacent vertex if only destination vertex is present in adjacency list, create a new vertex with source vertex as key and assign a list containing destination vertex as first adjacent vertex if both source vertex and destination vertex are not present in adjacency list, create a new vertex with source vertex as key and a list containing destination vertex as it's first adjacent vertex. Then create a new vertex with destination vertex as key, which has no adjacent vertex
#!/usr/bin/env python3

# Author: OMKAR PATHAK, Nwachukwu Chidiebere

# Use a Python dictionary to construct the graph.
from __future__ import annotations

from pprint import pformat
from typing import Generic, TypeVar

T = TypeVar("T")


class GraphAdjacencyList(Generic[T]):
    """
    Adjacency List type Graph Data Structure that accounts for directed and undirected
    Graphs.  Initialize graph object indicating whether it's directed or undirected.

    Directed graph example:
    >>> d_graph = GraphAdjacencyList()
    >>> print(d_graph)
    {}
    >>> d_graph.add_edge(0, 1)
    {0: [1], 1: []}
    >>> d_graph.add_edge(1, 2).add_edge(1, 4).add_edge(1, 5)
    {0: [1], 1: [2, 4, 5], 2: [], 4: [], 5: []}
    >>> d_graph.add_edge(2, 0).add_edge(2, 6).add_edge(2, 7)
    {0: [1], 1: [2, 4, 5], 2: [0, 6, 7], 4: [], 5: [], 6: [], 7: []}
    >>> d_graph
    {0: [1], 1: [2, 4, 5], 2: [0, 6, 7], 4: [], 5: [], 6: [], 7: []}
    >>> print(repr(d_graph))
    {0: [1], 1: [2, 4, 5], 2: [0, 6, 7], 4: [], 5: [], 6: [], 7: []}

    Undirected graph example:
    >>> u_graph = GraphAdjacencyList(directed=False)
    >>> u_graph.add_edge(0, 1)
    {0: [1], 1: [0]}
    >>> u_graph.add_edge(1, 2).add_edge(1, 4).add_edge(1, 5)
    {0: [1], 1: [0, 2, 4, 5], 2: [1], 4: [1], 5: [1]}
    >>> u_graph.add_edge(2, 0).add_edge(2, 6).add_edge(2, 7)
    {0: [1, 2], 1: [0, 2, 4, 5], 2: [1, 0, 6, 7], 4: [1], 5: [1], 6: [2], 7: [2]}
    >>> u_graph.add_edge(4, 5)
    {0: [1, 2],
     1: [0, 2, 4, 5],
     2: [1, 0, 6, 7],
     4: [1, 5],
     5: [1, 4],
     6: [2],
     7: [2]}
    >>> print(u_graph)
    {0: [1, 2],
     1: [0, 2, 4, 5],
     2: [1, 0, 6, 7],
     4: [1, 5],
     5: [1, 4],
     6: [2],
     7: [2]}
    >>> print(repr(u_graph))
    {0: [1, 2],
     1: [0, 2, 4, 5],
     2: [1, 0, 6, 7],
     4: [1, 5],
     5: [1, 4],
     6: [2],
     7: [2]}
     >>> char_graph = GraphAdjacencyList(directed=False)
     >>> char_graph.add_edge('a', 'b')
     {'a': ['b'], 'b': ['a']}
     >>> char_graph.add_edge('b', 'c').add_edge('b', 'e').add_edge('b', 'f')
     {'a': ['b'], 'b': ['a', 'c', 'e', 'f'], 'c': ['b'], 'e': ['b'], 'f': ['b']}
     >>> char_graph
     {'a': ['b'], 'b': ['a', 'c', 'e', 'f'], 'c': ['b'], 'e': ['b'], 'f': ['b']}
    """

    def __init__(self, directed: bool = True) -> None:
        """
        Parameters:
        directed: (bool) Indicates if graph is directed or undirected. Default is True.
        """

        self.adj_list: dict[T, list[T]] = {}  # dictionary of lists
        self.directed = directed

    def add_edge(
        self, source_vertex: T, destination_vertex: T
    ) -> GraphAdjacencyList[T]:
        """
        Connects vertices together. Creates and Edge from source vertex to destination
        vertex.
        Vertices will be created if not found in graph
        """

        if not self.directed:  # For undirected graphs
            # if both source vertex and destination vertex are both present in the
            # adjacency list, add destination vertex to source vertex list of adjacent
            # vertices and add source vertex to destination vertex list of adjacent
            # vertices.
            if source_vertex in self.adj_list and destination_vertex in self.adj_list:
                self.adj_list[source_vertex].append(destination_vertex)
                self.adj_list[destination_vertex].append(source_vertex)
            # if only source vertex is present in adjacency list, add destination vertex
            # to source vertex list of adjacent vertices, then create a new vertex with
            # destination vertex as key and assign a list containing the source vertex
            # as it's first adjacent vertex.
            elif source_vertex in self.adj_list:
                self.adj_list[source_vertex].append(destination_vertex)
                self.adj_list[destination_vertex] = [source_vertex]
            # if only destination vertex is present in adjacency list, add source vertex
            # to destination vertex list of adjacent vertices, then create a new vertex
            # with source vertex as key and assign a list containing the source vertex
            # as it's first adjacent vertex.
            elif destination_vertex in self.adj_list:
                self.adj_list[destination_vertex].append(source_vertex)
                self.adj_list[source_vertex] = [destination_vertex]
            # if both source vertex and destination vertex are not present in adjacency
            # list, create a new vertex with source vertex as key and assign a list
            # containing the destination vertex as it's first adjacent vertex also
            # create a new vertex with destination vertex as key and assign a list
            # containing the source vertex as it's first adjacent vertex.
            else:
                self.adj_list[source_vertex] = [destination_vertex]
                self.adj_list[destination_vertex] = [source_vertex]
        else:  # For directed graphs
            # if both source vertex and destination vertex are present in adjacency
            # list, add destination vertex to source vertex list of adjacent vertices.
            if source_vertex in self.adj_list and destination_vertex in self.adj_list:
                self.adj_list[source_vertex].append(destination_vertex)
            # if only source vertex is present in adjacency list, add destination
            # vertex to source vertex list of adjacent vertices and create a new vertex
            # with destination vertex as key, which has no adjacent vertex
            elif source_vertex in self.adj_list:
                self.adj_list[source_vertex].append(destination_vertex)
                self.adj_list[destination_vertex] = []
            # if only destination vertex is present in adjacency list, create a new
            # vertex with source vertex as key and assign a list containing destination
            # vertex as first adjacent vertex
            elif destination_vertex in self.adj_list:
                self.adj_list[source_vertex] = [destination_vertex]
            # if both source vertex and destination vertex are not present in adjacency
            # list, create a new vertex with source vertex as key and a list containing
            # destination vertex as it's first adjacent vertex. Then create a new vertex
            # with destination vertex as key, which has no adjacent vertex
            else:
                self.adj_list[source_vertex] = [destination_vertex]
                self.adj_list[destination_vertex] = []

        return self

    def __repr__(self) -> str:
        return pformat(self.adj_list)
