Assignment 4: Graphs

In this assignment, you will write a search algorithm that connects a start and goal location on the Dartmouth campus. Here is a screenshot of the complete program in action:

Grab the provided code and unzip it on cloud9. Use cloud9 to serve the pages, and navigate to graph.html to run the code.

We have written some code to get you started. graphLoad.js loads the data from the file dartmouth_graph.txt into a dictionary representing the graph. graphDisplay has all of the fancy graphics that loads the image of the map (dartmouth_map.png), displays it in a processing.js window, etc.

Once everything is working, the user should be able to click on a blue circle representing a location. That location will become the starting location for the graph search, and the blue circle will turn green. Then the user can wave the mouse arrow over another blue circle, which will turn red, and be the goal for the search. The program will then draw a path between the start and the goal.

Your job is to write the main logic for the function graphSearch in graph.js. Whenever graphDisplay.js needs to compute a path between two nodes, it will call your code in graphSearch to do that. graphSearch will return an array of strings representing the names of the locations, in order.

Nodes and the graphDict dictionary

Take a look at dartmouth_graph.txt. It describes what nodes are adjacent to which other nodes. For example, the line

Tuck; Murdough, Buchanan; 116, 487

tells you that the node named Tuck has two nodes adjacent to it: nodes named “Murdough” and “Buchanan”

The code we have provided loads data from a file and creates the graphDict structure, which we will now describe.

The information about a location of the graph is stored in a data structure called a node. A node is an object containing a few variables: the name of the node (a string), the x and y locations of the node (numbers representing pixel coordinates, but you won’t need these values), and adjacent, an array of strings representing adjacent location names.

You can use the graphDict dictionary to look up the node object for a given node name. So for example, if I wanted the node associated with the location Tuck, I could do: var node = graphDict["Tuck"]. Then I could inspect the x coordinate of that node using node.x, or the array of adjacent node names with node.adjacent.

How to get started

Break the problem down. The function graphSearch needs to do two major things:

breadth-first search. build a dictionary that represents how each node was reached during the course of the search. For example, if the node named “Buchanan” was first reached from the node named “Tuck” during the search, visitedFrom[“Buchanan”] has the value “Tuck”. To build this dictionary, we run the breadth-first-search algorithm we talked about in lecture. We add the first node to a queue. Then, while the queue is not empty, we pull the current node off the queue, find out what nodes are adjacent to it, and for each adjacent node that hasn’t already been reached, update visitedFrom to indicate that the adjacent node was visited from the current node.
backchain. During the search process, the goal might be pulled off of the queue. We should check for this situation. When it does, we have found the goal and can make use of visitedFrom to see where the goal was first reached from, where that node was reached from, and so forth back to the start. We can use a loop for this process, and build up an array of strings representing the sequence of nodes that connect the goal and the start.

The recommended way to tackle this problem is to start by writing the breadth-first search. Do a single search, and do one thing at a time. Pull the first node name (a string) off the queue. Figure out what nodes are adjacent to that node using the graphDict dictionary. Print some things out to verify that you have what you want. Ok, now add those adjacent node names to the queue, if they haven’t been visited (which you can check by looking them up in visitedFrom). If they haven’t been visited, then add to visitedFrom. Make sure each one of these steps is doing exactly as you intend before you pull any more nodes off the queue, etc. Then you are ready to test your loop. Once you are confident that visitedFrom is being built correctly, you can do the backchaining.