## Python, graph, graph_list.py

``````#!/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")

"""
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()
>>> d_graph
{}
{0: , 1: []}
{0: , 1: [2, 4, 5], 2: [], 4: [], 5: []}
{0: , 1: [2, 4, 5], 2: [0, 6, 7], 4: [], 5: [], 6: [], 7: []}
>>> print(d_graph)
{0: , 1: [2, 4, 5], 2: [0, 6, 7], 4: [], 5: [], 6: [], 7: []}
>>> print(repr(d_graph))
{0: , 1: [2, 4, 5], 2: [0, 6, 7], 4: [], 5: [], 6: [], 7: []}

Undirected graph example:
>>> u_graph = GraphAdjacencyList(directed=False)
{0: , 1: }
{0: , 1: [0, 2, 4, 5], 2: , 4: , 5: }
{0: [1, 2], 1: [0, 2, 4, 5], 2: [1, 0, 6, 7], 4: , 5: , 6: , 7: }
{0: [1, 2],
1: [0, 2, 4, 5],
2: [1, 0, 6, 7],
4: [1, 5],
5: [1, 4],
6: ,
7: }
>>> print(u_graph)
{0: [1, 2],
1: [0, 2, 4, 5],
2: [1, 0, 6, 7],
4: [1, 5],
5: [1, 4],
6: ,
7: }
>>> print(repr(u_graph))
{0: [1, 2],
1: [0, 2, 4, 5],
2: [1, 0, 6, 7],
4: [1, 5],
5: [1, 4],
6: ,
7: }
>>> char_graph = GraphAdjacencyList(directed=False)
{'a': ['b'], 'b': ['a']}
{'a': ['b'], 'b': ['a', 'c', 'e', 'f'], 'c': ['b'], 'e': ['b'], 'f': ['b']}
>>> print(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

self, source_vertex: T, destination_vertex: 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:
# 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:
# 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:
# 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:
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:
# 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:
# 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: