Please read/study and email me any comments/queries about any confusions or ambiguities and I'll fix things as appropriate - though note that the key task itself will not change, I'll just clarify the descriptions when really needed. Don't forget to also look at the help/FAQ file here: g52ads-0910-cw3-help.htm

G52ADS 2009-10: Coursework THREE.
"Shortest Paths with Wide Nodes"

DEADLINE: Friday Dec 11th 12:00
WEIGHT: This coursework will contribute 10% of the total module score.

Brief Description

This concerns finding shortest paths in (mostly undirected) graphs. The first part concern standard graphs with edges having a weight representing the distance, and you are asked to implement in Java an algorithm (Dijkstra's) to find arbitrary shortest paths, and also the diameter of the graph.

The diameter is simply the "longest 'shortest path' " - that is, the maximum over all pairs of nodes (A,B) of the distance of the shortest path between A and B. This might sound self-contradictory, but think of a "shortest path" as being a path that is always the shortest distance between its two endpoints - then the goal is to find the longest such path. Note that you are not allowed to make the path longer by making it take a very bad route between its two endpoints, as it would not then be a 'shortest path'. (Specifically, the diameter is NOT the longest path problem, which counter-intuitively is much much harder - all known algorithms take exponential time!).

The second part of the coursework requires you to also implement the case of "wide nodes" where using ("crossing") a node also incurs a distance. Motivation: Think of the case of a graph of connections between major cities - it makes sense that some time needs to be allowed for crossing the city, and not only for the edges (motorways) between the cities.

The last part is more advanced and essentially asks you to constructively criticese the defintions that I use for part 2.

You are will be given Java files with an interface that you must write class to implement (and without changing the supplied interface at all!). Your will also be provided with a format for simple text files describing the input graphs. After submission, your code will be compiled and run as part of a (hidden) test suite that we have. You should also test it yourself on various graphs and report on the design and efficiency of your code.

To do this coursework you will need a good understanding of Dijkstra's algorithm - or at least should have one by the time you are finished :-).

Part 1

Basic shortest paths ignoring the width of the nodes.That is with useNodeWidth=false. Also required to implement the calculation of graph diameter ignoring the width of the nodes.

Part 2

As part 1 but taking account of the width of the nodes. (That is with useNodeWidth=true). In this case, the distance, s(A,B), of a path from A to B should be taken to include the widths of the intermediate nodes, but not of the two end nodes. The shortest path probelm is to return the path that minimises this quantity. The diameter should be taken to be as before the maximum over all pairs of nodes (A,) of s(A,B). (For an example, see below).

Part 3

A discussion of whether the issues arising - such as whether the particular definitions, in the presence of wide nodes, of path lengths and diameter are reasonable or not.

Implementation Requirements

You are not allowed to use any code that does not come as part of the Java distribution

You are permitted freely use the Array and ArrayList etc.

You can, if you wish and think it appropriate use the other Java collection classes such as PriorityQueue. However, you could receive higher marks if you implement your own (better) version of such key data structures.

Report Requirements

For parts 1 and 2 you should:

• Briefly describe your implementation. This should be at a high-level, focussing on the data structures and algorithms. E.g. how did your store and access the open nodes, etc.
• Perform and report on some relevant experiments. E.g. so as to verify that the code works correctly, and also to obtain some idea of its efficiency, and how well it performs on large graphs. Also experiment and report on how the diameter increases with the size of the graph -- to support this, a graph generator you can use is here: RandomGraphGen.java : RandomGraphGen.class. Execute on the command line to obtain instructions on usage; and redirect output to a file to generate test files.

Part 3 is more open-ended and is a chance for people to note any interesting (and relevant!) observations or ideas that arose during the coursework. For example, are the 'wide nodes' a good idea for sat-navs, or should we stick with normal graphs, or do some other modification of graphs? It is a chance to demonstrate that you have fully absorbed the fundamental ideas of the C/W and can 'think out of the box' (i.e. add to C/W in some interesting fashion).

You are supplied with files here. This contains the three essential and "read-only" files:

• GraphIF.java. You are required to provide a class "Graph" that implements this interface as given.
• GraphException.java: Just defines the exceptions used by GraphIF.
• NodeList.java Defines a simple pair of an integer and an ArralyList. It is used by the interface in order to return answers.

• Graph.java. Gives an non-working example of an implementation of Graph - it compiles but all the implementations of the methods need to be fixed.
• Graph-fragment.java. Gives some (partial and sometimes incorrect) hints that might (or might not!) help you to implement Graph.java. Note the strong caveats at the head of the file! Do NOT assume that any if it is correct, but decide for yourself.
• TestHarness1.java Gives an example of how the Graph object might be created and used. YOUR CODE SHOULD COMPILE AND RUN WITH THIS AT LEAST.
• test.txt Gives an example of a input file describing a simple graph. The format of such data files is described below.

Input File Format

The input format is a simple space separated text file with each line containing information about a node or an edge. The meaining of a line depends on the single first character of the first field:

• 'n' means the line desribes a node (vertex) of the graph. The format is
  n nodeName width
  where the nodeName is a simple string (with no spaces) and the width is an integer
• 'u' the line describes an undirected edge. The format is
  u node1 node2 dist
  where node1 and node2 are strings representing the nodes, and the dist is an integer
• 'd' is a line representing a directed edge. The format is the same as for 'u' except it noew represents a directed edge from node1 to node2

You can assume that all the nodes (the 'n' lines) occur before all the edges (the u or d lines) -- but the u or d lines might occur in any order. (This is just to make the parsing easier -- you are given all the cities before the edges).

You can assume that the names of the nodes do not contain spaces or tabs - this is done so that splitting a line by whitespace is enough to extract the information.

Example: test.txt contains

n London 10
n Liverpool 5
n Birmingham 10
n Nottingham 3
u London Liverpool 100
u Liverpool Birmingham 60
u Birmingham Nottingham 40
u Nottingham London 90
d London Birmingham 60

Examples of paths:

• The shortest path from Liverpool to Nottingham is via Birmingham and so has distance 60+10+40=110. Where the 10 in the middle is to account for having to cross Birmingham, and note that the widths of the end nodes are not included. Note that the widths of the star ting and end nodes are not included in the overall distance. If useNodeWidths is false then the distance is just 60+40=100.
• The shortest path from Birmingham to London is via Nottimgham with distance 40+3+90 = 133.
• The diameter of this graph is 133

In reporting paths you should include both the starting and end nodes, even though their widths are not included in the calculation of the distance.

Submission Requirements

You need to submit (via the cw system and hardcopy) a report and your source code. The electronic report should either in word file format or PDF named g52ads-cw3.{docx,doc,pdf}. The code should be electronically submitted in a directory "src/". Also attach a hardcopy of your code to your report (DO NOT SUBMIT the interface files supplied, just the code that you wrote). Please print duplex! Please print your code in a relatively small font. This is to save paper, and to save me having to carry excessively large piles of paper :-) .

