CO2226: How Many Shortest paths exist Between the Playgrounds Ormeau Playground and Alexandra Playground: Software engineering, algorithm design and analysis, Singapore

Computing and Information Systems/Creative Computing

What to hand in Marks will be awarded for correct code (i.e. for code that produces results; if your code does not produce the correct result, no marks will be awarded for that part of the question).

You must submit one Java file called: Ass2226.java. For example, if your student number ID is 101031722, your file will be named: Ass2226101031722.java. When this file is compiled it must produce a file: Ass2226.class, e.g. Ass226101031722.class. When run, this must produce the answers to all the coursework assignment questions by implementing the appropriate algorithms.

Your java file may contain other classes, but they must all be included in the single java file; please do not submit multiple Java files as you will get a mark of zero – we only need one file. You must write your code assuming all data files are in the same directory as the program (and only use their names as arguments as shown in the example below).

 Failure to do this will lead to a mark of zero. If you cannot complete a particular question, the answer should say ‘NOT DONE’. Your program should take the text files described below as command-line arguments.

To run your program, the Examiners will type (pay attention that the filenames are referenced without the file extension):

 java Ass2226101031722 playgrounds playgrounds_lon_lat random graph

Your output should look like this:

Name: Joe

 Doe Student ID: 101031722

Question 1: 2

Question 2: 200 205

Question 3: 4

Question 4: 15

Question 5: [350, 352]

Question 6: 5.12

Question 7: 29.47

Execution Time: 32094 milliseconds

These are just sample answers to give you an idea of what output format is expected from your program. The examiners will change the data files to test your programs so make sure your program works with files containing fewer/more playgrounds or the existing playgrounds having different ids. Try deleting some lines from the files and see if your program gives different answers. You should use the code provided and build on that for answering the questions – no changes or alternative approaches are allowed in the logic of the code.

The efficiency of your program You will be penalized if your program runs too slowly (5 marks for every minute over 5 minutes on a machine with an Intel Core i7 vPro processor with 12 gigabytes of RAM).

Try to speed up your program by not re-computing values that you have already computed. Instead, store them (rather than re-computing) and identify opportunities and questions that will allow you to do so – then these values will be readily available to your program

Use System.nanoTime(); to time your program. Read the value at the beginning and end of your program and subtract and divide by a million to get the result expressed in seconds.

IF YOU DO NOT INCLUDE THE EXECUTION TIME OF YOUR PROGRAM YOU WILL SCORE ZERO.

IF YOU DO NOT USE THE DATA PROVIDED YOU WILL SCORE ZERO.

ALL SOLUTIONS SHOULD INVOLVE CALLS TO YOUR GRAPH INSTANCE METHODS; DO NOT TRY TO FIND ANSWERS ELSEWHERE.

Coursework assignment 2 – preparation and pre-assignment tasks

Finding the shortest paths in unweighted graphs (breadth-first search) Find out about Adjacency matrices for representing Graphs. Here is a program to help you become familiar with them:

import

java. util.HashSet;

import java.util.ArrayList;

public class graph

{

double [] [] adj;

graph (double [] [] a)

{

adj= new double [a.length][a.length];

for (int i=0;i<a.length;i++)

for (int j=0;j<a.length;j++)

adj[i][j]=a[i][j];

}

public HashSet <Integer> neighbours(int v)

{

HashSet <Integer> h = new HashSet <Integer> ();

for (int i=0;i<adj.length;i++)

if (adj[v][i]!=0)

h.add(i);

return h;

}

public HashSet <Integer> vertices()

{

3

HashSet <Integer> h = new HashSet <Integer>();

for (int i=0;i<adj.length;i++)

h.add(i);

return h;

}

ArrayList <Integer> addToEnd (int 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;

}

public HashSet <ArrayList <Integer>> shortestPaths1(HashSet

<ArrayList <Integer>> sofar, HashSet <Integer> visited, int end)

{

HashSet <ArrayList <Integer>> more = new HashSet <ArrayList

<Integer>>();

HashSet <ArrayList <Integer>> result = new HashSet <ArrayList

<Integer>>();

HashSet <Integer> newVisited = (HashSet <Integer>)

visited.clone();

boolean done = false;

boolean carryon = false;

for (ArrayList <Integer> p: sofar)

{

for (Integer z: neighbours(p.get(p.size()-1)))

{

if (!visited.contains(z))

{

carryon=true;

newVisited.add(z);

if (z==end) {

done=true;

result.add(addToEnd(z,p));

}

else

more.add(addToEnd(z,p));

}

}

}

if (done) return result; else

if (carryon)

return

shortestPaths1(more,newVisited,end);

else

return new HashSet <ArrayList <Integer>>();

}

4

public HashSet <ArrayList <Integer>> shortestPaths( int first,

int end)

{

HashSet <ArrayList <Integer>> sofar = new HashSet

<ArrayList<Integer>>();

HashSet <Integer> visited = new

HashSet<Integer>();

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

starting.add(first);

sofar.add(starting);

if (first==end)

return sofar;

visited.add(first);

return shortestPaths1(sofar,visited,end);

}

public static void main(String [] args)

{

double [ ] [] a = {

{0.0, 1.0, 1.0, 0.0},

{0.0, 0.0, 1.0, 1.0},

{0.0, 1.0, 0.0, 1.0},

{0.0, 1.0, 1.0, 0.0}

 };

graph g = new graph(a);

for (int i=0;i<a.length;i++)

{for (int j=0;j<a.length;j++)

if (i!=j) System.out.println(i + ” to ” + j +”: “+

g.shortestPaths(i,j));

}

}

}

