CPE 103 Graph Lab: Dijkstra
Using the JGraphT library to solve graph problems

Warning: These instruction do not tell you everything you need to know to solve this problem.
Some details are intentionally omitted; you have to figure these out on your own. Ask the instructor if you get stuck, not other student teams.

Goal: Write a program to find a path through a maze.

Background: Fig 24.5 in the text shows an example of a maze with a start point at the upper left and the exit point at the lower right. 

If we can figure out some way to represent the maze as a graph, then solving the maze is simply using Dijkstra's Shortest Path algorithm.  Luckily, the kind folks at the JGraphT project have provided a library that includes Dijkstra's algorithm, so we don't have to write it ourselves.  We just have to download their library (a jar file) and we can use it.
Download jgrapht-core-0.9.0.jar

So the challenge is, how can we represent the maze as a graph?

Here's how to derive a representation:
A graph is composed of edges and vertices.  So what part of the maze will be represented by a vertex, and what part will be represented by an edge?  One way to think of a maze is that it is rooms and walls.  But that doesn't lend itself to a graph representation.  Another way to think of a maze is as a set of connected rooms.  Then we can represent it similar to an Adjacency List. An edge in the graph can represent a connection between two rooms, where each vertex represents a room.

Using this idea, the maze in figure 24.5 can be represented as follows:

0 1
1 0 2 6
2 3
3 2
4 9
5 10
6 1 7 11
7 6 8
8 7 9
9 4 8 14
10 5 11 15
11 6 10
12 17
13 14 18
14 9 13 19
15 10
16 17 21
17 12 16 18 22
18 13 17
19 14
20 21
21 16 20
22 17 23
23 22 24
24 23

(You should double check that I have that correct).
The vertices are the first number in each row, and the cells that it is connected to are the subsequent numbers on that row.

Manually determine the shortest path through this maze and write the solution in your lab notebook.

Suggested Procedure

Download the JGraphT library and place the jar file where it is available on the classpath for your IDE.
Write a spike to make sure you can compile using JGraphT.  For example,

      SimpleGraph<Integer, DefaultEdge> myGraph;
      myGraph = new SimpleGraph<Integer, DefaultEdge>(DefaultEdge.class);

Then add some vertices and edges using the addVertex and addEdge methods with some hard coded parameters.
Then print the graph and see that they were added properly.


Next, design a MazePathFinder class that can work for any maze.

public class MazePathFinder
{
    /** Read the maze data */
    public void load(java.io.Reader reader)
    /** Find shortest path between two vertices */
    public java.util.List findShortestPath(int start, int end)
}
Write the pseudocode for your solution in your notebook before creating any code on the computer.

The load() method should read the adjacency list from a Reader.  Construct the vertices and edges for your graph from each line of input.
The findShortestPath() method simply invokes the Dijkstra algorithm. 
You'll probably want to write a driver with a main() method that prints the path to standard output.
Write a JUnit test that uses an assert to verify that your methods compute the correct solution to the maze.


Submit your completed source code and JUnit tests via Web-CAT.