Need help building following weighted graph in java class for NCCitiesRoads (see bolded area):

import java.util.*;

/** The NC Routes Project: Lesson 10 Start * The NCCitiesRoads class creates a graph * from city and road information */ 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 interface Graph { /** Return the number of vertices in the graph */

public int getSize();

/** Return the vertices in the graph */

public java.util.List 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 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.Tree dfs (int v);

/** Obtain a breadth-first search tree */

public AbstractGraph.Tree bfs (int v); }

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

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; } } }