fix the readFileMethod / BreadthFirst / DepthFirst Testing Enter an input mileag
ID: 3719214 • Letter: F
Question
fix the readFileMethod / BreadthFirst / DepthFirst
Testing
Enter an input mileages file and an output graph file in your run configurations, such as below:
MileagesSmall.csv
,Aspen,Boulder,Breckenridge,Craig,Denver,Durango,Fort Collins,Pueblo,Snowmass,Telluride
Aspen,,,,158,,,,,8,248
Boulder,,,99,,28,,55,146,,
Breckenridge,,,,,81,,,190,136,
Craig,,,,,198,,,,156,
Denver,,,,,,,64,112,,
Durango,,,,,,,,,,120
Fort Collins,,,,,,,,,,
Pueblo,,,,,,,,,,
Snowmass,,,,,,,,,,
Telluride,,,,,,,,,,
Here is the output you should see from your program, when it is working correctly:
And this is the image that it generates:
In recitation you were exposed to webgraphviz as a visualization tool. Another way to generate the png is via the terminal with using the following command:
// GraphImplementation.java - supplied code for graph assignment
import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
public class GraphImplementation extends GraphAbstract {
// Main entry point
public static void main(String[] args) {
if (args.length != 2) {
System.err.println("usage: java GraphImplementation ");
System.exit(-1);
}
// Instantiate code
GraphImplementation impl = new GraphImplementation();
// Read distances chart
System.out.println("Reading Chart: " + args[0]);
impl.readGraph(args[0]);
System.out.println();
// Write distances graph
System.out.println("Writing Graph: " + args[1]);
impl.writeGraph(args[1]);
System.out.println();
// Print depth first search
System.out.println("Depth First Search:");
impl.depthFirst("Fort Collins");
System.out.println();
// Print breadth first search
System.out.println("Breadth First Search:");
impl.breadthFirst("Aspen");
System.out.println();
/*
// EXTRA CREDIT: Print all shortest paths
for (int from = 0; from < cities.size(); from++) {
for (int to = 0; to < cities.size(); to++)
if (from != to) {
String fromCity = cities.get(from).name;
String toCity = cities.get(to).name;
System.out.print("Shortest Path: ");
impl.shortestPath(fromCity, toCity);
}
}
*/
}
// Reads mileage chart from CSV file
public void readGraph(String filename) {
// YOUR CODE HERE
ArrayList myCities = readFile(filename);
String[] line1 = myCities.get(0).split(",");
for(int i = 1; i < line1.length; i++) {
cities.add(new GraphNode(line1[i]));
}
for(int j = 1; j< myCities.size(); j++){
String[] edgeLine = myCities.get(j).split(",");
for(int i = 1; i< edgeLine.length; i++) {
if(!edgeLine[i].isEmpty()) {
mileages.add(new GraphEdge(j-1, i-1, Integer.parseInt(edgeLine[i])));
}
}
Collections.sort(mileages);
}
}
public void writeGraph(String filename) {
ArrayList output = new ArrayList<>();
output.add("digraph BST {");
output.add(" ratio = 1.0;");
output.add(" node [style=filled]");
output.add(" node [fillcolor=darkslateblue]");
output.add(" node [fixedsize=true]");
output.add(" node [shape=oval]");
output.add(" node [width=6]");
output.add(" node [height=4]");
output.add(" node [fontname=Arial]");
output.add(" node [fontsize=60]");
output.add(" node [fontcolor=white]");
output.add(" edge [dir=none]");
output.add(" edge [penwidth=24]");
output.add(" edge [fontname=Arial]");
output.add(" edge [fontsize=110]");
int cityIndex = 0;
for (GraphNode city: cities) {
output.add(" Node" + cityIndex + " [label="" + city.name + ""];");
cityIndex++;
}
for (GraphEdge edge: mileages) {
if (!(edge.fromIndex >= edge.toIndex)) {
String color;
if (edge.mileage <= 100) {
color = "green";
}
else if (edge.mileage <= 200) {
color = "blue";
}
else if (edge.mileage <= 300) {
color = "magenta";
}
else {
color = "red";
}
output.add(" Node" + edge.fromIndex + " -> Node" + edge.toIndex + " [label="" + edge.mileage + "" color="" + color + ""]");
}
}
// Write distances graph
output.add("}");
writeFile(filename, output);
}
public void depthFirst(String startCity) {
// YOUR CODE HERE
}
// Recursive helper method
public void depthFirst(int index, ArrayList visited) {
// YOUR CODE HERE
}
public void breadthFirst(String startCity) {
// YOUR CODE HERE
}
public void shortestPath(String fromCity, String toCity) {
// YOUR CODE HERE
}
// Helper functions
/**
* Reads the contents of file to {@code ArrayList}
* @param filename the file to read from
* @return an ArrayList of the contents
*/
static ArrayList readFile(String filename) {
ArrayList contents = new ArrayList<>();
try(Scanner reader = new Scanner(new File(filename))) {
while (reader.hasNextLine()) {
String line = reader.nextLine().trim();
if (!line.isEmpty())
contents.add(line);
}
} catch (IOException e) {
System.err.println("Cannot read chart: " + filename);
}
return contents;
}
/**
* Write contents of {@code ArrayList} to file
* @param filename the name of the file to write to
* @param contents an ArrayList of contents to write
*/
static void writeFile(String filename, ArrayList contents) {
try(PrintWriter writer = new PrintWriter(filename)) {
for (String line : contents)
writer.println(line);
} catch (IOException e) {
System.err.println("Cannot write graph: " + filename);
}
}
}
----------------------------------------------------------------------------
// GraphAbstract.java - abstract class for graph assignment
import java.util.ArrayList;
public abstract class GraphAbstract {
// Represents a graph edge
public class GraphEdge implements Comparable<GraphEdge> {
public int fromIndex; // index of "from" city
public int toIndex; // index of "to" city
public int mileage; // mileage between cities
public GraphEdge (int from, int to, int mileage) {
this.fromIndex = from;
this.toIndex = to;
this.mileage = mileage;
}
public int compareTo(GraphEdge edge) {
return this.mileage - edge.mileage;
}
}
// Represents a graph node (and incident edges)
public class GraphNode {
public String name; // City name
public ArrayList<GraphEdge> edges; // Distances
public GraphNode(String name) {
this.name = name;
edges = new ArrayList<>();
}
public boolean equals(Object object) {
return object instanceof GraphNode && ((GraphNode) object).name.equals(this.name);
}
}
// Graph data structures
public static ArrayList<GraphNode> cities = new ArrayList<>();
public static ArrayList<GraphEdge> mileages = new ArrayList<>();
/**
* Reads mileage chart from CSV file and builds lists of nodes (cities) and edges (distances).
* <p>
* The first line contains all the cities which should be represented as {@link GraphNode}s <br>
* The successive lines start with a city, followed by a list of mileages to other cities.
* <p>
* To avoid redundancy, not all the values are filled in, ignore empty entries. <br>
* When you read a mileage, for example from Fort Collins to Pueblo, create only one
* entry in the mileages array, but add the edge to both cities.
* <p>
* First extract all the edges, then sort the edges by mileage, then add the edges
* associated with each node.
* @param filename the CSV file
*/
public abstract void readGraph(String filename);
/**
* Writes mileage graph to DOT file.
* <p>
* Traverses the data structures created above and writes nodes and edges in GraphViz format.
* You will build the GraphViz format into an {@code ArrayList}, which will then be written to file
* using the {@link GraphImplementation#writeFile(String, ArrayList)} method.
* <p>
* Use the provided example and the following directions to implement this method:
* <ul>
* <li> All attributes of nodes and edges that are identical are put into the header of the .dot file.
* <li> The nodes are labeled Node0, Node1, etc., in the same order as the input file,
* and they have city names as labels.
* <li> The edges are then written, in the format Node0 -> Node1, etc. and labeled with a distance and color.
* </ul>
* The edge color should be green for {@code ?100 miles}, blue for {@code ?200} miles,
* magenta for {@code ?300 miles}, and red otherwise.
* <p>
* HINT: Match the file format exactly as provided in order to pass automated grading!
* @param filename the output file name
*/
public abstract void writeGraph(String filename);
// Print graph in depth first search order
public abstract void depthFirst(String startCity);
// Print graph in breadth first search order
public abstract void breadthFirst(String startCity);
// Calculate and print shortest path
public abstract void shortestPath(String fromCity, String toCity);
}
Explanation / Answer
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
public class GraphImplementation extends GraphAbstract {
public static void main(String[] args) {
if (args.length != 2) {
System.err.println("usage: java GraphImplementation <distanceFile> <graphFile>");
System.exit(-1);
}
// Instantiate code
GraphImplementation impl = new GraphImplementation();
// Read distances chart
System.out.println("Reading Chart: " + args[0]);
impl.readGraph(args[0]);
System.out.println();
// Write distances graph
System.out.println("Writing Graph: " + args[1]);
impl.writeGraph(args[1]);
System.out.println();
// Print depth first search
System.out.println("Depth First Search:");
impl.depthFirst("Fort Collins");
System.out.println();
// Print breadth first search
System.out.println("Breadth First Search:");
impl.breadthFirst("Aspen");
System.out.println();
// EXTRA CREDIT: Print all shortest paths
System.out.println("Shortest Path: ");
for (int from = 0; from < cities.size(); from++) {
for (int to = 0; to < cities.size(); to++)
if (from != to) {
String fromCity = cities.get(from).name;
String toCity = cities.get(to).name;
impl.shortestPath(fromCity, toCity);
}
}
}
// Reads mileage chart from CSV file
public void readGraph(String filename) {
ArrayList<String> data = readFile(filename);
String[] cityNames = data.get(0).split(",");
for (String city : cityNames) {
if (!city.isEmpty()) {
cities.add(new GraphNode(city));
}
}
int fromIndex = 0;
for (GraphNode city : cities) {
String[] edgeData = data.get(fromIndex + 1).split(",");
for (int toIndex = fromIndex + 1; toIndex < cities.size(); toIndex++) {
if ((toIndex + 1 < edgeData.length) && edgeData[toIndex + 1].length() > 0) {
mileages.add(new GraphEdge(fromIndex, toIndex, Integer.parseInt(edgeData[toIndex + 1])));
city.edges.add(new GraphEdge(fromIndex, toIndex, Integer.parseInt(edgeData[toIndex + 1])));
cities.get(toIndex).edges
.add(new GraphEdge(toIndex, fromIndex, Integer.parseInt(edgeData[toIndex + 1])));
}
}
city.edges.sort(null);
fromIndex++;
}
mileages.sort(null);
}
public void writeGraph(String filename) {
ArrayList<String> output = new ArrayList<>();
output.add("digraph BST {");
output.add(" ratio = 1.0;");
output.add(" node [style=filled]");
output.add(" node [fillcolor=darkslateblue]");
output.add(" node [fixedsize=true]");
output.add(" node [shape=oval]");
output.add(" node [width=6]");
output.add(" node [height=4]");
output.add(" node [fontname=Arial]");
output.add(" node [fontsize=60]");
output.add(" node [fontcolor=white]");
output.add(" edge [dir=none]");
output.add(" edge [penwidth=24]");
output.add(" edge [fontname=Arial]");
output.add(" edge [fontsize=110]");
int cityIndex = 0;
for (GraphNode city: cities) {
output.add(" Node" + cityIndex + " [label="" + city.name + ""];");
cityIndex++;
}
for (GraphEdge edge: mileages) {
if (!(edge.fromIndex >= edge.toIndex)) {
String color;
if (edge.mileage <= 100) {
color = "green";
}
else if (edge.mileage <= 200) {
color = "blue";
}
else if (edge.mileage <= 300) {
color = "magenta";
}
else {
color = "red";
}
output.add(" Node" + edge.fromIndex + " -> Node" + edge.toIndex + " [label="" + edge.mileage + "" color="" + color + ""]");
}
}
output.add("}");
writeFile(filename, output);
}
private int getIndex(String city) {
int index;
for (index = 0; index < cities.size(); index++) {
if (cities.get(index).name.equals(city)) {
break;
}
}
return index;
}
public void depthFirst(String startCity) {
int index = getIndex(startCity);
depthFirst(index, new ArrayList<Integer>(cities.size()));
}
// Recursive helper method
public void depthFirst(int index, ArrayList<Integer> visited) {
visited.add(index);
System.out.println("Visited " + cities.get(index).name);
for (GraphEdge edge: cities.get(index).edges) {
boolean visitedCity = false;
for (int i = 0; i < visited.size(); i++) {
if (visited.get(i).equals(edge.toIndex)) {
visitedCity = true;
}
}
if (!visitedCity) {
depthFirst(edge.toIndex, visited);
}
}
}
public void breadthFirst(String startCity) {
ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
ArrayList<Integer> visited = new ArrayList<Integer>(cities.size());
int cityIndex = getIndex(startCity);
queue.add(cityIndex);
visited.add(cityIndex);
while (!queue.isEmpty()) {
cityIndex = queue.poll();
System.out.println("Visited " + cities.get(cityIndex).name);
for (GraphEdge e: cities.get(cityIndex).edges) {
boolean visitedCity = false;
for (int i = 0; i < visited.size(); i++) {
if (visited.get(i).equals(e.toIndex)) {
visitedCity = true;
}
}
if (!visitedCity) {
queue.offer(e.toIndex);
visited.add(e.toIndex);
}
}
}
}
public void shortestPath(String fromCity, String toCity) {
int from = getIndex(fromCity);
int to = getIndex(toCity);
ArrayList<Integer> min = new ArrayList<Integer>();
ArrayList<Integer> prev = new ArrayList<Integer>();
ArrayList<Integer> unv = new ArrayList<Integer>();
for (int i = 0; i < cities.size(); i++) {
min.add(Integer.MAX_VALUE);
prev.add(-1);
unv.add(i);
}
min.set(from, 0);
while (!unv.isEmpty()) {
Integer minSK = Integer.MAX_VALUE;
int unvIndex = -1;
for (int i = 0; i < unv.size(); i++) {
if (min.get(unv.get(i)) < minSK) {
minSK = min.get(unv.get(i));
unvIndex = i;
}
}
unv.remove(unvIndex);
int indexSK = min.indexOf(minSK);
// update shortest distances
for (GraphEdge e: cities.get(indexSK).edges) {
int cost = minSK + e.mileage;
if (cost < min.get(e.toIndex)) {
min.set(e.toIndex, cost);
prev.set(e.toIndex, indexSK);
}
}
}
System.out.println("[" + fromCity + ", " + toCity + "] (Mileage " + min.get(to) + ")");
}
// Helper functions
static ArrayList<String> readFile(String filename) {
ArrayList<String> contents = new ArrayList<>();
try(Scanner reader = new Scanner(new File(filename))) {
while (reader.hasNextLine()) {
String line = reader.nextLine().trim();
if (!line.isEmpty())
contents.add(line);
}
} catch (IOException e) {
System.err.println("Cannot read chart: " + filename);
}
return contents;
}
static void writeFile(String filename, ArrayList<String> contents) {
try(PrintWriter writer = new PrintWriter(filename)) {
for (String line : contents)
writer.println(line);
} catch (IOException e) {
System.err.println("Cannot write graph: " + filename);
}
}
}
------------------------------------------------------------------------------------------------
import java.util.ArrayList;
public abstract class GraphAbstract {
// Represents a graph edge
public class GraphEdge implements Comparable<GraphEdge> {
public int fromIndex; // index of "from" city
public int toIndex; // index of "to" city
public int mileage; // mileage between cities
public GraphEdge (int from, int to, int mileage) {
this.fromIndex = from;
this.toIndex = to;
this.mileage = mileage;
}
public int compareTo(GraphEdge edge) {
return this.mileage - edge.mileage;
}
}
// Represents a graph node (and incident edges)
public class GraphNode {
public String name; // City name
public ArrayList<GraphEdge> edges; // Distances
public GraphNode(String name) {
this.name = name;
edges = new ArrayList<>();
}
public boolean equals(Object object) {
return object instanceof GraphNode && ((GraphNode) object).name.equals(this.name);
}
}
// Graph data structures
public static ArrayList<GraphNode> cities = new ArrayList<>();
public static ArrayList<GraphEdge> mileages = new ArrayList<>();
public abstract void readGraph(String filename);
public abstract void writeGraph(String filename);
// Print graph in depth first search order
public abstract void depthFirst(String startCity);
// Print graph in breadth first search order
public abstract void breadthFirst(String startCity);
// Calculate and print shortest path
public abstract void shortestPath(String fromCity, String toCity);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.