I need help with this Java program, Class specifications: Table 1: City Class Cl
ID: 3701389 • Letter: I
Question
I need help with this Java program, Class specifications:
Table 1: City Class
Class City implements Comparable<City>
Private Instance Variables
Description
String city
City name
double gpsX
GPS Longitude in Decimal Degrees
double gpsY
GPS Latitude in Decimal Degrees
int population
Population
int vertIndex
Index in Vertex ArrayList
Public Instance Methods
Description
City (String name, double x,
double y, int size,
int index)
Constructor to initialize each instance variable. Do not round these numbers, here – do the rounding in printCity().
String getCity()
Getter for city
double getLongitude()
Getter for gpsX
double getLatitude()
Getter for gpsY
int getPopulation()
Getter for population
int getIndex()
Getter for vertIndex
void setIndex (int index)
Setter for vertIndex
int compareTo (City c)
Compares population
boolean equals (Object c)
Override equals comparing city name
String toString()
Return City name
String printCity()
Return City object information with the GPS coordinates rounded to 2 decimal places, as
Mars Hill: [1]:[-82.55, 35.83]:(1869)
Table 2: Road Class
Class Road extends WeightedEdge
implements Comparable< WeightedEdge>
Private Instance Vars
Description
City startCity
City at (x1, y1)
City endCity
City at (x2, y2)
double distance
Miles from startCity to endCity as crow flies
String direction
Map direction: N, S, E, W, etc
Public Instance Methods
Description
Road (City c1, City c2)
Constructor to initialize each instance variable:
double getDistance()
Getter for distance
String getDirection()
Getter for direction
int compareTo (Road r)
Compares distance between startCity and endCity; the weight
String toString()
String printRoad()
Return Road object information with the distance rounded to 2 decimal places
For example:
Gastonia to Hickory traveling N for 34.84 miles
Private Instance Methods
Description
int findQuadrant
(double x1, double y1,
double x2, double y2)
Return the quadrant in which the direction of travel takes you from PointA (x1,y1) (startCity) to PointB:(x2,y2) (endCity):
return 1, 2, 3, or 4
double compAngle
(double sideA,
double sideB,
double sideC)
double distance
(double x1, double y1, double x2, double y2)
Return the distance from (x1,y1) to (x2,y2)
DO NOT round the answer here
String compDirection
(double angle, int quad)
Return the direction of travel using angle and quadrant
void computeDirection
()
Called from the constructor; use all the other private instance methods and City instance variables to set the values of the the distance and direction instance variables for the Road object. You must start this function by changing the GPS coordinates to radians.
At the end of the method change the distance to miles before storing it. (multiply by 3956).
Table 3: City Information
City
Longitude
Latitude
Population
Murphy
-84.029924
35.089848
1627
Mars Hill
-82.547843
35.828496
1869
Mooresville
-80.820139
35.584337
32711
Morrisville
-78.828930
35.827493
18576
Morehead City
-76.746748
34.727700
8661
Manteo
-75.669385
35.904595
1434
Table 4: Road Information
City1
City2
City1
City2
0
Murphy
Mars Hill
3
Morrisville
Mars Hill
0
Murphy
Mooresville
3
Morrisville
Mooresville
1
Mars Hill
Murphy
3
Morrisville
Morehead City
1
Mars Hill
Mooresville
3
Morrisville
Manteo
1
Mars Hill
Morrisville
4
Morehead City
Mooresville
2
Mooresville
Murphy
4
Morehead City
Morrisville
2
Mooresville
Mars Hill
4
Morehead City
Manteo
2
Mooresville
Morrisville
5
Manteo
Morrisville
2
Mooresville
Morehead City
5
Manteo
Morehead City
Given Code:
City Class:
public class City implements Comparable<City>
{
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)
{
// add code
}
/** Return the City name */
public String getCity()
{
// add code
}
/** Return the City longitude */
public double getLongitude()
{
// add code
}
/** Return the City latitude */
public double getLatitude()
{
// add code
}
/** Return the City poulation */
public int getPopulation()
{
// add code
}
/** Return the City index in the vertex ArrayList */
public int getIndex()
{
// add code
}
/** Set the City index of the vertex ArrayList */
public void setIndex (int index)
{
// add code
}
/** Compare the City poulations */
@Override
public int compareTo (City c)
{
// add code
}
/** Return true, when the City names are the same */
@Override
public boolean equals (Object c)
{
// add code
}
/**
* 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()
{
// add code as above
}
/** Return the City name as a String */
public String toString()
{
// add code
}
}
NCCitiesRoads Class:
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
// Create an ArrayList called roads of WeightedEdge Road objects
// 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);
// Do the rest yourself
// Add them to ArrayList
cities.add (city0);
cities.add (city1);
// Do the rest yourself
// Create 18 roads and add them to ArrayList
roads.add (new Road (city0, city1));
// Do the rest yourself
// 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
}
}
Road Class:
public class Road extends WeightedEdge implements Comparable<WeightedEdge>
{
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()
{
// add code here
}
/** Return the direction */
public String getDirection()
{
// add code here
}
/** 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
}
}
Class City implements Comparable<City>
Private Instance Variables
Description
String city
City name
double gpsX
GPS Longitude in Decimal Degrees
double gpsY
GPS Latitude in Decimal Degrees
int population
Population
int vertIndex
Index in Vertex ArrayList
Public Instance Methods
Description
City (String name, double x,
double y, int size,
int index)
Constructor to initialize each instance variable. Do not round these numbers, here – do the rounding in printCity().
String getCity()
Getter for city
double getLongitude()
Getter for gpsX
double getLatitude()
Getter for gpsY
int getPopulation()
Getter for population
int getIndex()
Getter for vertIndex
void setIndex (int index)
Setter for vertIndex
int compareTo (City c)
Compares population
boolean equals (Object c)
Override equals comparing city name
String toString()
Return City name
String printCity()
Return City object information with the GPS coordinates rounded to 2 decimal places, as
Mars Hill: [1]:[-82.55, 35.83]:(1869)
Explanation / Answer
import java.io.File;
import java.io.PrintWriter;
import java.util.*;
public class NCCitiesRoads
{
private static final String COMMAND_FILE = "src//commands.txt";
private static final String OUTPUT_FILE = "src//NCRoutesOut.txt";
private static final String NCMAP_FILE = "src//NCRoadMap.csv";
private static final String NCCITIES_FILE = "src//NCCities.csv";
private static final String CITY_REC = "CITY";
private static final String ROAD_REC = "ROAD";
private static HashMap<String, Integer> cityMap = new HashMap<String, Integer>();
private static HashMap<String, Integer> citySubMap = new HashMap<String, Integer>();
private static CityRoadMap<City> roadMap = null; // full map, cities and roads
private static List<City> cities = new ArrayList<>(52);
private static List<WeightedEdge> roads = new ArrayList<>(204);
private static CityRoadMap<City> subRoadMap = null; // partial map
private static List<City> subCities = new ArrayList<>();
private static List<WeightedEdge> subRoads = new ArrayList<>();
public static void main (String[] args) throws Exception
{
File outFile = new File (OUTPUT_FILE);
PrintWriter writer = new PrintWriter (outFile);
File cmdFile = new File (COMMAND_FILE);
Scanner fin = new Scanner (cmdFile);
String cmdLine = null;
System.out.println ("Begin NC Routes Program ");
System.out.println ("Input: " + cmdFile.getAbsolutePath() + " ");
while (fin.hasNext())
{
cmdLine = fin.nextLine();
if (!cmdLine.isEmpty())
{
String cmdArray[] = cmdLine.split (":");
String result = processCmd (cmdArray);
writer.println (result);
System.out.println (result);
}
}
System.out.println (" End NC Routes Program ");
System.out.println (" Output: " + outFile.getAbsolutePath());
writer.close();
fin.close();
}
// Calls the appropriate method to process the command.
public static String processCmd (String[] cmdArray) throws Exception
{
String city = "";
String cmd = cmdArray[0].trim();
String result = "Command: " + cmd + " ";
if (cmd.equalsIgnoreCase ("BuildMap"))
{
result += buildMap() + " ";
}
else if (cmd.equalsIgnoreCase ("BuildSubMap"))
{
result += buildSubMap() + " ";
}
else if (cmd.equalsIgnoreCase ("PrintMap"))
{
result += roadMap.printRoads();
}
else if (cmd.equalsIgnoreCase ("PrintSubMap"))
{
result += subRoadMap.printRoads();
}
else if (cmd.equalsIgnoreCase ("PrintCities"))
{
result += roadMap.printCities() + " ";
}
else if (cmd.equalsIgnoreCase ("PrintSubCities"))
{
result += subRoadMap.printCities() + " ";
}
else if (cmd.equalsIgnoreCase ("DFSMap"))
{
city = cmdArray[1].trim();
result += dfs (roadMap, cityMap, city);
}
else if (cmd.equalsIgnoreCase ("DFSSubMap"))
{
city = cmdArray[1].trim();
result += dfs (subRoadMap, citySubMap, city);
}
else if (cmd.equalsIgnoreCase ("BFSMap"))
{
city = cmdArray[1].trim();
result += bfs (roadMap, cityMap, city);
}
else if (cmd.equalsIgnoreCase ("BFSSubMap"))
{
city = cmdArray[1].trim();
result += bfs (subRoadMap, citySubMap, city);
}
else if (cmd.equalsIgnoreCase ("MSTMap"))
{
result += mst (roadMap)+ " ";
}
else if (cmd.equalsIgnoreCase ("MSTSubMap"))
{
result += mst (subRoadMap)+ " ";
}
else if (cmd.equalsIgnoreCase ("ShortPathMap"))
{
city = cmdArray[1].trim();
result += shortestPath (roadMap, cityMap, city)+ " ";
}
else if (cmd.equalsIgnoreCase ("ShortPathSubMap"))
{
city = cmdArray[1].trim();
result += shortestPath (subRoadMap, citySubMap, city)+ " ";
}
else if (cmd.equalsIgnoreCase ("SortCities"))
{
result += sortCities (cities);
}
else
{
result += "Unknown command.";
}
return result;
}
// Builds CityRoadMap roadMap graph object from the CITY and ROAD records in a file
public static String buildMap() throws Exception
{
int cityIndex = 0;
int roadIndex = 0;
String result = "";
String line = "";
File mapFile = new File (NCMAP_FILE);
Scanner in = new Scanner (mapFile);
while (in.hasNext())
{
line = in.nextLine();
String fields[] = line.split (",");
String field1 = fields[0];
if (field1.equals (CITY_REC))
{
String name = fields[1].trim();
double lon = Double.parseDouble (fields[2].trim());
double lat = Double.parseDouble (fields[3].trim());
int population = Integer.parseInt (fields[4].trim());
cities.add (new City (name, lon, lat, population, cityIndex));
cityMap.put (name, cityIndex);
cityIndex++;
}
// If the first field says "ROAD", then create Road object
else if (field1.equals (ROAD_REC))
{
String startCityName = fields[1].trim();
String endCityName = fields[2].trim();
City startCity = cities.get (cityMap.get (startCityName));
City endCity = cities.get (cityMap.get (endCityName));
roads.add (new Road (startCity, endCity));
roadIndex++;
}
}
// Add the processing message to the String result to return
result += "Processed " + cityIndex + " Cities and " + roadIndex + " Roads";
// Close the Scanner
in.close();
// Build a roadMap CityRaodMap graph object of the cities and roads
roadMap = new CityRoadMap<City> (cities, roads);
return result;
}
// Build CityRoadMap subRoadMap graph object from the list of city names in a file
public static String buildSubMap() throws Exception
{
int cityIndex = 0;
int roadIndex = 0;
String result = ""; // Message about success
String line = ""; // For reading file record
File citiesFile = new File (NCCITIES_FILE);
Scanner sc = new Scanner (citiesFile);
// Reads each record in mapFile:
while (sc.hasNext())
{
line = sc.nextLine();
String cityName = line.trim();
int oldCityIndex = cityMap.get(cityName);
City currentCity = cities.get(oldCityIndex);
currentCity.setIndex(cityIndex);
subCities.add(cityIndex, currentCity);
citySubMap.put(cityName, cityIndex);
cityIndex++;
}
for (City city: subCities)
{
List<City> adjList = roadMap.getNeighbors(city);
for (City adjCity: adjList)
{
String adjCityName = adjCity.getCity();
if (citySubMap.containsKey(adjCityName))
{
int newCityIndex = citySubMap.get(adjCityName);
adjCity.setIndex(newCityIndex);
Road newRoad = new Road(city, adjCity);
subRoads.add(newRoad);
roadIndex++;
}
}
}
result += "Processed " + cityIndex + " Cities and " + roadIndex + " Roads";
sc.close();
subRoadMap = new CityRoadMap<City>(subCities, subRoads);
return result;
}
// Depth first search:
public static String dfs (CityRoadMap map, HashMap<String, Integer> indexMap,
String cityName) throws Exception
{
String result = "";
AbstractGraph<String>.Tree dfs = map.dfs (indexMap.get(cityName));
List<Integer> searchOrders = dfs.getSearchOrder();
result += dfs.getNumberOfVerticesFound() +
" cities are searched in this DFS order starting from " +
map.getVertex(searchOrders.get(0)) + " ";
for (int i = 0; i < searchOrders.size(); i++)
{
result += map.getVertex (searchOrders.get (i));
if ((i+1) % 5 == 0 || i == searchOrders.size() - 1)
{
result += ' ';
}
else
{
result += " : ";
}
}
result += " ";
// Loop through the parent array to display the parent of each City
for (int i = 0; i < searchOrders.size(); i++)
{
if (dfs.getParent (i) != -1)
{
result += "Parent of " + map.getVertex(i) +
" is " + map.getVertex(dfs.getParent(i)) + ' ';
}
}
return result;
}
//Breadth first search:
public static String bfs (CityRoadMap map, HashMap<String, Integer> indexMap,
String cityName) throws Exception
{
String result = "";
AbstractGraph<String>.Tree bfs = map.bfs (indexMap.get(cityName));
List<Integer> searchOrders = bfs.getSearchOrder();
result += bfs.getNumberOfVerticesFound() +
" cities are searched in this BFS order starting from " +
map.getVertex(searchOrders.get(0)) + " ";
for (int i = 0; i < searchOrders.size(); i++)
{
result += map.getVertex(searchOrders.get(i));
if ((i+1) % 5 == 0 || i == searchOrders.size() - 1)
{
result += ' ';
}
else
{
result += " : ";
}
}
result += " ";
// Loop through the parent array to display the parent of each City
for (int i = 0; i < searchOrders.size(); i++)
{
if (bfs.getParent(i) != -1)
{
result += "Parent of " + map.getVertex(i) +
" is " + map.getVertex(bfs.getParent(i)) + ' ';
}
}
return result;
}
// Minimum Spanning Tree:
public static String mst (CityRoadMap map) throws Exception
{
String result = "";
WeightedGraph<String>.MST tree1 = map.getMinimumSpanningTree();
result += "Total weight is " +
Math.round(tree1.getTotalWeight()* 100.0) / 100.0 + " " +
tree1.printTree();
return result;
}
// Shortest Path:
public static String shortestPath (CityRoadMap map, HashMap<String, Integer> indexMap, String fromCityName)
{
String result = "";
WeightedGraph<String>.ShortestPathTree tree1 =
map.getShortestPath(indexMap.get(fromCityName));
result = tree1.printAllPaths();
return result;
}
// Sorts the cities by population and displays them
public static String sortCities (List<City> sortCities)
{
String result = "";
Collections.sort(sortCities);
System.out.println("Cities sorted by size:");
for (int l = 0; l < sortCities.size(); l++)
{
result = result + sortCities.get(l).printCity() + " ";
}
return result;
}
}
-----------------------------------------------------------------------------
import java.util.*;
@SuppressWarnings("unchecked")
public abstract class AbstractGraph<V> implements Graph<V>
{
protected List<V> vertices = new ArrayList<>();
protected List<List<Edge>> neighbors = new ArrayList<>();
protected AbstractGraph()
{
}
protected AbstractGraph(V[] vertices, int[][] edges)
{
for (int i = 0; i < vertices.length; i++)
{
addVertex(vertices[i]);
}
createAdjacencyLists(edges, vertices.length);
}
// Construct a graph from vertices and edges stored in lists
protected AbstractGraph(List<V> vertices, List<Edge> edges)
{
for (int i = 0; i < vertices.size(); i++)
{
addVertex(vertices.get(i));
}
createAdjacencyLists(edges, vertices.size());
}
//Construct a graph from Integer vertices and edge list
protected AbstractGraph(List<Edge> edges, int numVertices)
{
for (int i = 0; i < numVertices; i++)
{
addVertex((V) (new Integer(i)));
}
createAdjacencyLists(edges, numVertices);
}
// Construct a graph from Integer vertices
protected AbstractGraph(int[][] edges, int numVertices)
{
for (int i = 0; i < numVertices; i++)
{
addVertex((V) (new Integer(i)));
}
createAdjacencyLists(edges, numVertices);
}
// Create an edge adjacency list for each vertex
private void createAdjacencyLists(int[][] edges, int numVertices)
{
for (int i = 0; i < edges.length; i++)
{
addEdge(edges[i][0], edges[i][1]);
}
}
// Create an edge adjacency list for each vertex
private void createAdjacencyLists(List<Edge> edges, int numVertices)
{
for (Edge edge : edges)
{
addEdge(edge.u, edge.v);
}
}
// Return the number of vertices in the graph
@Override
public int getSize()
{
return vertices.size();
}
//Return the vertices in the graph
@Override
public List<V> getVertices()
{
return vertices;
}
// Return the object for the specified vertex
@Override
public V getVertex(int index)
{
return vertices.get(index);
}
//Return the index for the specified vertex object
@Override
public int getIndex(V v)
{
return vertices.indexOf(v);
}
// Return the neighbors of the vertex specified by the index
@Override
public List<Integer> getNeighbors(int index)
{
List<Integer> result = new ArrayList<>();
for (Edge e : neighbors.get(index))
{
result.add(e.v);
}
return result;
}
//Return the degree for a specified vertex
@Override
public int getDegree(int v)
{
return neighbors.get(v).size();
}
// Print the edges by calling Vertex toString()
@Override
public void printEdges()
{
for (int u = 0; u < neighbors.size(); u++)
{
System.out.print(getVertex(u) + " (" + u + "): ");
for (Edge e : neighbors.get(u))
{
System.out.print("(" + getVertex(e.u) + ", " +
getVertex(e.v) + ") ");
}
System.out.println();
}
}
// Clear the graph: clear vertex and edge lists
@Override
public void clear()
{
vertices.clear();
neighbors.clear();
}
// Add a vertex to the graph
@Override
public boolean addVertex(V vertex)
{
if (!vertices.contains(vertex))
{
vertices.add(vertex);
neighbors.add(new ArrayList<Edge>());
return true;
}
else
{
return false;
}
}
//Add an edge to the graph
protected boolean addEdge(Edge e)
{
if (e.u < 0 || e.u > getSize() - 1)
{
throw new IllegalArgumentException("No such index: " + e.u);
}
if (e.v < 0 || e.v > getSize() - 1)
{
throw new IllegalArgumentException("No such index: " + e.v);
}
if (!neighbors.get(e.u).contains(e))
{
neighbors.get(e.u).add(e);
return true;
}
else
{
return false;
}
}
// Add an edge to the graph using the indices of the vertices
@Override
public boolean addEdge(int u, int v)
{
return addEdge(new Edge(u, v));
}
//Edge inner class inside the AbstractGraph class
public static class Edge
{
public int u;
public int v;
public Edge(int u, int v)
{
this.u = u;
this.v = v;
}
// Use equals to traverse edge
public boolean equals(Object o)
{
return (u == ((Edge) o).u && v == ((Edge) o).v);
}
//Create a String verison of the edge
public String toString()
{
return ("[(" + u + "), (" + v + ")]");
}
}
// Obtain a DFS spanning tree starting from vertex v
@Override
public Tree dfs(int v)
{
List<Integer> searchOrder = new ArrayList<>();
int[] parent = new int[vertices.size()];
for (int i = 0; i < parent.length; i++)
{
parent[i] = -1;
}
boolean[] isVisited = new boolean[vertices.size()];
dfs(v, parent, searchOrder, isVisited);
return new Tree(v, parent, searchOrder);
}
// Recursive method for DFS search
private void dfs(int u, int[] parent,
List<Integer> searchOrder,
boolean[] isVisited)
{
searchOrder.add(u);
isVisited[u] = true;
for (Edge e : neighbors.get(u))
{
if (!isVisited[e.v])
{
parent[e.v] = u;
dfs(e.v, parent, searchOrder, isVisited);
}
}
}
//Obtain a BFS spanning tree starting from vertex v
@Override
public Tree bfs(int v)
{
List<Integer> searchOrder = new ArrayList<>();
// The parent array is used by the Tree
int[] parent = new int[vertices.size()];
for (int i = 0; i < parent.length; i++)
{
parent[i] = -1;
}
MyQueue<Integer> queue = new MyQueue<Integer>();
boolean[] isVisited = new boolean[vertices.size()];
queue.enqueue(v);
isVisited[v] = true;
// Loop until each vertex added to the queue is gone
while (!queue.isEmpty())
{
int u = queue.dequeue();
searchOrder.add(u);
for (Edge e : neighbors.get(u))
{
if (!isVisited[e.v])
{
queue.enqueue(e.v);
parent[e.v] = u;
isVisited[e.v] = true;
}
}
}
return new Tree(v, parent, searchOrder);
}
// Tree inner class inside the AbstractGraph class
public class Tree
{
private int root;
private int[] parent;
private List<Integer> searchOrder;
//Construct a tree with root, parent, and searchOrder
public Tree(int root, int[] parent, List<Integer> searchOrder)
{
this.root = root;
this.parent = parent;
this.searchOrder = searchOrder;
}
//Return the root of the tree
public int getRoot()
{
return root;
}
// Return the parent of vertex v
public int getParent(int v)
{
return parent[v];
}
// Return an array representing search order
public List<Integer> getSearchOrder()
{
return searchOrder;
}
//Return number of vertices found
public int getNumberOfVerticesFound()
{
return searchOrder.size();
}
// Return the path of vertices from a vertex whose index is given to the root
public List<V> getPath(int index)
{
ArrayList<V> path = new ArrayList<>();
do
{
path.add(vertices.get(index));
index = parent[index];
}
while (index != -1);
return path;
}
//Print a path of vertices from the root to vertex v whose index is given
public String printPath(int index)
{
String str = "";
List<V> path = getPath(index);
str += "A path from " + vertices.get(root) +
" to " + vertices.get(index) + ": ";
int count = 0;
// Print the path in reverse from root to index
for (int i = path.size() - 1; i > 0; i--)
{
if (i < path.size() - 1 && count % 5 == 0)
{
str += " " + path.get(i) + "--> ";
}
else
{
str += path.get(i) + "--> ";
}
count++;
}
str += path.get(0);
return str;
}
//Print the path of edges from the root to the starting vertex given when the Tree was built
public String printTree()
{
String str = "";
str += "Root is " + vertices.get(root) + " ";
str += "Edges:";
int count = 0;
for (int i = 0; i < parent.length; i++)
{
if (parent[i] != -1)
{
// Display an edge
if (count % 5 == 0)
{
str += " " + "(" + vertices.get(parent[i]) + ", " +
vertices.get(i) + ") ";
}
else
{
str += " " + "(" + vertices.get(parent[i]) + ", " +
vertices.get(i) + ") ";
}
count++;
}
}
str += " ";
return str;
}
}
}
----------------------------------------------------------------------------------
import java.text.DecimalFormat;
public class City implements Comparable<City>
{
private String city;
private double gpsX;
private double gpsY;
private int population;
private int vertIndex;
//Constructs 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;
}
// Returns the City name
public String getCity()
{
return city;
}
//Returns the City longitude
public double getLongitude()
{
return gpsX;
}
//Returns the City latitude
public double getLatitude()
{
return gpsY;
}
//Returns the City poulation
public int getPopulation()
{
return population;
}
//Returns the City index in the vertex ArrayList
public int getIndex()
{
return vertIndex;
}
//Sets the City index of the vertex ArrayList
public void setIndex (int index)
{
vertIndex = index;
}
//Compares the City populations
@Override
public int compareTo (City c)
{
int thisPop = getPopulation();
int thatPop = c.getPopulation();
int compareValue = -2;
if (thisPop > thatPop)
{
compareValue = 1;
}
else if (thisPop < thatPop)
{
compareValue = -1;
}
else if (thisPop == thatPop)
{
compareValue = 0;
}
return compareValue;
}
//Return true, when the City names are the same
@Override
public boolean equals (Object c)
{
boolean sameName = false;
City otherCity = (City) c;
if (this.city.equalsIgnoreCase(otherCity.getCity()))
{
sameName = true;
}
return sameName;
}
// Return the City info as a String
public String printCity()
{
DecimalFormat df = new DecimalFormat("#.0#");
String cityInfo =
String.format(getCity() + ": [" + getIndex() + "]" + ":["
+ "%s, %s" + "]:(" + getPopulation()
+ ")", df.format(gpsX), df.format(gpsY));
return cityInfo;
}
// Return the City name as a String
public String toString()
{
return city;
}
}
----------------------------------------------------------------------------
import java.util.*;
public class CityRoadMap<V> extends WeightedGraph<V>
{
public CityRoadMap()
{
}
public CityRoadMap (List<V> vertices, List<WeightedEdge> edges)
{
super(vertices, edges);
}
// Returns the neighbors of the City object vertex
public List<V> getNeighbors (V v)
{
ArrayList<V> result = new ArrayList<>();
int index = this.getIndex(v);
neighbors.get(index).forEach(e -> result.add(this.getVertex(e.v)));
return result;
}
//Displays cities and roads with distances and direction
public String printRoads()
{
StringBuilder roads = new StringBuilder();
this.getVertices().forEach(v ->
{
roads.append('[').append(((City)v).printCity()).append("]: ");
for (Edge e : neighbors.get(this.getIndex(v)))
{
roads.append(" ").append(((Road)e).printRoad()).append(' ');
}
roads.append(' ');
});
return roads.toString();
}
//Displays cities with GPS coordinates and population
public String printCities()
{
StringBuilder cities = new StringBuilder();
this.getVertices().forEach(v ->
{
cities.append(((City)v).printCity()).append(' ');
});
return cities.toString();
}
}
--------------------------------------------------------------------------------------
public interface Graph<V>
{
// Return the number of vertices in the graph
public int getSize();
//Return the vertices in the graph
public java.util.List<V> getVertices();
// Return the object for the specified vertex index
public V getVertex (int index);
// Return the index for the specified vertex object
public int getIndex (V v);
//Return the neighbors of vertex with the specified index
public java.util.List<Integer> getNeighbors (int index);
//Return the degree for a specified vertex
public int getDegree (int v);
// Print the edges
public void printEdges();
//Clear the graph
public void clear();
//Add a vertex to the graph
public boolean addVertex (V vertex);
// Add an edge to the graph
public boolean addEdge (int u, int v);
// Obtain a depth-first search tree
public AbstractGraph<V>.Tree dfs (int v);
//Obtain a breadth-first search tree
public AbstractGraph<V>.Tree bfs (int v);
}
---------------------------------------------------------------------------------
import java.util.*;
public class MyQueue<E extends Comparable<E>>
{
private LinkedList<E> list = new LinkedList<E>();
public void enqueue(E e)
{
list.addLast(e);
}
public E dequeue()
{
return list.removeFirst();
}
public int getSize()
{
return list.size();
}
public boolean isEmpty()
{
return list.size() == 0;
}
@Override
public String toString()
{
return "Queue: " + list.toString();
}
}
-----------------------------------------------------------------------
import java.text.DecimalFormat;
public class Road extends WeightedEdge implements Comparable<WeightedEdge>
{
private City startCity;
private City endCity;
private double distance;
private String direction;
public Road (City c1, City c2)
{
super (c1.getIndex(), c2.getIndex(), 0);
// Initialize the endpoint cities
startCity = c1;
endCity = c2;
// add code here
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)
{
double thisRoad = getDistance();
double thatRoad = edge.getDistance();
int compareValue = -2;
if(thisRoad > thatRoad)
{
compareValue = 1;
}
else if (thisRoad < thatRoad)
{
compareValue = -1;
}
else if (thisRoad == thatRoad)
{
compareValue = 0;
}
return compareValue;
}
// Calling computeDirection computes the direction of the Road object
private void computeDirection()
{
// 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);
double x3 = x1;
double y3 = y2;
if (quad == 1 || quad == 3)
{
// These are for Quad 1 or Quad 3
x3 = x2;
y3 = y1;
}
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.
double angleA = compAngle (sideA, sideB, sideC);
// Convert the sideC length (distance from PtA to PtB) into miles
distance = sideC * 3956;
// The distance is also the weight
weight = distance;
direction = compDirection (angleA, quad);
}
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)
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,
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:
public String printRoad()
{
DecimalFormat df = new DecimalFormat("#.0#");
String beginCity = startCity.getCity();
String endPoint = endCity.getCity();
String theDistance = String.format("%s miles", df.format(distance));
String theDirection = getDirection();
String roadInfo =
beginCity + " to " + endPoint + " traveling " + theDirection +
" for " + theDistance;
return roadInfo;
}
// Return the Road info as a String containing City names
public String toString()
{
String beginCity = startCity.getCity();
String endPoint = endCity.getCity();
String aRoad = "Road: " + beginCity + " to " + endPoint;
return aRoad;
}
}
-------------------------------------------------------------------------------------
public class WeightedEdge extends AbstractGraph.Edge
implements Comparable<WeightedEdge>
{
public double weight; // The weight on edge (u, v)
// Create a weighted edge on (u, v)
public WeightedEdge (int u, int v, double weight)
{
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 " wt = " + weight;
}
}
---------------------------------------------------------------------------
import java.util.*;
@SuppressWarnings("unchecked")
public class WeightedGraph<V> extends AbstractGraph<V>
{
public WeightedGraph()
{
}
public WeightedGraph(V[] vertices, int[][] edges)
{
createWeightedGraph (java.util.Arrays.asList (vertices), edges);
}
public WeightedGraph (int[][] edges, int numVertices)
{
List<V> 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<V> vertices, List<WeightedEdge> edges)
{
createWeightedGraph (vertices, edges);
}
//Construct a WeightedGraph from Integer vertices and edge list
public WeightedGraph (List<WeightedEdge> edges, int numVertices)
{
List<V> vertices = new ArrayList<>();
for (int i = 0; i < numVertices; i++)
{
vertices.add ((V)(new Integer (i)));
}
createWeightedGraph (vertices, edges);
}
private void createWeightedGraph (List<V> vertices, int[][] edges)
{
this.vertices = vertices;
for (int i = 0; i < vertices.size(); i++)
{
neighbors.add (new ArrayList<Edge>());
}
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]));
}
}
private void createWeightedGraph (List<V> vertices, List<WeightedEdge> edges)
{
this.vertices = vertices;
for (int i = 0; i < vertices.size(); i++)
{
neighbors.add (new ArrayList<Edge>());
}
for (WeightedEdge edge: edges)
{
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)
{
double[] cost = new double[getSize()];
for (int i = 0; i < cost.length; i++)
{
cost[i] = Double.POSITIVE_INFINITY;
}
cost[startingVertex] = 0;
int[] parent = new int[getSize()];
parent[startingVertex] = -1;
double totalWeight = 0;
List<Integer> T = new ArrayList<>();
while (T.size() < getSize())
{
int u = -1;
double currentMinCost = Double.POSITIVE_INFINITY;
for (int i = 0; i < getSize(); i++)
{
if (!T.contains(i) && cost[i] < currentMinCost)
{
currentMinCost = cost[i];
u = i;
}
}
T.add (u);
totalWeight += cost[u];
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;
}
}
}
return new MST (startingVertex, parent, T, totalWeight);
}
// MST is an inner class in WeightedGraph
public class MST extends Tree
{
private double totalWeight;
public MST (int root, int[] parent, List<Integer> searchOrder,
double totalWeight)
{
super (root, parent, searchOrder);
this.totalWeight = totalWeight;
}
public double getTotalWeight()
{
return totalWeight;
}
}
//Find single source shortest paths
public ShortestPathTree getShortestPath (int sourceVertex)
{
double[] cost = new double[getSize()];
for (int i = 0; i < cost.length; i++)
{
cost[i] = Double.POSITIVE_INFINITY;
}
cost[sourceVertex] = 0;
int[] parent = new int[getSize()];
parent[sourceVertex] = -1;
List<Integer> T = new ArrayList<>();
while (T.size() < getSize())
{
int u = -1;
double currentMinCost = Double.POSITIVE_INFINITY;
for (int i = 0; i < getSize(); i++)
{
if (!T.contains(i) && cost[i] < currentMinCost)
{
currentMinCost = cost[i];
u = i;
}
}
T.add (u);
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;
}
}
}
return new ShortestPathTree (sourceVertex, parent, T, cost);
}
//ShortestPathTree is an inner class in WeightedGraph
public class ShortestPathTree extends Tree
{
private double[] cost;
public ShortestPathTree (int source, int[] parent,
List<Integer> 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;
}
}
}