I attached file
Name of Student: ______________ Class: Spring 2021 SENG 2000 Professor: Dr. Jonathan A. Saddler SENG 2000 Assignment 2P Graph Tree Node Finding Due Wed. Mar 17. 6:00 PM to Canvas 25-pt. assignment Goal: Demonstrate proficiency in determining implications of concrete graph search algorithm outputs. Your Task: Each of the following problems is made of a graph and a set of problems. You are not given certain input graphs in advance, other than the graph for Problems 1 and 2, which could potentially be used to test most of the problems below other than these two. Please answer these questions with answers saved to this answer document, and using Python files you create and upload to Canvas named and labeled as specified below. Do not zip up the python files using an archiver. Rather, upload all python files separately as part of your Canvas submission with this assignment document. Problems 1 and 2: Edges above are numbered 1 – 14. Vertices are numbered a – h. 1. List the numbered edges that are not part of the tree created by running breadth-first search starting with vertex a. (5pts) (-1pts for answers missing) (-1pts for extra answers) (in case of ties when selecting a single node from the adjacency list to add to the queue, assume that edges leading to a vertex must be added in alphabetical order) (there should be 6 edges) Answer: 2. List the numbered edges that are not part of the tree created by running depth-first search starting with vertex a. (use tie-breaking rules from above) (5 pts) (-1pts for answers missing) (-1pts for extra answers) Answer: Problems 3 and 4: Programming exercises. 3. Modify the BFS program to locate and print one of the “most-distant vertices” from the BFS start vertex that exists on the graph after running BFS, using the parents tree. Every BFS parent tree with edges has at least one path that is of maximum length. The most distant vertex is the one or one of many vertices at the end of some path on the BFS parent tree that is of maximum length. Solve this problem while following the input constraints below, and name the file that takes input to your program: BFS_MD.py (5pts) (hint, locate nodes that are not parents to any other node (leaves), then write code that locates the parents of these leaves, and tries to build a path to the start vertex. I will run tests on your program to determine that it works according to the below specifications. Testing Input constraints: The input graph is not allowed to have cyclic relationships. The input graph may have between 1 and 9 vertices, and between 0 and 30 edges. Your program must take an arbitrary number of vertices and edge specifications as does the current program posted to Canvas. The name of each vertex will be a number. The length of the path to the most-distant vertex will be between 4 and 9-hops-long. Test rubric: The program does not crash on any of my inputs (1pt) The program prints at least (a) one edge from the input graph when run on one of my tests, and (b) at least one correct most-distant vertex on that same test. (2pts) The program passes not just one but all tests, and for each test, prints one most-distant vertex and its full path. (2pts) Total 5pts Output Constraints: A path is a list of edges, which can be expressed as a list of ordered doubles, i.e. [ (a, b), (b, c), (c, d), (d, e) ] is the path leading to the most distant vertex in the graph above, vertex “e” Print this path to the console, to the left, as a sequence of edges to the left of (or right of) the lettered name of the most distant vertex. 4. Modify the DFS program to determine the length of the longest path that exists on the graph, and to print that path. (10 pts) Name your python file DFS_LP.py, and be sure to upload all supplementary files along with your submission, by appending _LP.py to the ends of the Python files that you use to create this submission (vertex_LP.py, graph_LP.py for example) (hint: note that the longest path is not necessarily the path to the “most-distant vertex”) Testing Input Constraints: · The input graph is not allowed to have cyclic relationships. · The input graph may have between 1 and 12 vertices, and between 0 and 30 edges. · Your program must take an arbitrary number of vertices and edge specifications as does the current program posted to Canvas. · The name of each vertex will be a letter this time. · The length of the longest path may be between length 1 and length 10. The program does not crash on my inputs 3pts The program prints at least (a) one edge from the input graph in the longest path is printed when one of my tests runs, and (b) at least one correct length of some longest path 3pts The program passes not just one but all tests, and for each test, prints one longest path and the correct length. 4pts Total 10pts Output Constraints: A path is a list of edges, which can be expressed as a list of ordered doubles, i.e. [ (a, b), (b, c), (c, d), (d, e) ] is the path leading to the most distant vertex in the graph above, vertex “e” Print this path to the console, to the left, as a sequence of edges to the left of (or right of) the length of the longest path.