Informatik 2 – Schmiedecke

Lab X4 – Graph Algorithms: Gwyneth Castle

 

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.


This is a programming project –

            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

Hand in:  Link to report and source code with javadoc-documentation.
                  Demonstrate your solution in the lab!


 

Prep Questions:

 

  1. Explain the adjacency matrix and one other data structure for storing graphs.
  2. Why do graph implementations (normally) map the vertices of a graph to a uninterrupted sequence of node numbers?
  3. 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!

 

 

Introduction:

 

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.

 

Lab experiments:

 

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:

 

  1. 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 {             

                        /* methods for graph setup */          

             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;                 

        }

 

  1. 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.

  2. 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