Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Hey guys I need help with this question Create a package called graphSymbol Copy SymbolGraph.java (Links to an external site.)Links to an external site. into

Hey guys I need help with this question

  • Create a package called graphSymbol
  • Copy SymbolGraph.java (Links to an external site.)Links to an external site. into the package
  • Modify the main method so that it uses hard-coded values instead of command line argument Use routes.txt (Links to an external site.)Links to an external site. to create the SymbolGraph.
  • Run it ( execute the main method of SymbolGraph ) Youll see the output Done reading src/graphDirected/routes.txt There is no prompt. Nonetheless, enter JFK and press enter Enter LAX and press enter, etc.

Expected Output: Done reading src/graphSymbol/routes.txt JFK ORD ATL MCO LAX LAS PHX

  • What does it mean that ORD, ATL, and MCO are listed when entering JFK?
  • What methods does SymbolGraph provide except for main?

Part 2: Create a class called RouteFinder.

It should allow the user to specify a departure airport

If the specified airport is not listed in routes.txt a message should be printed that

the airport could not be found. Otherwise, list the shortest paths to all the destinations

that can be reached from the departure airport. In this context, the shortest path

means the route with the least amount of landings between departure and destination.

Expected Output:

Done reading src/graphSymbol/routes.txt

Destination: JFK

The following destinations can be reached from JFK:

JFK: JFK MCO: JFK MCO ORD: JFK ORD DEN: JFK ORD DEN HOU: JFK ORD HOU DFW: JFK ORD DFW PHX: JFK ORD PHX ATL: JFK ATL LAX: JFK ORD PHX LAX LAS: JFK ORD PHX LAS

Part 3 - Extra Challenge: What would you do if you wanted to use a digraph with vertex names instead of vertex numbers?

Here is the SG.Java

