**Submission:**

Submit your homework via E-learning

**Deliverables:**

Name your file as StudentID_FirstName.py

Sample input graph file

**Description:** We are going to implement undirected graph representation

**def load_graph (graph, filename):**

Reads the content of filename (e.g. graph1.txt) to build the graph. The graph is represented as a dictionary where keys represent vertices and values are list of vertex neighbros. See belowgraph = { "a" : ["c"], "b" : ["c", "e"], "c" : ["a", "b", "d", "e", "h"], "d" : ["c"], "e" : ["b", "c"], "f" : ["g", "h"] "g" : ["f", "h"] "h" : ["c", "f", "g"] }

Each line in the input file contains an edge representated as**source****destination****def get_vertices (graph):**

Returns a list of graph vertices.

['f', 'h', 'b', 'a', 'c', 'e', 'd', 'g']**def get_edges (graph):**

Returns a list of graph edges.

[('c', 'a'), ('c', 'b'), ('c', 'd'), ('c', 'e'), ('c', 'h'), ('g', 'f'), ('g', 'h'), ('e', 'b'), ('e', 'c'), ('f', 'g'), ('f', 'h'), ('a', 'c'), ('b', 'c'), ('b', 'e'), ('d', 'c'), ('h', 'c'), ('h', 'f'), ('h', 'g')]**def are_adjacent (graph, vertex1, vertex2):**

Returns True if vertex1 and vertex2 are adjacent (there's an edge between them), False otherwise**def get_adjacency_matrix (graph):**

Returns an adjacency matrix representation of the graph. The adjacency matrix is a 2D array of 0's and 1's. matrix[i][j] = 1 if there's an edge between vertex i and vertex j and matrix[i][j] = 0 if there's no edge between vertex i and vertex j**def print_matrix (graph, matrix):**
Prints the adjaceny matrix. Vertices are displayed in ascending order

a b c d e f g h a 0 0 1 0 0 0 0 0 b 0 0 1 0 1 0 0 0 c 1 1 0 1 1 0 0 1 d 0 0 1 0 0 0 0 0 e 0 1 1 0 0 0 0 0 f 0 0 0 0 0 0 1 1 g 0 0 0 0 0 1 0 1 h 0 0 1 0 0 1 1 0

Returns the shortest path between start and end vertices. If there is no path between start and end the function returns None.

Takes graph edges and plot the graph