NetBeans Java Code: Well documented please. Your task for this assignment is to
ID: 3696065 • Letter: N
Question
NetBeans Java Code: Well documented please.
Your task for this assignment is to create one or more software methods to determine the shortest path between anytwo specified nodes in a directedweighted graph that represents links between U.S.cities. The Netbeans project CityProject has software that creates a graph of selected U.S. represented by an array of vertices and an array of edges. Each city is a vertex in the graph. Each link between cities is an edge in the graph, as shown below in the output from the project as it currently existsExplanation / Answer
CityProject.java
import java.awt.*;
import javax.swing.*;
import java.util.*;
import java.io.*;
public class CityProject {
// main metod for the project
public static void main(String[] args) {
/**************Scanner Code************************/
String source;
String destination;
//sets up input stream from the keyboard
Scanner keyboardInput;
keyboardInput = new Scanner(System.in);
//get the full loan amount
System.out.print("Please enter your start location ");
source = keyboardInput.nextLine();
//get the annual interest rate
System.out.print("Please enter your destination ");
destination = keyboardInput.nextLine();
/**************Scanner Code************************/
City[] cities = new City[123]; //array of cities (Vertices) max = 200
for (int i = 0; i < cities.length; i++) {
cities[i] = new City();
}
Edge[] links = new Edge[2000];// array of links (Edges) max = 2000
for (int i = 0; i < links.length; i++) {
links[i] = new Edge();
}
int cityCount; // actual number of cities
int linkCount; // actual number of links
// load cities into an array from a datafile
cityCount = readCities(cities);
// load links into an array from a datafile
linkCount = readLinks(links, cities);
// create the adjacency list for each city based on the link array
createAdjacencyLists(cityCount, cities, linkCount, links);
// print adjacency lists for all cities
//PrintAdjacencyLists(cityCount, cities);
// draw a map of the cities and links
//drawMap(cityCount, cities,linkCount, links);
//call dijkstra method to run algorithm
dijkstra(source, cities);
//create stack to hold stack of destination to source city StackElems
Stack testStack = new Stack();
testStack= addToStack(source, destination, cities );
//print the route of the shortest path for source and destination city
printShortestPath(testStack, source, destination);
} // end main
//************************************************************************
// method to read city data into an array from a data file
public static int readCities(City[] cities) {
int count = 0; // number of cities[] elements with data
String[][] cityData = new String[123][3]; // holds data from the city file
String delimiter = ","; // the delimiter in a csv file
String line; // a String to hold each line from the file
String fileName = "cities.csv"; // the file to be opened
try {
// Create a Scanner to read the input from a file
Scanner infile = new Scanner(new File(fileName));
/* This while loop reads lines of text into an array. it uses a Scanner class
* boolean function hasNextLine() to see if there is another line in the file.
*/
while (infile.hasNextLine()) {
// read the line
line = infile.nextLine();
// split the line into separate objects and store them in a row in the array
cityData[count] = line.split(delimiter);
// read data from the 2D array into an array of City objects
cities[count].setName(cityData[count][0]);
cities[count].setX(Integer.parseInt(cityData[count][1]));
cities[count].setY(Integer.parseInt(cityData[count][2]));
count++;
}// end while
infile.close();
} catch (IOException e) {
// error message dialog box with custom title and the error icon
JOptionPane.showMessageDialog(null, "File I/O error:" + fileName, "File Error",
JOptionPane.ERROR_MESSAGE);
}
return count;
} // end loadCities()
//*************************************************************************
// method to read link data into an array from a data file
public static int readLinks(Edge[] links, City[] cities) {
int count = 0; // number of links[] elements with data
String[][] CityLinkArray = new String[695][3]; // holds data from the link file
String delimiter = ","; // the delimiter in a csv file
String line; // a String to hold each line from the file
String fileName = "links.csv"; // the file to be opened
try {
// Create a Scanner to read the input from a file
Scanner infile = new Scanner(new File(fileName));
/* This while loop reads lines of text into an array. it uses a Scanner class
* boolean function hasNextLine() to see if there another line in the file.
*/
while (infile.hasNextLine()) {
// read the line
line = infile.nextLine();
// split the line into separate objects and store them in a row in the array
CityLinkArray[count] = line.split(delimiter);
// read link data from the 2D array into an array of Edge objects
// set source to vertex with city name in source column
links[count].setSource(findCity(cities, CityLinkArray[count][0]));
// set destination to vertex with city name in destination column
links[count].setDestination(findCity(cities, CityLinkArray[count][1]));
//set length to integer valuein length column
links[count].setLength(Integer.parseInt(CityLinkArray[count][2]));
count++;
}// end while
} catch (IOException e) {
// error message dialog box with custom title and the error icon
JOptionPane.showMessageDialog(null, "File I/O error:" + fileName, "File Error",
JOptionPane.ERROR_MESSAGE);
}
return count;
} // end loadLinks()
//*************************************************************************
// emthod to find the City onject with the given city name
public static City findCity(City[] cities, String n) {
int index = 0; // loop counter
// go through the cities array until the name is found
// the name will be in the list
while (cities[index].getName().compareTo(n) != 0) {
index++;
}// end while()
return cities[index];
} // end findCity()
// method to create an adjacency lists for each city
public static void createAdjacencyLists(int cityCount, City[] cities, int linkCount, Edge[] links) {
AdjacencyNode temp = new AdjacencyNode();
// iterate city array
for (int i = 0; i < cityCount; i++) {
//iterate link array
for (int j = 0; j < linkCount; j++) {
// if the currentl link's source is the current city
if (links[j].getSource() == cities[i]) {
/* create a node for the link and inseert it into the adjancency list
* as the new head of the list.
*/
// temporarily store the current value of the list's head
temp = cities[i].getAdjacencyListHead();
//create a new node
AdjacencyNode newNode = new AdjacencyNode();
// add city and distance data
newNode.setCity(links[j].getDestination());
newNode.setDistance(links[j].getLength());
// point newNode to the previous list head
newNode.setNext(temp);
// set the new head of the list to newNode
cities[i].setAdjacencyListHead(newNode);
} // end if
} // end for j
} // end for i
} // end createAdjacencyLists()
// method to print adjacency lists
public static void PrintAdjacencyLists(int cityCount, City[] cities) {
System.out.println("List of Edges in the Graph of Cities by Source City");
// iterate array of cities
for (int i = 0; i < cityCount; i++) {
// set current to adjacency list for this city
AdjacencyNode current = cities[i].getAdjacencyListHead();
// print city name
System.out.println(" From " + cities[i].getName());
// iterate adjacency list and print each node's data
while (current != null) {
System.out.println(" "+ current.toString());
current = current.getNext();
} // end while (current != null)
} // end for i
} // end PrintAdjacencyLists()
// method to draw the graph (map of cities and links)
static void drawMap(int cCount, City[] c, int lCount, Edge[] l)
{
CityMap canvas1 = new CityMap(cCount, c, lCount, l);
int width = 1500; // width of the Canvas
int height = 900; // heightof the Canvas
// set up a JFrame to hold the canvas
JFrame frame = new JFrame();
frame.setTitle("U.S. Cities");
frame.setSize(width, height);
frame.setLocation(10, 10);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
// add the canvas to the frame as a content panel
frame.getContentPane().add(canvas1);
frame.setVisible(true);
} // end drawMap()
/******methods written by Leslie Salazar ****************************/
//method takes source city and an array and implements dijkstra's algorithm to find shortest path for
//all cities in the array.
public static void dijkstra(String source, City[] allCities)
{
//will hold sourceCity
City sourceCity;
//will hold currentCity
City currentCity;
//Step 1
//find the city from array of all cities assign to sourceCity variable
//set its bestDistance to 0 & its immediatePredecessor to null
sourceCity = findCity(allCities, source);
sourceCity.setBestDistance(0);
sourceCity.setImmediatePredecessor(null);
//set currentCity to point to sourceCity
currentCity = sourceCity;
while(!visited(allCities))
{
//System.out.println("name from dijk "+currentCity.getName());
setEdgeBstDist(currentCity);
currentCity.setVisited(true);
currentCity = citiesBestDist(allCities);
}//end while
}//end dijkstra()
//for every edge in the adjacency list, find the bestdistance through the current city.
//The method will do this only if the calculated bestdistance is better than what's
//already been found.
public static void setEdgeBstDist(City curCity)
{
AdjacencyNode currentNode = curCity.getAdjacencyListHead();
//System.out.println(currentNode.toString());
while(currentNode != null)
{
//System.out.println("inside dij while");
//current Edge's best distance previously
int prevBstDist = currentNode.getCity().getBestDistance();
//current Edge's best distance through current city
int BstDistThruCurCity = curCity.getBestDistance() + currentNode.getcDistance();
//if bestDistance through current city is less than before
//set the new bestdistance for that Edge's city and set the
//immediate predecessor to be the current City
if(BstDistThruCurCity < prevBstDist)
{
currentNode.getCity().setBestDistance(BstDistThruCurCity);
//System.out.println("line 349 setEdgeBstDist"+currentNode.getCity().getBestDistance());
currentNode.getCity().setImmediatePredecessor(curCity);
//currentNode = currentNode.getNext();
//System.out.println(currentNode.toString());
}
//to avoid null pointer exception
//if(currentNode.getNext()!=null)
//{
currentNode = currentNode.getNext();
//}
//if(temp)
}//end while
curCity.setVisited(true);
}//end setEdgeBstDist
//for all cities in cities[], will find city with best distance
public static City citiesBestDist(City[] allCities)
{
City bDistCity = null;
int minVal = Integer.MAX_VALUE;
int tempVal;
for(int i = 0; i < allCities.length; i++)
{
if(allCities[i].getBestDistance() <= minVal && allCities[i].getVisited() != true)
{
//System.out.println("citiesBestcalled line 380");
minVal = allCities[i].getBestDistance();
bDistCity = allCities[i];
//System.out.println("best distance city: "+bDistCity.getName());
}//end if
}//end for loop
return bDistCity;
}//end citiesBestDist()
//method will find if all cities have been visited
public static boolean visited(City[] allCities)
{
boolean beenVisited = true;
for(int i = 0; i < allCities.length; i++)
{
if(allCities[i].getVisited() == false)
{
beenVisited = false;
}//end if
}//end for loop
return beenVisited;
}//end visited
//method will use the provided source and destination string to add the immediate predecessor
//city chain beginnning from the destination city and ending at the source city.
public static Stack addToStack(String source, String destination, City[] citiesArray)
{
City nodeToAddToStack;
City currentCity;
Stack shortestPath = new Stack();
//find the destination city
nodeToAddToStack = findCity(citiesArray,destination);
currentCity = nodeToAddToStack;
StackElem stackDestCity = new StackElem(currentCity);
shortestPath.push(stackDestCity);
//System.out.println(currentCity.getName());
boolean done = false;
while(!done)
{
//System.out.println(currentCity.getName());
currentCity = currentCity.getImmediatePredecessor();
StackElem stackCity = new StackElem(currentCity);
shortestPath.push(stackCity);
//if(source == currentCity.getName())
if(currentCity.getName().compareTo(source) == 0)
{
done = true;
}
}//end while loop
return shortestPath;
}//end addToStack
//method will take a stack with each city from the shortest path found for a
//source and destination city and pop each StackElem and print the city's name.
public static void printShortestPath(Stack spStack, String source, String destination)
{
StackElem cityInfo;
int i = 0;
System.out.println("Here is your shortest path from " + source + " to " + destination + " " );
while(i < spStack.stackSize())
{
cityInfo = spStack.pop();
System.out.println(cityInfo.getStackData().getName() + " ");
}
}//printShortestPath()
/****************************************************************************/
} // end class cityProject
City.java
class City extends Vertex {
// added properties
private boolean visited = false;
private int bestDistance = Integer.MAX_VALUE; //maximum value and integer can have
private City immediatePredecessor;
private AdjacencyNode adjacencyListHead; // link to first node in adjacency list
City() {}
//added methods
public void setVisited(boolean v) {
this.visited = v;
} // end setVisited()
public void setBestDistance(int b) {
this.bestDistance = b;
} // end setBestDistance()
public void setImmediatePredecessor(City c) {
this.immediatePredecessor = c;
} // end setImmediatePredecessor()
public void setAdjacencyListHead(AdjacencyNode a) {
this.adjacencyListHead = a;
} // end setAdjacencyListHead()
public boolean getVisited() {
return this.visited;
} // end getVisited()
public int getBestDistance() {
return this.bestDistance;
} // end getBestDistance()
public City getImmediatePredecessor() {
return this.immediatePredecessor;
} // end getImmediatePredecessor()
public AdjacencyNode getAdjacencyListHead() {
return this.adjacencyListHead;
} // end getAdjacencyListHead()
} // end class MyCity
Vertex.java
public class Vertex {
private String name; // name of the city
private int x; // city's x-coordinate for drawing
private int y; // city's y-coordinate for drawing
Vertex() {
} // end Vertex()
Vertex(String n, String s, int x, int y) {
this.name = n;
this.x = x;
this.y = y;
} // end Vertex(...)
public void setName(String n) {
this.name = n;
} // end setName()
public void setX(int x) {
this.x = x;
} // end setX()
public void setY(int y) {
this.y = y;
} // end setY()
public String getName() {
return this.name;
} // end getName()
public int getX() {
return this.x;
} // end getX()
public int getY() {
return this.y;
} // end getY()
public String toString() {
return (this.name + " " + " " + this.x + " " + this.y);
} // end toString()
} // end class Vertex
Edge.java
//Array of edges sorted by source
public class Edge {
City source; // the name of the source vertex;
City destination; // the name of the destination vertex;
int length; // the length of the edge;
Edge() {
}
Edge(City s, City d, int l) {
this.source = s;
this.destination = d;
this.length = l;
} // end Edge(...)
public void setSource(City s) {
this.source = s;
} // end setSource
public void setDestination(City d) {
this.destination = d;
} // end setDestination
public void setLength(int l) {
this.length = l;
} // end setLength
public City getSource() {
return this.source;
} // end getSource
public City getDestination() {
return this.destination;
} // end getDestination
public int getLength() {
return this.length;
} // end getLength
public String toString() {
return this.source + " to " + this.destination + ": " + this.length;
}
} //end class edge
Stack.java
public class Stack
{
//tail StackElem of Stack
private StackElem tail;
//top StackElem of Stack
private StackElem top;
//Stack contructor assigns null to tail and top properties
public Stack()
{
this.tail = null;
this.top = null;
}
//Accessor methods
public StackElem getTop()
{
return top;
}
public StackElem getTail()
{
return tail;
}
//Mutator methods
public void setTop(StackElem elemToAdd)
{
this.top = elemToAdd;
}
public void setTail(StackElem elemToAdd)
{
this.tail = elemToAdd;
StackElem temp;
temp = elemToAdd;
StackElem currentElem = top;
if(top == null)
{
this.top = temp;
}
else
{
while(currentElem.getNextStacElem() != null)
{
currentElem = currentElem.getNextStacElem();
}//end while
currentElem.setNextStackElem(temp);
}
}//end setTail()
//will crawl Stack and return integer of number of StackElems in Stack
public int stackSize()
{
int i;
StackElem currentElem = top;
for(i = 0; currentElem != null; i++)
{
currentElem = currentElem.getNextStacElem();
}
return (i);
}
//push method takes as parameter a StackElem to add to the top of the Stack
//method keeps track of tail poistion withing Stack
public void push(StackElem elemToAdd)
{
StackElem currentElem = tail;
if(top == null)
{
top = elemToAdd;
tail = top;
}else
{
elemToAdd.setNextStackElem(top);
top = elemToAdd;
}
}//end push()
//method returns Stack's top StackElem and removes it from Stack
public StackElem pop()
{
StackElem tempTop= top;
if(top == null)
{
System.out.println("The Stack is empty");
}else
{
tempTop = top;
top = top.getNextStacElem();
//return tempTop;
}
return tempTop;
}
//method crawls Stack from top and prints to console data from StackElem
public void printStack()
{
StackElem currentElem = top;
String wordString;
if(this.top ==null)
{
System.out.println("Stack is empty");
}else if (currentElem != null)
{
while(currentElem != null)
{
wordString = currentElem.getStackData().getName();
System.out.println("String from Stack's printStack method "+wordString);
currentElem = currentElem.getNextStacElem();
}//end while
}//end else if
}//end printStack()
}
StackElem.java
public class StackElem
{ //pointer to String
private City data;
//pointer to next StackElem
private StackElem nextElem;
//constructor sets property pointers to null
public StackElem()
{
this.data = null;
this.nextElem = null;
}
//constructor with pointer to String
public StackElem(City dataElem)
{
this.data = dataElem;
}
//constructor with pointer to string and pointer to next StackElem
public StackElem(City dataElem, StackElem nextDataElem)
{
this.data = dataElem;
this.nextElem = nextDataElem;
}
//accessor methods
public City getStackData()
{
return data;
}
public StackElem getNextStacElem()
{
return nextElem;
}
//mutator methods
public void setStackData(City dataElem)
{
this.data = dataElem;
}
public void setNextStackElem(StackElem nextStackElem)
{
this.nextElem = nextStackElem;
}
}
AdjacencyNode.java
class AdjacencyNode {
private City city;
private int distance;
AdjacencyNode next;
AdjacencyNode() {
}
AdjacencyNode(City c, int d) {
this.city = c;
this.distance = d;
} // end AdjacencyNode
public void setCity(City c) {
this.city = c;
} // end setCityName()
public void setDistance(int d) {
this.distance = d;
} // end setDistance()
public void setNext(AdjacencyNode a) {
this.next = a;
} // end setNext()
public City getCity() {
return this.city;
} // end getcityName()
public int getcDistance() {
return this.distance;
} // end getcDistance()
public AdjacencyNode getNext() {
return this.next;
} // end getNext()
public String toString() {
return ("to: " + this.city.getName() +" distance: "+ this.distance);
} // end getNext()
} // end class AdjacencyNode
CityMap.java
import java.awt.*;
import javax.swing.*;
public class CityMap extends Canvas {
City[] cities = new City[200]; //array of cities (Vertices) max = 200
int cityCount; // actual number of cities
Edge[] links = new Edge[2000]; // array of links (Edges) max = 2000
int linkCount; // avtual number of links
CityMap() {
} // end CityCanvas(...)
CityMap(int cCount, City[] c, int lCount, Edge[] l) {
this.cities = c;
this.cityCount = cCount;
this.links = l;
this.linkCount = lCount;
} // end CityCanvas(...)
public void paint(Graphics graphics) {
// fill background
graphics.setColor(Color.WHITE);
graphics.fillRect(0, 0, 1500, 900);
// place us image under map
Image us = new ImageIcon("us.png").getImage();
graphics.drawImage(us, 125, 0, null);
// draw links
// iterate link array
for (int i = 0; i < linkCount; i++) {
// get soucrce city and destination city coordinates
int xS = links[i].getSource().getX(); // x coordinate of source city
int yS = links[i].getSource().getY(); // y coordinate of source city
int xD = links[i].getDestination().getX(); // x coordinate of destination city
int yD = links[i].getDestination().getY(); // y coordinate of destination city
graphics.setColor(new Color(200, 200, 200));
graphics.drawLine(xS, yS, xD, yD);
} // end for
// draw cities
for (int i = 0; i < cityCount; i++) {
//draw a dot for each city, 4 x 4 pixels
graphics.setColor(Color.red);
graphics.fillOval(cities[i].getX() - 3, cities[i].getY() - 3, 6, 6);
} // end for
// draw labels
for (int i = 0; i < cityCount; i++) {
// draw a label for each city, offest by 6 hor. and 9 ver. pixels
graphics.setColor(Color.black);
graphics.setFont(new Font("Lucida Console", Font.BOLD, 9));
graphics.drawString(cities[i].getName(), cities[i].getX() + 6, cities[i].getY() + 9);
} // end for
// add note to the canvas
Image logo = new ImageIcon("note.png").getImage();
graphics.drawImage(logo, 35, 600, null);
} // end paint()
} // end class CityMap
//**********************************************************************************************************************************
links.csv
Albany NY New York NY 145
Albany NY Portland ME 270
cities.csv
Amarillo TX 659 406
sample output
Please enter your start location
Albany
Please enter your destination
Portland
Scranton
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.