*Little programming project on graphs and other data structures.*

*Objectives:
Gain experience in working with graphs and hash tables, too. *

*Directly
related to: Lectures 9-11. Review on File Reading.*

So part of your job is to organize
your work**: Work in double-groups**, make plans,

and delegate some of the
tasks to group members. This time, delegation is ok J

Demonstrate your solution in the lab!

- Explain the adjacency matrix
and
*one other*data structure for storing graphs. - Why do graph implementations
(normally) map the vertices of a graph to a uninterrupted sequence of node
numbers?
- Usually, we use a hash table to
map vertex names to node numbers. Is it a good idea to immediately use the
hash index of a vertex as its node number? Explain!

** **

Imagine that by unexpected luck, from a very
distant and yet unknown great granduncle, you inherited an medieval castle in
Mid-Wales, called Gwyneth Castle. Until recently, your relative had irregularly
visited the castle, so it is even inhabitable! In order to discourage burglars
from steeling the antiques, all the heavy oak doors inside are locked with
those huge, uncrackable medieval locks, the keys weighing a pound each.

Moreover, these keys are not stored in a
central place, but deposited inside other rooms. Your ancestor left you a list
of rooms, stating which key he deposited inside that room.

The letter containing the list also contained the
suggestion to sleep in Lady Olwyn's gallery, because there you would find a bed
set up and further instructions. And you were asked to pick up the Hall key
from the Vicar in St. Gwyneth's and advised to lock the castlle the same way
when you leave
.

The best thing you can do in preparation of
your first visit, is to write a program that teaches you the best path to Lady
Olwyn's gallery and any other rooms that might be named in the instructions
deposited there.

Your program will consist of two parts: Part one transforms the room list provided as download into a adjacency matrix. Part two determines the (hopefully shortest) path from the hall to a given room using the adjacency matrix.

To help you
get started, you are invited to set up a prototype of your program, using the
java.util.HashMap for the name-to-number mapping, an off-the-shelf CSV reader
for reading the room list, and the simplistic
static method getPath() from the class GraphUtilities, which finds a path in
most cases, but not necessarily the shortest one.

*Prototype Setup:*

**Reading the Room List:
**

1.
Download the file gwynethUtilities.jar
which contains the necessary resources.

2.
Have a look at the room list, called
gwynethAccessPlan.txt: It is a CSV file with commas as separators. *The first
record contains the maximum number of rooms listed*. All successive records
are pairs of room names, separated by a comma, indicating that the first room
contains the key to the second. E.g.

*Viscountess Lleucus' Private Chamber,
Archduke Llywellyn's Armoury
*means that Viscountess Lleucus'
Private Chamber contains the key to Archduke Llywellyn's Armoury.

So you need a little utility for reading a CSV (comma separated values) file: Write your own CSV reader class, using either java's StringTokenizer class, or a download and use a CSV reader from the internet, e.g. from the Apache CSV page (I suggest open CSV) or JavaCSV . All you need, are methods to read a new line, and to get the first and the second csv value from the line, as each line contains a pair of rooms..

3. First, test your CSV reader on a simple file containing lines like "A, BB", "CCC, D", etc. Then test it on the room list: Copy it to System.out, adding comments ike "the number of rooms is" and "contains the key for".

**Mapping the Node Names to Numbers:
**

**4.
**When working with graphs, nodes
are internally encoded as successive numbers so that they can be used as
indeces into an adjacency matrix. In your Castle class, establish this private
encoding it should be kept as secret in side the class. Every room in the room list has to be mapped to a number using
a java.util.HashMap: If the name is not yet contained in the HashMap, append it
to a names array, regard the index as internal node encoding, and add the pair (name,
index) to the HashMap. Notice that the name is the key, not the index. The
HashMap will be used for quick translation *from name to number*, the
array for a fast backward translation *from number to name*.

- Admittedly, for a node list of less
than 50 nodes, you don't really need a HashMap, but you need it for practice ;)

** **

**Setting Up the Castle Access Graph:**

** **

- Let your Castle class implement
the Graph interface below. For simplicity, define a constructor which
receives the maximum number of vertices as parameter. That allows you to
define the adjacency matrix immediately, without counting the vertices
first.

**public interface Graph {**** **

**
**

** public void addVertex(String
label)throws ContainedException; **

**
public void addEdge(String src, String dest) throws
NotContainedException; **

** **

**
/* methods for graph usage */**

** **

** public int getDistance(String src,
String dest) throws NoPathException, NotContainedException;**

**public String[] getPath(String src, String dest)
throws NoPathException, NotContainedException; **

** **

- Define the adjacency matrix as a two-dimensional int array, with
its size determined by the number
of rooms. Using int instead of boolean simplifies distance
calculations.

- Implement the graph setup methods, using the encoding mechanism
from step 4.

8.
In the constructor, read the room list,
and add all rooms edges to your graph.

9.
As
test cases, create some files describing simpler graphs, and write corresponding Junit tests. Also,
print out the HashTable and the adjacency matrix *and check them by hand. *

**Finding the Shortest Paths:
**

10. For a prototype implementation, use the static method int[] getPath (in class GraphUtilities) to implement the method String[] getPath. This may not yield the shortest path, but for the prototype, it will do. You will need to translate numbers back to room names using the room. The provided method has the following signature:

static int[] getPath(int from, int to,
int[][] adjacency);

Adding a User Interface:

11. Now surround this with an interaction interface, graphical or not,
which asks the user for a room and tells him how to get there **from the hall.**

* *

*Refinements:*

*One refinement is required free choice. The other one is
optional work!
*

12. **HashMap:**

Replace the java.util.HashMap by your own implementation. Describe and document
the has clash resolution technique you chose and of course run Junit tests
on it.

13. **Dijkstra's Algorithm:**

Implement Dijkstra's Shortest Paths algorithm with the entrance hall as
starting node, and use its results instead of the prototype method getPath().
You will need two extra matrices, one as distance matrix, which is going to
contain, for every pair of nodes, their shortest distance. Initially, it is a
copy of the adjacency matrix. The second matrix is a path matrix which you need
to "remember" which was the shortest path: For each pair of nodes, it
contains the first intermediate node on the shortest path between them. The
idea is that at the first call of getPath, you run Dijkstra's algorithm and
then read the answer from the path matrix.

*Hint: If you implement the algorithm as a
static method taking two matrices as parameters, you can easily exchange your
algorithms with fellow students. Just use a signature like **static
int[] getPath(int[][] dist, int[][] path); but bear in
mind that getPath might modify its parameters!*

* *

*Extra Work:*

*If you have done both refinements
and are still looking for a challenge:*

14. **Use open doors:**

After you have unlocked a door, the room is directly accessible from the hall
using the corridors. So, the next path might be considerably simpler! Take that
into account by adding direct edges between the hall and any room on your path,
when the user states that he has gone that path: add a method like
"explore", or "go" to your graph class. Afterwards, the
shortest paths need to be re-calculated.

15. **Optimisation?**

This changing graph is a special situation: Could you think of any simpler
solution than introducing these shortcut-edges
andsuccessive re-calculations?

16. **Lock it up again:**

You were strongly advised to lock the castle the same way as before when you
leave. Certainly, you want your program to help you with that! Can you
implement a technique that tells you which of the unlocked doors to lock in
which order and where to deposit the keys (so that you do not get stuck)?

** **

*Copyright note*

*Ilse Schmiedecke 2007/ 2009
for questions and comments: schmiedecke@tfh-berlin.de*