For the graph visualization algorithm, we would create an image of the plotted nodes along with their edges. This would help demonstrate the mapped road network. To complete this task, we first attempted to plot each node using our adjacency list. After we did this, we noticed that each node was hardly visible and eventually chose to use a 3 by 3 square to plot each node. Following this task, we began to connect each node together using the edges established by our adjacency list. We would draw this using Bresenham’s Line Generation Algorithm. This would allow us to draw lines between our nodes. We would also check to make sure repeat edges would not be drawn between nodes. Through this, we were successfully able to visualize the graph along with the road network of San Francisco. We discovered that we had to flip the y axis to be a working graph. The output of our graph visualization algorithm is stored as a file named "Graph_Visualization_Output" in the results folder of our repository.
For our traversal algorithm, we chose to implement BFS. The purpose of our BFS algorithm was to traverse the graph and mark each node that made up our graph as visited. We used our adjacency list, which was built using a linked list, in this algorithm. Each node that was stored in our adjacency list had pointers to all of the nodes that it was connected to via an edge in the graph. We passed in the starting node ID number as a parameter to our function. After that, our traversal algorithm placed each node into a queue, and as each node was placed into the queue, we would traverse through the respective node’s linked list. The linked list was ordered starting with the nodes that were closer to the parent node, and ending with the nodes that were furthest. As we traversed through the linked list for a particular node, all connected nodes were marked as visited. We repeated this process for each node in the adjacency list, and stopped when every node that made up our graph was marked as visited. The algorithm returned a vector of boolean values which was the size of all nodes in our graph. If each node had been visited in our graph, then every value stored in the vector would be marked as true.
For the shortest path algorithm, we would pass in the starting ID of a node as a parameter. From that point, our algorithm would find the shortest path between the starting node and each node in the graph that it was connected to. We did this by keeping a minimum distance tracker for all neighboring nodes and seeing which node had the minimum distance from the starting node. As we went along, we kept track of nodes that were visited and unvisited as we moved between nodes, as well as the distances between the starting node and each node and the previous node for each node in the graph. Once we were at a point where there were no more connected nodes that we could visit, we knew that we had found the shortest path. Our function returned a pair of vectors, the first being the vector containing the distances, and the second being the vector containing the previous nodes. In our function, we printed the id of each node that we visited to the terminal. The terminal output of our algorithm when calling the function starting at the node ID 44 is stored as a file named "Shortest_Path_Terminal_Output" in the results folder of our repository.