The total length of the report section (excluding copies of your code) must be no more than 6 pages..

HARDCOPY: Besides submitting the code and report electronically via the "cw" system, you MUST also submit a hardcopy of the report in the standard fashion (time-stamped with coversheet into the coursework letterbox).

Remark: The double submission system is to make sure that if one is somehow lost then the other will be present. It also gives me the option to check your code electronically, both to see it works and to check for plagiarism. As usual, you should be regularly copying all your work to the Unix servers (the H drive) as these are backed up. If you get a mark of zero and claim that your submission was lost, then I will be checking the cw system and (possibly) the backups; if it is not found on the cw/unix system then I will have no option but continue to treat it as not submitted.

Marking Scheme

The division of marks available between the two parts is simply:

• Part 1: (without the node widths). 70%
• Part 2: (with the node widths). 20%
• Part 3: Discussion. 10%

Marks will depend on the

• your code, using the usual criteria such as good style, reasonable efficiciency, correctness
• your report, in particular, the effectiveness and sensibleness of your experimental studies and the associated analyses

Late submissions allowed for up to a week after the deadline, but are penalised at standard University rate of 5% per day.

Plagiarism Policy

This coursework must be all your own work. You should remember that the coursework submissions will be archived, and plagiarism detection tools used. Plagiarism is a very serious offence! Read the University regulations. If at all in doubt about whether something is allowed, then consult me or your personal tutor.

Hints and Suggestions

I will maintain a help/FAQ file here: g52ads-0910-cw3-help.htm

Last updated: 08-Dec-2009
Contact: ajp 'at' cs.nott.ac.uk