The purpose of the Portfolio Assignment is to showcase your programming skills to potential employers and colleagues. This is the only assignment in this course that is allowed to be publicly posted online (e.g. GitHub, personal website, etc. …). While this is a great opportunity to publicize your work, it is not required that you post the assignment online.
This assignment is comprised of 2 parts. In the first part, you will complete the implementation of a undirected graph ADT where the vertices and edges should be stored as an adjacency list. In the second part, you will implement a directed graph ADT where the vertices and edges should be stored using an adjacency matrix.
Part 1- 2: Implementation of Undirected and Directed Graph
For these parts of the assignment, you are going to implement various graph methods and algorithms with the provided skeleton codes(below). For detailed instructions and method descriptions, please read this (updated) document very carefully: CS261 Programming Assignment 6 - v1.02.pdf .
Use the provided tests in the skeleton code to test your code. You are encouraged to write additional unit tests, however, you are not permitted to share any additional tests with other students.
Skeleton Code Files:
Please find the skeleton files below- ud_graph.py
d_graph.py
Scoring
Implementation of Undirected and Directed Graph ADTs:
Undirected Graph (via Adjacency List) add_vertex() -- (2 points) add_edge() -- (4 points) remove_edge() -- (4 points) remove_vertex() -- (4 points) get_vertices() -- (3 points) get_edges() -- (5 points) is_valid_path() -- (6 points) dfs() -- (6 points) bfs() -- (6 points) count_connected_components() -- (4 points) has_cycle() -- (6 points)
Directed Graph (via Adjacency Matrix) add_vertex() -- (2 points) add_edge() -- (4 points) remove_edge() -- (4 points) get_vertices() -- (3 points) get_edges() -- (5 points) is_valid_path() -- (6 points) dfs() -- (6 points) bfs() -- (6 points) has_cycle() -- (6 points) dijkstra() -- (8 points)
What to Turn In (2 files)
You will turn in the above two files via Gradescope (available right now!). There is no written part of this assignment.
The python files will be submitted through Gradescope from this assignment page:
Assignment 6: GradeScope Submission