Assignment A6: Searching Implicit Graphs

Overview

Graphs are often presented explicitly in courses on data structures and algorithms. For example, the undirected graph G = (V, E), where V = {v₀, v₁, v₂} and E = {(v₀, v₁), (v₁, v₂)} is presented with an expression that gives each vertex and edge its own representation. In real applications, it is often the case that a graph is presented only implicitly; its vertices and edges have to be constructed by code as an algorithm runs. In this assignment, you'll work with one family of such implicit graphs.

A problem-space graph is an implicit graph whose vertices represent "states" corresponding to possible situations that can be reached in the course of solving a problem. The edges represent possible transitions from one state to another according to a set of "operators." Such a graph is typically given by providing a start vertex v₀ (corresponding to the problem's "initial state," s₀) together with a set of operators { ϕ₀, ϕ₁, ..., ϕ_m-1}. Each operator ϕ_i consists of two parts:
precondition_i: a predicate that takes a vertex as its argument and returns true iff and only if it is permissable to apply this operator's transition function to the vertex.
transition_i: a function that takes a vertex as its argument and returns a new vertex. The old and new vertices (call them v_x and v_y) represent an edge of the graph.

Typical tasks associated with problem-space graphs are (a) solving the problem, (b) exploring all or a portion of the space by "visiting" all or some of its vertices, (c) finding shortest paths between given pairs of vertices, (d) measuring properties of the graph such as average degree of a vertex, (e) finding the diameter (length of a longest shortest path between two of its vertices), and (f) building a visual display of the graph.

The basic functionality that you'll provide in this assignment will handle the finding of shortest paths, using breadth-first search (BFS). This can be used, in principle, to solve problems as well. In addition to breadth-first search, you'll implement one or more additional algorithms that will serve to compare BFS to alternatives.

We'll work with a problem space based on a popular puzzle, but we won't stop there. We'll consider a couple of "extensions" to the puzzle that will make this assignment not just an exercise but also more of an exploration in its own right. The puzzle is really a family of puzzles. Known as the Towers of Hanoi, it involves three pegs and a set of disks of different sizes. The player (solver) of the puzzle starts with all the disks on the first peg, the disks being arranged with the largest-diameter one at the bottom and sizes decreasing going up the stack. The objective is to move all the disks to the third peg, respecting the following constraints: only one disk may be moved at a time. Only a disk that is topmost in its stack of disks may be moved. It must then be moved either to a peg containing no disks or to a peg where the topmost disk is of a larger diameter than its own. The reason this is a family of puzzles rather than a single one is because the number of disks involved is a parameter to the initialization of the puzzle. For example, an instance of the puzzle with 5 disks is a little more difficult to solve than one with only 4 disks. An instance having 100 disks, while solvable in theory, is impossible in practice, assuming it takes at least one femtosecond to make a move.

Our graph is defined implicitly as follows. The starting vertex v₀ represents the initial state of the puzzle. We have six operators: { ϕ_0,1, ϕ_0,2, ϕ_1,0, ϕ_1,2, ϕ_2,0, ϕ_2,1}. Here, operator ϕ_i,j could be interpreted as "Try to move a disk from peg i to peg j." We are using 0-based indexing for the pegs so peg 0 is the first peg, etc.

Here is the ExploredGraph.java starter code file. (Alternatively, you may use a newer version that contains a couple of improvements made by staff member Kuikui Liu.) The starter code includes basic definitions for the classes and gives, for the Vertex class, a constructor that accepts a string of the form below.

Vertex v0 = new Vertex( "[[4,3,2,1],[],[]]" );

All of your code will be added in this file. To help you find places where you should add code, there are several "// Implement this" comments. In addition to the code you add, provide line-by-line comments in your code and per-method comments for those methods that you implement. These per-method comments will normally be about one to three lines of text, as needed to describe the purpose of the method. The comments do not have to be in JavaDoc format. In these per-method comments, you should say what the input arguments represent and what the return value represents.

Partnership Option

You are encouraged to find and work with a partner in this assignment. If you work with a partner, you will be able to split the work, possibly do more of the extra credit options, and gain partnership experience. If you work alone, on the other hand, coordination is simpler, and you get to do all of the analysis of the assignment and implementation yourself. If you work in a partnership, you will be asked to explain how you divided up the work of the assignment. Normally, partners will receive the same score in the assignment. However, in some unusual cases, the scores could be different.

Basic Code Specification

Implement the following classes and methods:

Vertex: a class to represent vertices of the graph. Since each vertex represents a state of a Towers-of-Hanoi puzzle, it must contain the basic information about which disk is on which peg. It should have a toString() method that returns a string of the form "[[4,3,2,1],[],[]]". The starter code includes one constructor and the toString method.
Edge: a class to represent edges of the graph. Provide a constructor, a toString method, and methods to retrieve endpoint1 and endpoint2 of the edge (call them getEndpoint1() and getEndpoint2()). If you do the extra credit A6E2, also provide methods setEdgeCost(int c) and getEdgeCost().
Note: The toString method should use the following format: "Edge from [[4,3,2,1],[],[]] to [[4,3,2],[1],[]]". Notice that although we sometimes consider edges of these graphs to be undirected, we will consider our edges here to actually be directed. Thus, there may be an edge in our graph whose string representation is "Edge from [[4,3,2],[1],[]] to [[4,3,2,1],[],[]]", but we will consider these to be distinct.
Operator: a class to represent operators for the problem. There should be methods to construct operators, access their components, and apply their components. getPrecondition() should return a function that can be applied to a vertex to find out whether the operator's transition function is applicable to the vertex. getTransition() should return a function that can be applied to a vertex (provided that the precondition is true) to get a "successor" vertex -- the result of making the move. toString() should return a string that describes this operator, clearly differentiating it from the others.
ExploredGraph: a class that holds a collection of vertices and a collection of edges. It will be used to store the portion of the problem-space graph that has been made explicit by the program so far. It should have the following methods. initialize(v) should set up an instance of this class, and insert the starting vertex v into its set of vertices. Typically, v will be the start vertex, but your method should allow any legal vertex for the problem-space graph. [Optional alternative added Nov. 24 for consistency with starter code: initialize(), which should set to empty the explored graph's sets of vertices and edges. The autograding software will accept either of these signatures.] nvertices() should return an int giving the number of vertices currently in the explored graph structure. nedges() should return an int giving the number of edges currently in the explored graph structure. bfs(vi, vj) should run a breadth-first search starting at vi and continue until reaching vj. dfs(vi, vj) should run a depth-first search starting at vi and stopping either when reaching vj or running out of options or resources. retrievePath(vj) should use the path links established by the most recent call to bfs or other search method, and it should return the path to vj. The path should end at vj, and that might require reversing the list of vertices obtained by the backtrace. shortestPath(vi, vj) should use bfs and return a list of vertices that starts with vi and ends with vj representing a shortest path in the problem-space graph from vi to vj. This can be implemented using a combination of bfs and retrievePath.

Extra credit options

Each of the following options can earn you some extra credit. However, do not attempt the extra credit features until you have the basic features working correctly. If you have implemented any of the extra credit features, add another comment line near the top of your main source file explaining which ones you finished. For example: "* We completed Options A6E1 and A6E2."

(Option A6E1) 5 points. The standard Towers of Hanoi puzzles always use three pegs. Allow the number of pegs in the problem to be greater than 3. This should be done by introducing a new Vertex constructor that can handle a more general kind of state expression. For example, instead of just handling [[4,3,2,1],[],[]], it could also handle [[4,3,2,1],[],[],[]] or even [[2,1],[5,3],[],[],[6,4]]. Then you will need to create the set of operators so that there are npegs*(npegs-1) different operators. So when npegs = 4, there should be 12 operators.

(Option A6E2) 5 points. Turn the problem-space graph into a weighted graph using the following criteria. The disks are already numbered 1, 2, 3, 4, etc. If an edge represents moving a disk number k from peg i to peg j, then make the cost of that edge be a function of three variables: i, j, and k. Implement a choice function useEdgeCostFunction(m) where m selects one of the following cost functions:

edgeCost(i, j, k) = 1.
edgeCost(i, j, k) = k.
edgeCost(i, j, k) = k².
edgeCost(i, j, k) = 2^k.
edgeCost(i, j, k) = p 2^k, where p = 0.1 if j=1 and p = 1, otherwise. (This cost function is supposed to encourage moving disks to the middle peg.)
edgeCost(i, j, k) = ? (make up your own function here, to try to force the shortest solution path to be strange.)

Your shortest-path method should then use the weighted distances when performing its computation. You should use Dijkstra's method here.

(Option A6E3) 5 points. Do this option only if you have completed A6E2. Instead of using Dijkstra's algorithm to find a shortest path from vi to vj, implement A* search, which is a well-known method for efficiently finding a path in a problem-space graph from a starting vertex to a goal vertex. You will need to design a "heuristic" function as part of this option. If you are working on this, we'll have a discussion in GoPost on how this can be done.

(Option A6E4) 5 points. Using your choice of graphics package, plotting method, or GUI tools, find a way to display a graphical representation of (a) the explored graph created by your programs, and (b) the most recently retrieved path. The illustration at the top-right corner of this page shows roughly what such a display might look like, for the graph display. You may use Java's GUI-construction package called Swing and a JPanel object to draw on. You could also write your display method in some other language and output your graph as a file that is then read by the display program. If you do this option, turn in the additional code (if separate), and a screen shot of one of your dislayed graphs.

Lead TAs

Kuikui Liu, Rahul Nadkarni and Hunter Zahn are serving as lead TAs for this assignment.

Turn-in

Turn in your source files through our Catalyst CollectIt dropbox. This assignment is due Wednesday, March 2 at 11:59 PM. Late penalties apply (see the policies page for details).

Each student should turn in a README.txt file containing answers to the following questions

What is your name (last name first)?
Did you work with a partner? If so, what is your partner's name (last name first)?
Which extra-credit options (if any) did you complete?
If you worked in a partnership, how did you divide up the work of the assignment -- analyzing the specification and/or questioning the teaching staff; setting up a new programming environment such as Java 8 with Eclipse; Implementing the methods for the classes Vertex, Edge, Operator, ExploredGraph, and the search methods dfs, bfs, retrievePath, etc.
What did you learn from this assignment? Include concepts such as graph representation by adjacency lists, graph search algorithms, problem-space theory (operators, preconditions, transition functions), combinatorial explosion (size of graph as a function of number of disks, etc.). Also include skills such as programming with Java 8's functional features, teamwork, etc.
If your assignment is late, how do you wish to handle the lateness penalty? (Answer for yourself, not your partner, if you have one.)

If you are in a partnership, the "partnership representative" must turn in your source file (ExploredGraph.java), but both partners must turn in separate README.txt files. The partnership representative is that partner whose last name comes earlier in the alphabetical ordering of names.

If you are working in a partnership and wish to submit the assignment late, you may each take an equal number of late days, if you both have those options still available. Alternatively, if a partner does not have enough late-day options remaining, that partner may pay the lateness penalty for the number of days needed.

Version 1.02. Recent updates: version 1.1b of starter code added Feb. 27 (the link in parentheses). Added format information for the toString method of class Edge, Feb. 25.