/****************************************************************************** * Compilation: javac SymbolGraph.java * Execution: java SymbolGraph filename.txt delimiter * Dependencies: ST.java Graph.java In.java StdIn.java StdOut.java * Data files: https://algs4.cs.princeton.edu/41graph/routes.txt * https://algs4.cs.princeton.edu/41graph/movies.txt * https://algs4.cs.princeton.edu/41graph/moviestiny.txt * https://algs4.cs.princeton.edu/41graph/moviesG.txt * https://algs4.cs.princeton.edu/41graph/moviestopGrossing.txt * * % java SymbolGraph routes.txt " " * JFK * MCO * ATL * ORD * LAX * PHX * LAS * * % java SymbolGraph movies.txt "/" * Tin Men (1987) * Hershey, Barbara * Geppi, Cindy * Jones, Kathy (II) * Herr, Marcia * ... * Blumenfeld, Alan * DeBoy, David * Bacon, Kevin * Woodsman, The (2004) * Wild Things (1998) * Where the Truth Lies (2005) * Tremors (1990) * ... * Apollo 13 (1995) * Animal House (1978) * * * Assumes that input file is encoded using UTF-8. * % iconv -f ISO-8859-1 -t UTF-8 movies-iso8859.txt > movies.txt * ******************************************************************************/ /** * The {@code SymbolGraph} class represents an undirected graph, where the * vertex names are arbitrary strings. * By providing mappings between string vertex names and integers, * it serves as a wrapper around the * {@link Graph} data type, which assumes the vertex names are integers * between 0 and V - 1. * It also supports initializing a symbol graph from a file. * 

* This implementation uses an {@link ST} to map from strings to integers, * an array to map from integers to strings, and a {@link Graph} to store * the underlying graph. * The indexOf and contains operations take time * proportional to log V, where V is the number of vertices. * The nameOf operation takes constant time. *

* For additional documentation, see Section 4.1 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class SymbolGraph { private ST st; // string -> index private String[] keys; // index -> string private Graph graph; // the underlying graph /** * Initializes a graph from a file using the specified delimiter. * Each line in the file contains * the name of a vertex, followed by a list of the names * of the vertices adjacent to that vertex, separated by the delimiter. * @param filename the name of the file * @param delimiter the delimiter between fields */ public SymbolGraph(String filename, String delimiter) { st = new ST(); // First pass builds the index by reading strings to associate // distinct strings with an index In in = new In(filename); // while (in.hasNextLine()) { while (!in.isEmpty()) { String[] a = in.readLine().split(delimiter); for (int i = 0; i < a.length; i++) { if (!st.contains(a[i])) st.put(a[i], st.size()); } } // inverted index to get string keys in an array keys = new String[st.size()]; for (String name : st.keys()) { keys[st.get(name)] = name; } // second pass builds the graph by connecting first vertex on each // line to all others graph = new Graph(st.size()); in = new In(filename); while (in.hasNextLine()) { String[] a = in.readLine().split(delimiter); int v = st.get(a[0]); for (int i = 1; i < a.length; i++) { int w = st.get(a[i]); graph.addEdge(v, w); } } } /** * Does the graph contain the vertex named {@code s}? * @param s the name of a vertex * @return {@code true} if {@code s} is the name of a vertex, and {@code false} otherwise */ public boolean contains(String s) { return st.contains(s); } /** * Returns the integer associated with the vertex named {@code s}. * @param s the name of a vertex * @return the integer (between 0 and V - 1) associated with the vertex named {@code s} * @deprecated Replaced by {@link #indexOf(String)}. */ @Deprecated public int index(String s) { return st.get(s); } /** * Returns the integer associated with the vertex named {@code s}. * @param s the name of a vertex * @return the integer (between 0 and V - 1) associated with the vertex named {@code s} */ public int indexOf(String s) { return st.get(s); } /** * Returns the name of the vertex associated with the integer {@code v}. * @param v the integer corresponding to a vertex (between 0 and V - 1) * @return the name of the vertex associated with the integer {@code v} * @throws IllegalArgumentException unless {@code 0 <= v < V} * @deprecated Replaced by {@link #nameOf(int)}. */ @Deprecated public String name(int v) { validateVertex(v); return keys[v]; } /** * Returns the name of the vertex associated with the integer {@code v}. * @param v the integer corresponding to a vertex (between 0 and V - 1) * @throws IllegalArgumentException unless {@code 0 <= v < V} * @return the name of the vertex associated with the integer {@code v} */ public String nameOf(int v) { validateVertex(v); return keys[v]; } /** * Returns the graph assoicated with the symbol graph. It is the client's responsibility * not to mutate the graph. * @return the graph associated with the symbol graph * @deprecated Replaced by {@link #graph()}. */ @Deprecated public Graph G() { return graph; } /** * Returns the graph assoicated with the symbol graph. It is the client's responsibility * not to mutate the graph. * @return the graph associated with the symbol graph */ public Graph graph() { return graph; } // throw an IllegalArgumentException unless {@code 0 <= v < V} private void validateVertex(int v) { int V = graph.V(); if (v < 0 || v >= V) throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1)); } /** * Unit tests the {@code SymbolGraph} data type. * * @param args the command-line arguments */ public static void main(String[] args) { String filename = args[0]; String delimiter = args[1]; SymbolGraph sg = new SymbolGraph(filename, delimiter); Graph graph = sg.graph(); while (StdIn.hasNextLine()) { String source = StdIn.readLine(); if (sg.contains(source)) { int s = sg.index(source); for (int v : graph.adj(s)) { StdOut.println(" " + sg.name(v)); } } else { StdOut.println("input not contain '" + source + "'"); } } } }

and

here is the routes.txt

JFK MCO ORD DEN ORD HOU DFW PHX JFK ATL ORD DFW ORD PHX ATL HOU DEN PHX PHX LAX JFK ORD DEN LAS DFW HOU ORD ATL LAS LAX ATL MCO HOU MCO LAS PHX

Please help

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Professional Microsoft SQL Server 2012 Administration

Authors: Adam Jorgensen, Steven Wort

1st Edition

1118106881, 9781118106884

More Books

Students also viewed these Databases questions

Question

Was the treatment influenced by being novel or disruptive?

Answered: 1 week ago