Assignment 5

Harvey Mudd College
Computer Science 60
Assignment 5, Due Thursday, October 7, by midnight

"Emulating Mouse Intelligence ?"

Assignment 5 puts your code in the position of a laboratory mouse, seeking the shortest path from its starting point in a maze to the exit (or a piece of cheese, perhaps). In this assignment the maze will be represented by a directed graph (imagine a labyrinth of one-way and two-way doors), and the goal is to find the shortest path available from a starting node to a designated finishing node. It will require implementing breadth-first search, a Queue class, and a QCell class.

The next assignment will add a graphical interface and package the whole application as an applet.

File and Classes to Create

You will need to create the file BFsearch.java and submit it with cs60submit. In /cs/cs60/assignments/a5 there is a skeleton file you can use. It offers slightly less in the way of code than the Java Unicalc skeleton code from Assignment 4.

In this BFsearch.java file, you will need to write three classes:

BFsearch: This class should have a method named main that controls the thread of execution for the graph search. It should have whatever additional methods are needed to keep main readable and clear. These will likely be static methods -- the intention is not to actually create any BFsearch objects, but merely use this class as a central place to bring together the other classes you will need to create.
Queue: This class should implement a queue as a linked list. Although Java offers a LinkedList class (java.util.LinkedList), for this assignment you need to write the linked list from scratch. (Editorial comment: it would be remiss of any intro CS course not to include a linked list at some point... .) Thus, you need to create cells which hold both data (java Objects) and a reference to another cell (which may point to the next cell in the queue or be null, in the case of the queue's tail cell). You should implement those cells with a QCell class (see the next item).
QCell: This class implements the cells that your Queue class should use to hold data. Since only Queue will use QCell, it is cleanest to make QCell an inner class, that is, a class defined within Queue itself. The skeleton of the QCell class is provided as an inner class in the file BFsearch.java.

Files and Classes available to use

A Graph class which implements the GraphInterface interface is available in /cs/cs60/java/graph. To use it and related classes, you only need to include the line

import graph.*;

at the top of your BFsearch.java file. Because some of the classes in java.util and the Polylist class will be used, you will also want to

import polya.*;
import java.util.*;

at the top of your file. These lines are already included in the BFsearch.java skeleton file.

You can look up the methods available for Graph and its related classes from this webpage of docs on the Graph package. Also, the reference links page has a pointer to the Polya package online reference.

What does the code have to do?

The code will be given a directed graph as input. Each node of that directed graph will be labeled with a name (a String object). Also, your program will be given the name of the starting node and the goal node of the search.

With all of this information, your code needs to perform a breadth-first search on the given Graph in order to find the shortest path from the starting node to the finish node. As it does, it should enqueue the nodes which remain to be expanded. (Here you should use the Queue class you have implemented.) Each enqueued node should "carry with it" the path which has been traversed thus far (from the start to the node in question). That path should be in the form of a Polylist (for easy manipulation and output).

When the breadth-first search finds the goal node, it should then output the path that was found from the start to the goal. This will be the shortest such path in the graph. Though in general there may be other paths with an equal number of steps, we will try to ensure that there is a unique shortest path for the test inputs.

Thus, your code's output must be of the form

shortest path = (start n1 n4 n6 n2 goal)

where start, n1, n2, n4, n6, and finish are the names of nodes along a shortest path from start to finish.

If there is no path from the start to finish, the output should be

shortest path = ()

that is, the empty Polylist encodes a nonexistent path.

My code finds the goal node... how the heck do I get the whole path?

It was mentioned in passing above, but when you enqueue a node onto the queue, you will also need to enqueue the path that has been taken to get to that node so far (from the starting node). One way to do this is not to enqueue a single node, but to enqueue a Polylist of nodes. This polylist can have any format you choose, but one possibility is to make the first element of the list the current node (which needs to go on the queue) and have the rest of the list be the nodes which lead from start to the current node. If these are in reverse order, it becomes very easy to extend this to the current node's children (targets) with cons.

Other things to be aware of include

In a general graph, it is possible to travel through cycles during the course of a search. For depth-first search, this can be very bad. For breadth-first search, this merely means that a given node might be pending to be explored on the Queue many times. Your code should avoid traversing any loops by checking if a node that is about to be enqueued forms a loop. (Recall that every node being enqueued also "carries" (in a Polylist) all of the nodes on the path from the start to it.) If it does form a cycle, do not enqueue it. If it does not form a cycle, do enqueue it.
Even with the check described above, you may end up enqueuing a node in the Queue many times -- for example, if there is fan-in going into a node, it may be reached several times without ever forming a cycle. Completely optionally and for additional credit, use Java's Hashtable class to store all of the names of the nodes which get enqueued. Then, make sure no node gets enqueued more than once by checking the hashtable before inserting each potentially new node.

What doesn't the code have to do?

Your code does not have to handle the input. Code for taking in input from a file (or the keyboard) will be included in the skeleton file BFsearch.java. The input will be transformed into an object of the Graph class. You'll need to do all of your processing with this object.

Here is a listing of the skeleton file BFsearch.java in /cs/cs60/assignments/a5. The main method of the BFsearch class is entirely implemented for you -- graphs are taken in as Polylists, parsed, and converted to a Graph object named graph.

You will need to write the search function in the BFsearch class, the Queue class, and the inner class QCell which Queue will use.

// file:    BFsearch.java
//
// purpose: read in directed graphs as S expression, followed by start and
//          end node names, on standard input, create Graph, and perform
//          breadth-first search from start to end.  If a path is found, the
//          node names in the path are printed.  If not, then the program
//          prints ()
//
// author:
//
// date:
//
// IMPORTANT NOTE: This file is largely uncommented. In addition to
//                 commenting what you are writing, be sure to include
//                 the how and why -- how you're tacking the problem
//                 and why you make any decision you do.

import graph.*;
import polya.*;
import java.util.*;

/*
 * Class BFsearch holds the static search function.
 */
public class BFsearch
{
  public static void main(String arg[])
  {
    // Tokenizer to read Polylists, and atoms

    Tokenizer in = new Tokenizer(System.in);

    Object ob;

    while( (ob = in.nextSexp()) != Tokenizer.eof )
    {
      // Get next item, to end-of-file, and try to parse as Graph.

      Graph graph = GraphParser.parse(ob);

      if( graph == null )
      {
	System.out.println("input item not parseable as a graph");
      }
      else
      {
	System.out.println(graph);
      }


      // Get next item, interpret as start, unless end-of-file.
      ob = in.nextSexp();
      if( ob == Tokenizer.eof )
	break;

      Node start = graph.ensureNode((String)ob);


      // Get next item, interpret as stop, unless end-of-file.
      ob = in.nextSexp();
      if( ob == Tokenizer.eof )
	break;

      Node stop = graph.ensureNode((String)ob);

      System.out.println("start = " + start + ", stop = " + stop + "\n");


      // Search the graph and report results.

      Polylist path = search(graph, start, stop);

      if( path.isEmpty() )
	System.out.println("shortest path = ()\n");
      else
	System.out.println("shortest path = " + path + "\n");
    }
  }


  // search graph breadth first, finding the shortest path from start to finish
  // If a path is found, the list of nodes on the path are returned.  Otherwise
  // the empty list is returned.

  public static Polylist search(Graph g, Node start, Node finish)
  {

    /* Here is the place to fill in your search code */
    

    return Polylist.nil;                          // No path found.

  }
}


/*
 *   A general Queue class using uni-directional linked lists
 */

class Queue
{
    class QCell
    {
	/* Create the QCell class here */
    }

    /* Create the rest of the Queue class here */
}

Testing your code

In the /cs/cs60/assignments/a5 directory, you will find test files graph1.in, graph2.in, etc. Each of these files encodes a graph and has a designated start and finish node. By running

java BFsearch < /cs/cs60/assignments/a5/graph1.in > output.out

(or graph2.in or whichever one you'd like to use), your program should get the input it needs to compute the shortest path and place the output in the file output.out. If you would like to see the output appear in the shell, merely omit the > output.out part of the command. You can compare the answer your program generates with the answers in the files graph1.out (or whichever corresponds to your input) with the unix command

diff ./output.out /cs/cs60/assignments/a5/graph1.out

This command returns the differences between the two files. Thus, if it returns nothing at all, your output matches exactly. Otherwise, sets of lines will appear that detail where the two files differ.

Reading

You will want to have read to at least Chapter 7 of the text for this assignment. Both CS60 sections have skipped over Chapter 6 -- except for section 6.4. In addition, you may need to consult your Java reference (be it online or a book).

Submission

You should submit your BFsearch.java source file in the usual way, i.e., by running

% cs60submit BFsearch.java

You will be asked to input the assignment number (5).

Harvey Mudd College Computer Science 60 Assignment 5, Due Thursday, October 7, by midnight