Coursework 2 (20 marks) Introduction   This coursework builds on the first coursework, and requires you to add functionality to your solution to…

Coursework 2 (20 marks)

Introduction

 

This coursework builds on the first coursework, and requires you to add functionality to your solution to that coursework (or you can use the example solution to the first coursework if you like).

 

There are two things you have to do.

1) Find an efficient way of cabling together the stations.

Suppose that you have to run cables between the stations, in such a way that every station is connected, directly or indirectly, to every other station. The cables have to run along the routes between the stations. You are required to cable up the network in such a way as to minimise the length of cable used. The appendix explains how you can do this.

 

2) Find the shortest route between any two points. The completed program must allow the user to find the shortest route between any two points. You can use Dijkstra’s algorithm to do this (as set

out in lecture 5).

Functional Requirements

 

In addition to the functional requirements set out in the specification of

coursework, the new program must meet the following:

FR5

In addition to the elements set out in the previous specification, the

GUI should contain the following elements:

•  A drop down box, or a set of radio buttons, allowing the user to select one of three options labelled “Network”, “Span Tree”, and “Route”. We will refer to this as the Mode

Selector.

• Two drop down boxes, each of which lists the names of the stations in the network, and allows the user to select one of those names. We shall refer to these as the Start Station Selector  and the Destination Station Selector. 

FR6

If “Span Tree” is selected on the mode selector, and if a network has previously been read, then the graph area should be updated to display a network of cables that cables together the stations in the most efficient way.

FR7

If “Route” is selected on the mode selector, and if a network has previously been read, then the graph area should be updated to show a shortest route between the stations selected by the Start

Station Selector, and Destination Station Selector.

FR8

If “Network” is selected on the mode selector, and if a network has previously been read, then that network is displayed.

 

Non-functional Requirements

 

In addition to the non-functional requirements set out in the specification of coursework 1, your application should meet the following:

 

NFR4

Prim’s algorithm should be used to find a minimum spanning tree (see FR6).

NFR5

Dijkstra’s  algorithm should be used to find a shortest path between

two stations (FR7).

 

 

Some notes on implementation:

Some definitions of Dijkstra’s algorithm refer to a priority queue of vertices. It is therefore tempting to think that you can use the java class PriorityQueue in an implementation of the algorithm. However there is a catch: The Java PriorityQueue class does not allow the priority of elements to be changed after they have been added. There are ways around this, but it might be simplest not to use a PriorityQueue.

 

 If you are tempted to use a SortedSet implementation when implementing Prim’s algorithm, bear in mind that the Comparator used when creating a SortedSet must be consistent with the equals() method of the elements it contains. It might be easier to use a List implementation and sort it using the Collections.sort() method.

What you have to submit

 

You should submit two files:

1) A .zip file containing all of your code, preferably as a Netbeans project.

 

2) A .doc or .docx file containing a short reflection on the extent to which you feel that you have met the functional and non-functional requirements set out in this document.

Mark Scheme

For meeting FR5 2 marks

For meeting FR6 and NFR4 4 marks

For meeting FR7 and NFR5 4 marks

For meeting FR8 1 marks

For the quality of your code 7 marks

For the reflection on your degree of success2 marks

 

Appendix: Spanning trees and Prim’s algorithm 

If G is a graph then:

A subgraph of G is a graph, each of whose vertices belong to G, and each of whose edges belong to G. In other words it is a part of the graph G.

 

A spanning tree of G is a connected subgraph of G that is connected, contains all of the vertices of G and contains no cycles.

A minimum spanning tree of G is a spanning tree such that the total length of all the arcs that it contains is as small as possible. In other words there is no other spanning tree for G where the total length of the arcs is shorter.

A minimum spanning tree for G can be obtained by using Prim’s algorithm, which generates a minimum spanning tree T as follows.

1) Choose any vertex of the G and add it to T.

2) Look at all the edges in the G that connect a vertex that is in T to one that is not. Out of these edges, choose the shortest, and add it to T (if there is more than one edge that would count as shortest, then you can pick whichever you like).

3) Repeat step 2 until all of the vertices of G are also in T.