Need help with java assignment

Page 1 of 10 International Programmes Computing and related subjects

CO2226 Coursework assignment 2 2013-14

CO2226 Software engineering, algorithm design and analysis Coursework assignment 2, 2013–14

What to submit

There are 11 programs to be written for this assignment. These must be named Q1.java to Q11.java. You must also adapt the classes abstractGraph.java and arrayGraph.java below. You must submit a zip file containing these (at most) 13 Java files and (at most) 11 executable jar files: Q1.jar to Q11.jar. to allow the examiners to run the code with ease.

Most importantly, you must complete the ‘Answer sheet’ provided here, by copying and pasting the output of your programs into it. This must be submitted as a separate text file called YourName_SRN_CO2226_cw2answers.txt.

Marking scheme

Marks will be awarded on the basis of correct output, together with working, commented code.

Your marks will be based mainly on the correctness of your programs. The correctness of your programs will be judged by the correctness of their outputs, in other words by your answers in YourName_SRN_CO2226_cw2answers.txt. and by running your executable jar files.

You should fully test your programs to be sure that they are correct. One way to do this would be to make a very simple London Underground, by deleting lines from the edges file.

Another way is to test you programs on very simple cases that can be worked out manually, for example, the shortest routes between Baker Street and Oxford Circus. You need to convince yourself that your programs are correct by testing them in this way.

Background

There is a zip file containing the original programs you need called: ass26.zip.

Undirected graphs in Java

Below are two classes:

1. An abstract class abstractGraph which has a method shortestPaths which finds the set of all shortest paths (in terms of number of vertices) between any two vertices in the graph.

2. A non-abstract class arrayGraph, where the graph is represented as an adjacency matrix.

package graphs;

import java.util.Set;

import java.util.HashSet;

import java.util.ArrayList;

import java.util.TreeMap;

import java.util.PriorityQueue;

Page 2 of 10 International Programmes Computing and related subjects

CO2226 Coursework assignment 2 2013-14

public abstract class abstractGraph

