CSCI4041 HW5
Part B - Graph Algorithms (Programming Problem)
Problem H5.4: Route Mapping (40 points + 5 points possible extra credit)
Figure 1 - Route mapping using a drone visualization.
Instructions: You are to implement several graph algorithms and test them on a drone visualization system.
Submission: Submit the search algorithms .py file to the Homework 5 - Part B Grade- scope assignment.
Setup:
• Download the support code from Canvas: hw5-support-code.zip
• Install python dependencies:
— pip3 install flask
— pip3 install flask cors
• Run the application
— Use a terminal to cd to visualization code directory and run the visualization:
* python3 app.py
— Navigate to http://127.0.0.1:5000
Drone Visualization
The drone visualization allows you to move a robot across the UMN. As soon as the robot moves, the drone will attempt to find the robot and move to its location. Figure 2 shows how to move the robot, Figure 3 shows a control panel where you can choose whether to view the robot or drone. You can also choose the algorithm you would like to use to move towards the robot.
Three simple algorithms already exist to help you get started:
• Point to Point: Moves the drone directly from one point to another.
• Fly: Uses a parabolic arc to fly from one point to another.
• Random Graph: Flies to a random point on the map and then follows a graph to the robot. Figure 3 shows this algorithm in action.
Figure 2 - Click to move the robot and route the drone.
Figure 3 - Interface for choosing the algorithms for the drone to use to find the robot.
Figure 4 - The drone follows a path on a graph to find the robot.
Task / Rubric
The search algorithms .py file has a simple graph implementation and a set of graph al- gorithms for you to implement. You will do all your work in the search algorithms .py file. You should not need to touch the visualization code. Your task is to implement a subset of the following algorithms to reach 40 points (5 points extra credit possible):
• Breadth First Search
– (10 points) - breadth first(start, dest) - Breadth First Search.
– (5 points) - breadth first hub(start, dest) - Every node with 5 or more neigh- bors is considered a hub. Calculate the top three hubs that are closest to both the start and destination using Euclidean distance. Use the breadth first algorithm to visit each hub before reaching the destination (visit hubs in order of decreasing distance from the destination - furthest to closest).
• Depth First Search
– (10 points) - depth first(start, dest) - Depth First Search.
– (5 points) - depth first best(start, dest) - Perform the depth first search, but when choosing an edge to follow, always choose the edge that leads to a node that is closest to the goal (e.g. has the shortest Euclidean Distance).
• Bellman Ford
– (10 points) - bellman ford(start, dest) - Bellman Ford Algorithm.
– (5 points) - bellman ford negative(start, dest) (5 points) - When calculating the weights of neighbors, if the neighbor node name ends with a 0, then it has a negative weight. Use Bellman Ford to find the path to the destination. If no path is found, use point to point navigation.
• Dijkstra / A*
– (10 points) - dijkstra(start, dest) - Dijkstra’s Algorithm.
– (5 points) - astar(start, dest) - A* algorithm using Euclidean Distance as the heuristic.
• Minimum Spanning Tree
– (10 points) - min spanning tree(start, dest) - Calculate and follow the path on a minimum spanning tree to the destination.
For each algorithm, you will take in a start point (3D point) and a destination point (3D point) to write an algorithm that returns a path (list of 3D points) on a graph for the drone to follow. You may calculate the weight of each edge using the Euclidian distance between nodes.
Please look at the random graph(start, dest) function to understand how to use the graph. You can create a graph with the following line of code: graph = MapGraph(‘graph.json’). You may add / edit any structure within the search algorithms.py file including the MapGraph class
Note: The start and destination points passed in are 3D points, not nodes in the graph. Therefore, for each search algorithm, you will first need to find the closest start and destination nodes in the graph. You can use the following method: graph.find closest vertex(point).