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

 resources/MileagesSmall.csv MileageSmall.dot

Here is the output you should see from your program, when it is working correctly:

 digraph BST { ratio = 1.0; node [style=filled] node [fillcolor=darkslateblue] node [fixedsize=true] node [shape=oval] node [width=6] node [height=4] node [fontname=Arial] node [fontsize=60] node [fontcolor=white] edge [dir=none] edge [penwidth=24] edge [fontname=Arial] edge [fontsize=110] Node0 [label="Aspen"]; Node1 [label="Boulder"]; Node2 [label="Breckenridge"]; Node3 [label="Craig"]; Node4 [label="Denver"]; Node5 [label="Durango"]; Node6 [label="Fort Collins"]; Node7 [label="Pueblo"]; Node8 [label="Snowmass"]; Node9 [label="Telluride"]; Node0 -> Node8 [label="8" color="green"] Node1 -> Node4 [label="28" color="green"] Node1 -> Node6 [label="55" color="green"] Node4 -> Node6 [label="64" color="green"] Node2 -> Node4 [label="81" color="green"] Node1 -> Node2 [label="99" color="green"] Node4 -> Node7 [label="112" color="blue"] Node5 -> Node9 [label="120" color="blue"] Node2 -> Node8 [label="136" color="blue"] Node1 -> Node7 [label="146" color="blue"] Node3 -> Node8 [label="156" color="blue"] Node0 -> Node3 [label="158" color="blue"] Node2 -> Node7 [label="190" color="blue"] Node3 -> Node4 [label="198" color="blue"] Node0 -> Node9 [label="248" color="magenta"] }

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:

 $ cd path/to/MileageSmall.dot $ dot -Tpng MileageSmall.dot > MileageSmall.png

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

for (int to = 0; 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

cities.add(new GraphNode(line1[i]));

}

for(int j = 1; j

String[] edgeLine = myCities.get(j).split(",");

for(int i = 1; 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 { 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); }

Aspen Durango Boulder 158 248120 8 Craig 28 Breckenridge Telluride 156 55198 13681 146 190 Snowmass Denver 64 112 Fort Collins Pueblo