Draw a picture of the graph and see if you agree with the output (please note that the

constructor assumes a non-directed graph; th

The Belfast Playgrounds Distance Problem Study the following files of data about bikes:

• playgrounds.csv. This file has two fields in the following order: id of the playground and the name of the playground 
• randomGraph.csv. This file contains three fields, the playground id of the source playground, the playground id of the destination playground and the cost for taking this route
• playgrounds_lon_lat.csv. This file has three fields in the following order: the playground id, the playground’s longitude and the playground’s latitude. Examine the following program

Examine the following program:

import java.io.*;

import java.util.Scanner;

import java.util.*;

class Assignment2

{

static int N= 500;

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

static TreeMap <Integer,String> playgroundNames = new

TreeMap

 <Integer,String>();

static ArrayList<String> convert (ArrayList<Integer>

m)

{

ArrayList<String> z= new

ArrayList<String>();

for (Integer i:m)

z.add(playgroundNames.get(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(“randomGraph”));

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(“playgrounds”));

z =s.nextLine();

while (s.hasNext())

{

z =s.nextLine();

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

playgroundNames.put(Integer.parseInt(results[0]),

Dijkstra’s algorithm (finding the shortest path in a weighted graph) 

Watch Dijkstra’s Algorithm (YouTube video) and Dijkstra’s Algorithm again! Study Dijkstra’s algorithm MIT Lecture 17 Video.

 Study the pseudo-code below for Dijkstra’s Algorithm to find the shortest path from Start to end graph nodes: 

Set S = {start}; 

//S is the set of vertices for which the shortest paths from start have already been found 

HashMap Q = Map each Vertex to Infinity (Double.POSITIVE_INFINITY), 

except map start -> 0;

 // Q.get(i) represents the shortest distance found from start to i found so far

 ArrayList [] paths; For each i 

set path[i] to be the path just containing start. while (Q is not empty)

 { let v be the key of Q with the smallest value; //I’ve given you a method int find the smallest(HashMap t) for this

 if (v is the end and Q does not map v to infinity) return paths[end]; let w be the value of v in Q; add v to S;

 for (each neighbor u of v)  do 

{

 if (u not in S) 

{ 

let w1 be 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

Task 1 Implement Dijkstra’s Algorithm using the pseudo-code above; 

namely, put a function 

Dijkstra into the graph class

Here are some hints: 

int find smallest(HashMap t) 

{

 Object [] things= t.keySet().toArray(); 

double val=t.get(things[0]); int least=(int) things[0]; 

Set k = t.keySet(); for (Integer i : k)

 {

 if (t.get(i) < val) { least=i; val=t.get(i); } } return least

Task 2 Test your implementation using the following test program (again, you would need to provide the ids of the start and end node as part of the program arguments which is not needed for your final program).

class testDijk

{

public static void main(String [] args) throws

Exception

{

int N=1000;

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

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(“randomGraph”));

String z;

z =s.nextLine();

while (s.hasNext())

{

z =s.nextLine();

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

edges[Integer.parseInt(results[0])]

[Integer.parseInt(results[1])]=Double.parseDoubl

e(results[2]);

}

graph G= new graph (edges);

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

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

}

}

Coursework assignment 2 – questions Please note that playgrounds in the questions are referred to by their name. As part of the assignment, you will need to resolve them into their ids (for example, 12 for Lemberg Street Playground). IMPORTANT: in the case of a direct link, please ignore this option and look for a route that includes at least one extra link; this constraint applies to all questions for this coursework assignment.

1. How many shortest paths exist between the playgrounds Ormeau Playground and Alexandra Playground? The shortest path here means a path with a minimal number of vertices. (Note: Use the shortest paths method above.

2. Which pair of playgrounds have the highest number of shortest paths between them? Just give the playground ids (in the case of more than one pair having the same numbers of shortest paths we need all pairs). It does not matter how the pairs are presented in your answer

3. How many shortest paths do(es) this(these) pair(s) have?

4. How long are each of these shortest paths?

Hint: You may wish to use the following method:

static ArrayList first element (HashSet > s)

{ return ( ArrayList)s.toArray()[0];

}

5. Which set of playgrounds is furthest away from the Balfour Avenue Playground in terms of the number of stops? (Just print out the set of ids corresponding to the playgrounds – again in the case of a tie we want the ids of all playgrounds matching

6.  What is the length in terms of some of the weights of the edges of the shortest path between Belfast Zoo Playground and Cave Hill Adventurous Playground? (Note: use Dijkstra’s Algorithm).

7. What is the length (in km) of the shortest path (in terms of distance) between Victoria Playground and Marrowbone Junior Playground? (Note: use Dijkstra’s Algorithm).

You will need to use the following method (and the relevant data from the playgrounds_lon_lat file).

static double realDistance(double lat1, double lon1, double lat2, double lon2)

{

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;

For finding the distance in km between any two points on the Earth’s surface with given latitude and longitude, the latitude and longitude of each playground are given in the playgrounds_lon_lat file. You will have to use this to compute the adjacency matrix for the weighted graph representation of the Belfast Playground problem. We need the ad[i][j] to be the distance from the playground I to playground j now.