{

public abstract HashSet <Integer> neighbours(Integer v);

// public abstract double weight (Integer v, Integer w);

// public abstract Set <Integer> vertices();

private boolean done;

//set to true if we find what we looking for or nothing left to find

private HashSet <Integer> alreadyVisited;

// the vertices visited altogether

private HashSet <Integer> newAlreadyVisited;

// the vertices visited at this level

private HashSet <ArrayList <Integer>> shortestPaths;

private double infinity=1000000.0;

ArrayList <Integer> addToEnd (Integer i, ArrayList <Integer> path)

// returns a new path with i at the end of path

{

ArrayList <Integer> k;

k=(ArrayList<Integer>)path.clone();

k.add(i);

return k;

}

HashSet <ArrayList <Integer>> nexts(ArrayList <Integer> path, Integer end)

/* given a path, finds all the paths that are one longer

can be made by adding a vertex

that hasn't already been visited at earlier levels */

{

Integer last=path.get(path.size()-1);

HashSet <ArrayList <Integer>> k= new HashSet <ArrayList <Integer>>();

Set <Integer> neighs=neighbours(last);

if (!neighs.contains(end))

{

for (Integer i:neighs) if (!alreadyVisited.contains(i))

k.add(addToEnd(i,path));

newAlreadyVisited.addAll(neighs);

}

else

{

done=true;

shortestPaths.add(addToEnd(end,path));

}

return k;

}

HashSet <ArrayList <Integer>> nexts(HashSet<ArrayList <Integer>> paths, Integer end)

/* applies nexts above to whole set of paths*/

{

HashSet <ArrayList <Integer>>k=new HashSet <ArrayList <Integer>>();

for (ArrayList <Integer> path:paths) k.addAll(nexts(path,end));

if (k.isEmpty()) done=true;

return k;

}

public HashSet <ArrayList <Integer>> shortestPaths( Integer start, Integer end)

{

shortestPaths=new HashSet <ArrayList <Integer>> ();

Page 3 of 10 International Programmes Computing and related subjects

CO2226 Coursework assignment 2 2013-14

alreadyVisited=new HashSet <Integer>();

newAlreadyVisited=new HashSet <Integer>();

done=false;

ArrayList <Integer> begin = new ArrayList <Integer>();

begin.add(start);

HashSet <ArrayList <Integer>> pathsSoFar=

new HashSet <ArrayList <Integer>>();

pathsSoFar.add(begin);

if (end==start) return pathsSoFar;

newAlreadyVisited.add(start);

while(!done) {

alreadyVisited.addAll(newAlreadyVisited);

pathsSoFar=nexts(pathsSoFar,end);

}

return shortestPaths;

}

And the following arrayGraph class:

package graphs;

import java.util.Set;

import java.util.HashSet;

import java.util.Map;

public class arrayGraph extends abstractGraph

{

double [][] adj;

public arrayGraph (double [][] ad)

{

adj=ad;

}

public HashSet <Integer> neighbours(Integer v)

{

HashSet k= new HashSet <Integer>();

for (int j=0;j<adj.length;j++) if (adj[v][j] > 0) k.add(j);

return k;

}

}

Page 4 of 10 International Programmes Computing and related subjects

CO2226 Coursework assignment 2 2013-14

The London Underground system (See The London Tube Map: http://www.tfl.gov.uk/assets/downloads/standard-tube-map.pdf)

Study the following files of data about the London Underground system:

 Some information about the stations: https://computing.elearning.london.ac.uk/mod/resource/view.php?id=2663

"id","latitude","longitude","name","display_name","zone","total_lines","rail"

Only the first four fields of every line will be used in this assignment. The last four are not needed.

 Some information about which stations are adjacent: edges https://computing.elearning.london.ac.uk/mod/resource/view.php?id=2662

"station1","station2","line"

Only the first two fields of every line will be used in this assignment. For example, the first line 11,163,1 means that station 11 (Baker Street) and 163 (Marylebone) are adjacent. (Ignore the 1!)

Page 5 of 10 International Programmes Computing and related subjects

CO2226 Coursework assignment 2 2013-14

(Note: These files are slightly out of date. Some of the latest stations on the map are not in the file. Please just use the files given.)

Representing the London Underground as a graph We can think of this being a graph, with the stations being vertices and the connections being the edges. Now consider the following program: import java.io.*;

import java.util.Scanner;

import java.util.*;

import graphs.*;

class underground

{

static int N= 308 ;

static double [][] edges = new double[N][N];

static String [] stationNames = new String[N];

static ArrayList<String> convert (ArrayList<Integer> m)

{

ArrayList<String> z= new ArrayList<String>();

for (Integer i:m) z.add(stationNames[i]);

return z;

}

static HashSet<ArrayList<String>> convert (HashSet<ArrayList<Integer>> paths)

{

HashSet <ArrayList <String>> k= new HashSet <ArrayList <String>>();

for (ArrayList <Integer> p:paths) k.add(convert(p));

return k;

}

public static void main(String[] args) throws Exception

{

for(int i=0;i<N;i++)for(int j=0;j<N;j++) edges[i][j]=0.0;

Scanner s = new Scanner(new FileReader("edges"));

String z =s.nextLine();

while (s.hasNext())

{

z =s.nextLine();

String[] results = z.split(",");

edges[Integer.parseInt(results[0])][Integer.parseInt(results[1])]=1.0;

edges[Integer.parseInt(results[1])][Integer.parseInt(results[0])]=1.0;

}

s = new Scanner(new FileReader("stations"));

z =s.nextLine();

while (s.hasNext())

{

z =s.nextLine();

String[] results = z.split(",");

stationNames[Integer.parseInt(results[0])]=results[3];

}

arrayGraph G= new arrayGraph (edges);

System.out.println(convert(G.shortestPaths(Integer.parseInt(args[0]),

Integer.parseInt(args[1]))));

}

}

Page 6 of 10 International Programmes Computing and related subjects

CO2226 Coursework assignment 2 2013-14

This program allows the user to enter two stations and the system finds all the shortest routes between the two stations in terms of number of stops. (To compile this make sure that the two graph classes above are in a directory called graphs immediately below the current directory.) Example output: java underground 5 87 [["Alperton", "Park Royal", "North Ealing", "Ealing Common", "Acton Town", "Turnham Green", "Hammersmith", "Barons Court", "Earl's Court", "Gloucester Road", "South Kensington", "Sloane Square", "Victoria", "Green Park", "Westminster", "Embankment"], ["Alperton", "Park Royal", "North Ealing", "Ealing Common", "Acton Town", "Turnham Green", "Hammersmith", "Barons Court", "Earl's Court", "Gloucester Road", "South Kensington", "Knightsbridge", "Hyde Park Corner", "Green Park", "Westminster", "Embankment"], ["Alperton", "Sudbury Town", "Sudbury Hill", "South Harrow", "Rayners Lane", "West Harrow", "Harrow-on-the-Hill", "Northwick Park", "Preston Road", "Wembley Park", "Finchley Road", "Baker Street", "Bond Street", "Green Park", "Westminster", "Embankment"], ["Alperton", "Park Royal", "North Ealing", "Ealing Common", "Acton Town", "Turnham Green", "Hammersmith", "Barons Court", "Earl's Court", "Gloucester Road", "South Kensington", "Sloane Square", "Victoria", "St. James's Park", "Westminster", "Embankment"]]

Q1. Write a program closeTunnel.java that allows us to close a tunnel connecting two stations of

our choice and then do the same as the previous program. The tunnel to close is that between the second (args[2]) and third (args[3]) command-line argument. For example, the following command

java closeTunnel 5 87 285 107

finds the shortest paths between Alperton and Embankment when the tunnel between Green Park and Westminster is closed:. [["Alperton", "Park Royal", "North Ealing", "Ealing Common", "Acton Town",

"Turnham Green", "Hammersmith", "Barons Court", "Earl's Court", "Gloucester

Road", "South Kensington", "Sloane Square", "Victoria", "St. James's Park",

"Westminster", "Embankment"]]

What is the correct output if you run: java closeTunnel 271 267 210 291

i.e. In other words the set of all shortest paths between Uxbridge and Upminster with the tunnel between Rayner's Lane and West Harrow closed? You must use the convert and shortestPaths methods to produce the output.

[10 marks]

Page 7 of 10 International Programmes Computing and related subjects

CO2226 Coursework assignment 2 2013-14

Adding weights (distances between adjacent vertices) to the graph

Adapt the abstractGraph and the arrayGraph classes above to handle edge weights. The weight of an edge is the distance between the nodes at each end of the edge.

Do this by adding an abstract method from edges to doubles in abstractGraph. public abstract double weight (Integer v, Integer w); this method will have to be implemented in arrayGraph.

Your adjacency matrix should now contain the weights of the edges and not 1.0 as in the previous example. We can still use 0.0 to mean there is no edge.

Use this method (taken from http://snipplr.com/view/25479/): for computing the distance between two points on the Earth's surface. You will have to look up the latitude and longitude of each station in the station file.

{

int R = 6371; // km (change this constant to get miles)

double dLat = (lat2-lat1) * Math.PI / 180;

double dLon = (lon2-lon1) * Math.PI / 180;

double a = Math.sin(dLat/2) * Math.sin(dLat/2) +

Math.cos(lat1 * Math.PI / 180 ) * Math.cos(lat2 * Math.PI / 180 ) *

Math.sin(dLon/2) * Math.sin(dLon/2);

double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));

double d = R * c;

return d;

}

So instead of

edges[Integer.parseInt(results[0])][Integer.parseInt(results[1])]=1.0;

edges[Integer.parseInt(results[1])][Integer.parseInt(results[0])]=1.0;

you will need something like

edges[Integer.parseInt(results[0])][Integer.parseInt(results[1])]=weight(Integer.parseI

nt(results[0]), Integer.parseInt(results[1]));

etc.

Q2. Write a program that allows us to find the distance between any two adjacent stations. Use your program to find the distance in metres between King’s Cross and Caledonian Road.

[5 marks]

Q3. What are the two adjacent stations that are furthest apart? Write a program which finds this out.

[5 marks]

Q4. Which two stations are closest? Write a program to work it out.

Page 8 of 10 International Programmes Computing and related subjects

CO2226 Coursework assignment 2 2013-14

[5 marks]

Q5. There is one station, S, such that the number of stations to the east of it is exactly one more than the number of stations to the west of it. Write a program to find the station S.

[5 marks]

Q6. There is one station, T, such that the number of stations to the north of it is exactly one more than the number of stations to the south of it. Write a program to find the station T.

[5 marks]

Q7. Adapt underground.java above to print out the lengths of the shortest routes between stations in kilometres (km). One possible way to go about this would be to add two public methods to abstractGraph class: public double pathWeight(ArrayList<Integer> path)

public HashSet <Double> pathWeights(HashSet <ArrayList<Integer>> paths)

To do this, in the main class distances.java we would add two new arrays:

static Double[] stationLat;

static Double[] stationLong;

for holding the latitude and longitude of each station. We would then get this information from the stations file (using the other components of the split (use Double.parseDouble on the 2nd and 3rd components of the split of each line)). We would then use the realDistance method above to calculate the entries for the adjacency matrix. We could use the old code from underground.java to print out the shortest paths. But then we would need to apply pathWeights (from the abstractGraph class) to get the lengths of each path in km. Example output: java distances 1 3 [["Acton Town", "Turnham Green", "Hammersmith", "Barons Court", "Earl's Court", "Gloucester Road", "South Kensington", "Knightsbridge", "Hyde Park Corner", "Green Park", "Westminster", "Waterloo", "Bank", "Liverpool Street", "Aldgate East"], ["Acton Town", "Turnham Green", "Hammersmith", "Barons Court", "Earl's Court", "Gloucester Road", "South Kensington", "Sloane Square", "Victoria", "Green Park", "Westminster", "Waterloo", "Bank", "Liverpool Street", "Aldgate East"], ["Acton Town", "Turnham Green", "Hammersmith", "Barons Court", "Earl's Court", "Gloucester Road", "South Kensington", "Sloane Square", "Victoria", "St. James's Park", "Westminster", "Waterloo", "Bank", "Liverpool Street", "Aldgate East"]] [15.946891989130329, 15.550901039305282, 16.62569743408007]

Page 9 of 10 International Programmes Computing and related subjects

CO2226 Coursework assignment 2 2013-14

Use your program distances.java to output the distances of all the shortest paths between Alperton and Embankment when the tunnel between Green Park and Westminster is closed. What is the output?

[10 marks]

Study Dijkstra's algorithm MIT Lecture 17 Video.

Here is an example of a pseudo-code for Dijkstra's Algorithm to find a shortest path from start to end:

Set S = {start};

Map <Integer,Double> Q = Map each Vertex to Infinity, except map start -> 0;

Map <Integer, ArrayList <Integer> > paths = Map each vertex to the empty path;

//paths.get(v) represents the current shortest path from start to v;

while (Q is not empty)

{

let v be the key of Q with the smallest value; //you should write a method Integer

findMin(TreeMap <Integer,Double> t) for this

if (v is end) return paths(end);

let w be the value of v in Q;

add v to S;

for (each neighbour u of v that is not in S) do

{

let w1 be the the weight of the (v,u) edge + w;

if w1 < the value of u in Q, then do the following:

{

update Q so now the value of u is w1

update paths(u) to be paths(v) with u stuck on the end

(remember to take a copy of paths v)

}

}

remove v from Q;

}

return [];

Add a method ArrayList <Integer> dijkstra(int start, int end) to the abstractGraph class for finding the path shortest distance between two vertices in a weighted graph. Use this to write a program similar to distance.java above, which finds the length of the shortest path in kilometres. Example output: java shortestDistancePath 5 67 ["Alperton", "Park Royal", "North Ealing", "Ealing Common", "Acton Town", "Turnham Green", "Hammersmith", "Barons Court", "Earl's Court", "Gloucester Road", "South Kensington", "Sloane Square", "Victoria", "St. James's Park", "Westminster", "Waterloo", "Bank", "Liverpool Street", "Aldgate East", "Whitechapel", "Stepney Green", "Mile End", "Bow Road", "Bromley-By-Bow", "West Ham", "Plaistow", "Upton Park", "East Ham", "Barking", "Upney", "Becontree", "Dagenham Heathway"] 36.11127254278942

Page 10 of 10 International Programmes Computing and related subjects

CO2226 Coursework assignment 2 2013-14

Q8. What is the shortest route between Uxbridge and Upminster and what is its length?

[15 marks]

Q9. What is the distance of the shortest path connecting the furthest apart two adjacent stations when the tunnel between them is closed? Write a program that outputs this. If it doesn't exist it should say no!

[10 marks]

Q10. What is the total length of all the tunnels in the system? Write a program which adds up

all the lengths of the edges in the graph.

[10 marks]

Q11. Every station has a computer. We want to connect the computers in a network so that every computer can be reached from every other computer. We want to put cables along the tube lines so that there is a path of cable connecting every computer to every other computer in the London underground system. Use Prim's algorithm (watch MIT Lecture Video on Greedy Algorithms ) to find out how much cable we need. You can base your code on the explanation in the video (it starts after about 1 hour). Do this by adding a method public double prim() to the abstractGraph() class. Again, use a Map <Integer,Double> Q for the priority queue and use your findMin() method for extracting the least. Pi ( ), in the video, can be represented as a TreeMap <Integer,Integer> pi.

How many kilometres of cable do we need?

[20 marks]