Finish methods in GraphImplementation

Descriptions for what to do for each method can be found in GraphAbstract

// GraphAbstract.java - abstract class for graph assignment

import java.util.ArrayList;

public abstract class GraphAbstract {

// Represents a graph edge public class GraphEdge implements Comparable { 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 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 cities = new ArrayList<>(); public static ArrayList mileages = new ArrayList<>();

/** * Reads mileage chart from CSV file and builds lists of nodes (cities) and edges (distances). *

* The first line contains all the cities which should be represented as {@link GraphNode}s * The successive lines start with a city, followed by a list of mileages to other cities. *

* To avoid redundancy, not all the values are filled in, ignore empty entries. * 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. *

* 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. *

* 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. *

* Use the provided example and the following directions to implement this method: *

*
• All attributes of nodes and edges that are identical are put into the header of the .dot file. *
• The nodes are labeled Node0, Node1, etc., in the same order as the input file, * and they have city names as labels. *
• The edges are then written, in the format Node0 -> Node1, etc. and labeled with a distance and color. *

* The edge color should be green for {@code ?100 miles}, blue for {@code ?200} miles, * magenta for {@code ?300 miles}, and red otherwise. *

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

--------------------------------------------------------------------------------------------------------

// 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

readFile(filename);

}

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]");

// YOUR CODE HERE

// 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);

}

}

}