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