In the main method of the NCCitiesRoads class

Create 6 City vertices and add them to an ArrayList using the details given below in the table

Create 18 Road edges between the cities and add them to an ArrayList using the details given below in the table.

Create a WeightedGraph with City vertices and Road edges.

Be sure to follow the constructors for the City, the Road, and the WeightedGraph classes when creating the objects.

Next, display each of the items requested below:

The number of Cities in the map.

The City object information for the 4th City added, using a graph method to retrieve the City.

The City with the largest number of Roads ending there.

The Road edge information for each Road using a graph method.

The complete Road information for each Road from the Road ArrayList. Cast the WeightedEdge to a Road object.

Provide an additional ArrayList with the Cities sorted and print it Use the Collections.sort method.

public class NCCitiesRoads { /** * For this program: * 1. Create the City and Road ArrayLists * 2. Add 6 City objects to the City Vertex ArrayList. * 3. Add 18 Road objects to the Road Edge ArrayList. * 4. Create a WeightedGraph passing in the * City and Road ArrayLists. * 5. Next, display each of the items requested below: * (look at the Graph/WeightedGraph methods) * a. The number of Cities in the map. * b. The City object information for the 4th City * added, using a graph method to retrieve the City. * c. The City with the largest number of Roads ending there. * d. The Road edge information for each Road using a * graph method. * e. The complete Road information for each Road from the * Road ArrayList. Cast the WeightedEdge from the * ArrayList to a Road object * f. Provide an ArrayList with the Cities sorted * and print it - (use Collections.sort) */

public static void main (String[] args) { // Create an ArrayList called cities of City objects ArrayList cities = new ArrayList();

// Create an ArrayList called roads of WeightedEdge Road objects ArrayList roads = new ArrayList();

// Create 6 Cities

City city0 = new City ("Murphy", -84.029924, 35.089848, 1627, 0); City city1 = new City ("Mars Hill", -82.547843, 35.828496, 1869, 1); City city2 = new City ("Mooresville", -80.820139, 35.584337, 32711, 2); City city3 = new City ("Morrisville", -78.828930, 35.827493, 18576, 3); City city4 = new City ("Morehead City", -76.746748, 34.727700, 8661, 4); City city5 = new City ("Manteo", -75.669385, 35.904595, 1434, 5);

// Add them to ArrayList

cities.add (city0); cities.add (city1); cities.add(city2); cities.add(city3); cities.add(city4); cities.add(city5); // Create 18 roads and add them to ArrayList

roads.add (new Road (city0, city1)); roads.add (new Road (city0, city2)); roads.add (new Road (city1, city0)); roads.add (new Road (city1, city2)); roads.add (new Road (city1, city3)); roads.add (new Road (city2, city0)); roads.add (new Road (city2, city1)); roads.add (new Road (city2, city3)); roads.add (new Road (city2, city4)); roads.add (new Road (city3, city1)); roads.add (new Road (city3, city2)); roads.add (new Road (city3, city4)); roads.add (new Road (city3, city5)); roads.add (new Road (city4, city2)); roads.add (new Road (city4, city3)); roads.add (new Road (city4, city5)); roads.add (new Road (city5, city3)); roads.add (new Road (city5, city4));

// Create Weighted Graph

// The number of cities in the map.

// The City object information for the 4th City added, // using a graph method to retrieve the City.

// The City with the largest number of Roads ending there. // This requires you to loop thru arraylist

// The Road edge information for each Road using a graph method.

// The complete Road information for each Road from the Road ArrayList. // Cast the WeightedEdge from the ArrayList to a Road object // This requires you to loop thru arraylist // Provide an additional ArrayList with the Cities sorted and print it // (use Collections.sort) // This requires you to loop thru arraylist to create new arraylist

}

......................................................................

public class City implements Comparable { private String city; // City name private double gpsX; // Longitide in degrees private double gpsY; // Latitide in degrees private int population; // Population size private int vertIndex; // index in the Vertex ArrayList

/** Construct a City object and initialize the instance variables */

public City (String name, double x, double y, int size, int index) { city=name; gpsX=x; gpsY=y; population=size; vertIndex=index; }

/** Return the City name */

public String getCity() { return city; }

/** Return the City longitude */

public double getLongitude() { return gpsX; }

/** Return the City latitude */

public double getLatitude() { return gpsY; }

/** Return the City poulation */

public int getPopulation() { return population; }

/** Return the City index in the vertex ArrayList */

public int getIndex() { return vertIndex; }

/** Set the City index of the vertex ArrayList */

public void setIndex (int index) { vertIndex=index; }

/** Compare the City poulations */

@Override public int compareTo (City c) { return Integer.compare(population, c.population); }

/** Return true, when the City names are the same */

@Override public boolean equals (Object c) { return city.equals(((City)c).city); }

/** * Return the City info as a String * Example: Mars Hill: [1]:[82.55 W, 35.83 N]:(1869) * Round the GPS coordinates to 2 decimal places for display */

public String printCity() { return String.format("%s: [%d]:[%.2f W, %.2f N]:(%d)", city, vertIndex, gpsX, gpsY, population); }

/** Return the City name as a String */

public String toString() { return city; } }

.......................................................................................

public class Road extends WeightedEdge implements Comparable { private City startCity; // The city at the start of the road private City endCity; // The city at the end of the road private double distance; // The distance in miles from startCity to endCity private String direction; // The direction of travel on the road // from startCity to endCity

/** Construct a Road object and initialize all the instance variables */

public Road (City c1, City c2) { // Pass the indices of the vertices from the // Vertex List to the grandparent Edge super (c1.getIndex(), c2.getIndex(), 0);

// Initialize the endpoint cities

// add code here

// Calling this method computes the direction of the Road // object and the distance between the City vertices and // sets the corresponding instance variables and the // weight instance variable of the parent WeightedEdge computeDirection(); }

/** Return the distance */

public double getDistance() { return distance; }

/** Return the direction */

public String getDirection() { return direction; }

/** Compare two Road edges by their weights */

public int compareTo (Road edge) { // add code here }

/** * Calling computeDirection computes the direction of the Road * object and the distance between the City vertices and * sets the corresponding instance variables: * distance * weight * direction * * Note: Do NOT round any values (especially GPS) in this method * we want them to have their max precision. * Only do rounding when displaying values * */

private void computeDirection() { // Convert the startCity (PointA) and endCity (PointB) // GPS coordinates from degrees into radians

// Point A: (x1, y1): startCity double x1 = Math.toRadians (startCity.getLongitude()); double y1 = Math.toRadians (startCity.getLatitude());

// Point B: (x2, y2): endCity double x2 = Math.toRadians (endCity.getLongitude()); double y2 = Math.toRadians (endCity.getLatitude());

// Find quadrant int quad = findQuadrant (x1, y1, x2, y2);

// Uses quadrant the determine coordinates of Point C: (x3, y3) // These are for Quad 2 or Quad 4 double x3 = x1; double y3 = y2;

if (quad == 1 || quad == 3) { // These are for Quad 1 or Quad 4 x3 = x2; y3 = y1; }

// Compute length of sides a, b, and c which are across // from points (and angles) A, B and C, respectively

double sideA = distance (x2, y2, x3, y3); double sideB = distance (x1, y1, x3, y3); double sideC = distance (x1, y1, x2, y2);

// Compute the angle at pointA in degrees. // The order of these three sides is important: // sideA: across from angle A - the direction being calculated // sideB: across from angle B // sideC: across from angle C which is the right angle // and the side that is the path from PointA (x1, y1) // to PointB (x2, y2)

double angleA = compAngle (sideA, sideB, sideC);

// Set distance, weight and direction // Note: Dont round anything here, we want max precision

// Convert the sideC length (distance from PtA to PtB) into miles distance = sideC * 3956;

// The distance is also the weight weight = distance;

// Use angleA and the quadrant to find // the direction of travel from PointA to PointB direction = compDirection (angleA, quad); }

/** * Assuming that PointA (x1, y1) is at the origin, * Find the Quadrant containing PointB (x2, y2) * This is accomplished by comparing both x1 to x2 and y1 to y2 */

private int findQuadrant (double x1, double y1, double x2, double y2) { int quad = 0; if (x1 < x2 && y1 <= y2) { quad = 1; } else if (x1 >= x2 && y1 < y2) { quad = 2; } else if (x1 > x2 && y1 >= y2) { quad = 3; } else if (x1 <= x2 && y1 > y2) { quad = 4; } return quad; }

/** * Compute the distance between PointA (x1,y1) and PointB (x2,y2) * Return the distance rounded to two decimal places */

private double distance (double x1, double y1, double x2, double y2) { return Math.sqrt ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)); }

/** Compute AngleA at PointA from the sides of the triangle */

private double compAngle (double sideA, double sideB, double sideC) { return Math.toDegrees (Math.acos(((sideB * sideB) + (sideC * sideC) - (sideA * sideA)) / (2 * sideB * sideC))); }

/** * Compute the direction of the line between PointA to PointB, * Using the angle at PointA and the quadrant PointA is in */

private String compDirection (double angle, int quadrant) { String dirStr = "None";

switch (quadrant) { case 1: { if (angle <= 11.25) { dirStr = "E"; } else if (angle <= 33.75) { dirStr = "ENE"; } else if (angle <= 56.25) { dirStr = "NE"; } else if (angle <= 78.75) { dirStr = "NNE"; } else // angle 78.75 -> 90 { dirStr = "N"; } break; } case 2: { if (angle <= 11.25) { dirStr = "N"; } else if (angle <= 33.75) { dirStr = "NNW"; } else if (angle <= 56.25) { dirStr = "NW"; } else if (angle <= 78.75) { dirStr = "WNW"; } else // angle 78.75 -> 90 { dirStr = "W"; } break; } case 3: { if (angle <= 11.25) { dirStr = "W"; } else if (angle <= 33.75) { dirStr = "WSW"; } else if (angle <= 56.25) { dirStr = "SW"; } else if (angle <= 78.75) { dirStr = "SSW"; } else // angle 78.75 -> 90 { dirStr = "S"; } break; } case 4: { if (angle <= 11.25) { dirStr = "S"; } else if (angle <= 33.75) { dirStr = "SSE"; } else if (angle <= 56.25) { dirStr = "SE"; } else if (angle <= 78.75) { dirStr = "ESE"; } else // angle 78.75 -> 90 { dirStr = "E"; } break; } } return dirStr; }

/** * Return the Road info as a String: * Round distance to 2 places for display. * "Barco to Elizabeth City traveling WSW for 17.41 miles" */

public String printRoad() { // code this as above }

/** * Return the Road info as a String containing City names * Road: Charlotte to Greensboro */

public String toString() { // code this as above } }

...............................................................................................................

public class WeightedEdge extends AbstractGraph.Edge implements Comparable { public double weight; // The weight on edge (u, v)

/** Create a weighted edge on (u, v) */

public WeightedEdge (int u, int v, double weight) { // Pass the indices of the vertices from the // Vertex List to the parent Edge super (u, v);

this.weight = weight; }

/** Compare two edges on weights */

public int compareTo (WeightedEdge edge) { if (weight > edge.weight) { return 1; } else if (weight == edge.weight) { return 0; } else { return -1; } }

/** Create a String version of the WeightedEdge */ @Override public String toString () { return /*super.toString + */ " wt = " + weight; } }

......................................................................................................

import java.util.*; @SuppressWarnings("unchecked") public class WeightedGraph extends AbstractGraph { /** Construct an empty graph */

public WeightedGraph() { }

/** * Construct a WeightedGraph from vertex array * and edges stored in an adjacency matrix */

public WeightedGraph(V[] vertices, int[][] edges) { createWeightedGraph (java.util.Arrays.asList (vertices), edges); }

/** * Construct a WeightedGraph from Integer vertices * and edges stored in an adjacency matrix */

public WeightedGraph (int[][] edges, int numVertices) { List vertices = new ArrayList<>(); for (int i = 0; i < numVertices; i++) { vertices.add ((V)(new Integer (i))); } createWeightedGraph (vertices, edges); }

/** Construct a WeightedGraph vertices and edges stored in lists */

public WeightedGraph (List vertices, List edges) { createWeightedGraph (vertices, edges); }

/** Construct a WeightedGraph from Integer vertices and edge list */

public WeightedGraph (List edges, int numVertices) { List vertices = new ArrayList<>(); for (int i = 0; i < numVertices; i++) { vertices.add ((V)(new Integer (i))); }

createWeightedGraph (vertices, edges); }

/** * Create an edge adjacency list for each vertex * from edges stored in an adjacency matrix */

private void createWeightedGraph (List vertices, int[][] edges) { this.vertices = vertices;

for (int i = 0; i < vertices.size(); i++) { // Create a list for vertices neighbors.add (new ArrayList()); }

for (int i = 0; i < edges.length; i++) { neighbors.get (edges[i][0]).add (new WeightedEdge (edges[i][0], edges[i][1], edges[i][2])); } }

/** * Create an edge adjacency list for each vertex in * the vertex list from edges stored in a list */

private void createWeightedGraph (List vertices, List edges) { this.vertices = vertices;

for (int i = 0; i < vertices.size(); i++) { // Create a list for vertices neighbors.add (new ArrayList()); }

for (WeightedEdge edge: edges) { // Add an edge into the list neighbors.get (edge.u).add (edge); } }

/** Return the weight on the edge (u, v) */

public double getWeight (int u, int v) throws Exception { for (Edge edge : neighbors.get (u)) { if (edge.v == v) { return( (WeightedEdge) edge).weight; } }

throw new Exception ("Edge does not exit"); }

/** Display edges with weights */

public void printWeightedEdges() { for (int i = 0; i < getSize(); i++) { System.out.print (getVertex(i) + " (" + i + "): ");

for (Edge edge : neighbors.get (i)) { double wt = ((WeightedEdge)edge).weight; System.out.print ("(" + edge.u + ", " + edge.v + ", " + Math.round(wt*100)/100.0 + ") "); }

System.out.println(); } }

/** Add the edge to the weighted graph */

public boolean addEdge (int u, int v, double weight) { return addEdge (new WeightedEdge (u, v, weight)); }

/** Get a minimum spanning tree rooted at vertex 0 */

public MST getMinimumSpanningTree() { return getMinimumSpanningTree (0); }

/** Get a minimum spanning tree rooted at a specified vertex */

public MST getMinimumSpanningTree (int startingVertex) { // The array element cost[v] stores the cost by adding v to the tree

double[] cost = new double[getSize()];

for (int i = 0; i < cost.length; i++) { cost[i] = Double.POSITIVE_INFINITY; // Initial cost }

cost[startingVertex] = 0; // Cost of source is 0

// Parent of a vertex int[] parent = new int[getSize()];

// StartingVertex is the root parent[startingVertex] = -1;

// Total weight of the tree thus far double totalWeight = 0;

// T stores the vertices in MST found so far List T = new ArrayList<>();

// Expand T until it has all the vertices while (T.size() < getSize()) { // Vertex to be determined int u = -1; double currentMinCost = Double.POSITIVE_INFINITY;

// Loop to find smallest cost v in set V-T for (int i = 0; i < getSize(); i++) { if (!T.contains(i) && cost[i] < currentMinCost) { currentMinCost = cost[i]; u = i; } }

// Add a new vertex to T and the cost to the total weight T.add (u); totalWeight += cost[u];

// Adjust cost[v] for each v that is adjacent to u using // the weight of the edge (u,v) when v is still in in V-T for (Edge e : neighbors.get (u)) { if (!T.contains(e.v) && cost[e.v] > ((WeightedEdge)e).weight) { cost[e.v] = ((WeightedEdge)e).weight; parent[e.v] = u; } } } // End of while

return new MST (startingVertex, parent, T, totalWeight); }

/** MST is an inner class in WeightedGraph */

public class MST extends Tree { // Total weight of all edges in the tree private double totalWeight;

// Constructor updates parent Tree and sets weight public MST (int root, int[] parent, List searchOrder, double totalWeight) { super (root, parent, searchOrder); this.totalWeight = totalWeight; }

//Return weight of MST public double getTotalWeight() { return totalWeight; } }

/** Find single source shortest paths */

public ShortestPathTree getShortestPath (int sourceVertex) { // cost[v] stores the cost of the path from v to the source double[] cost = new double[getSize()];

// Initial cost for each vertice is set to infinity for (int i = 0; i < cost.length; i++) { cost[i] = Double.POSITIVE_INFINITY; }

// Cost of source is 0 cost[sourceVertex] = 0;

// parent[v] stores the previous vertex of v in the path int[] parent = new int[getSize()];

// The parent of source is set to -1 parent[sourceVertex] = -1;

// T stores the vertices whose path found so far List T = new ArrayList<>();

// Expand T while (T.size() < getSize()) { // Vertex to be determined int u = -1; double currentMinCost = Double.POSITIVE_INFINITY;

// Loop to find smallest cost v in set V-T for (int i = 0; i < getSize(); i++) { if (!T.contains(i) && cost[i] < currentMinCost) { currentMinCost = cost[i]; u = i; } }

// Add a new vertex to T T.add (u);

// Adjust cost[v] for v that is adjacent to u // and v still in set V-T for (Edge e : neighbors.get (u)) { if (!T.contains(e.v) && cost[e.v] > cost[u] + ((WeightedEdge)e).weight) { cost[e.v] = cost[u] + ((WeightedEdge)e).weight; parent[e.v] = u; } } } // End of while

// Create a ShortestPathTree return new ShortestPathTree (sourceVertex, parent, T, cost); }

/** ShortestPathTree is an inner class in WeightedGraph */ public class ShortestPathTree extends Tree { private double[] cost; // cost[v] is the cost from v to source

/** Construct a path */

public ShortestPathTree (int source, int[] parent, List searchOrder, double[] cost) { super (source, parent, searchOrder); this.cost = cost; }

/** Return the cost for a path from the root to vertex v */

public double getCost (int v) { return cost[v]; }

/** Print paths from all vertices to the source */

public String printAllPaths() { String str = ""; str += "All shortest paths from " + vertices.get (getRoot()) + " are: ";

for (int i = 0; i < cost.length; i++) { // Print a path from vertex i to the source str += printPath (i); str += " (cost: " + Math.round(cost[i]*100)/100.0 + ") "; // Path cost }

return str; } } }