Modify the Graph program given in the textbook (program 4.5.1) to create a program, SubGraph. It would take a filename and vertices as input arguments on the command line. It would create and print out a graph using the data specified in the file (as is done by the "Graph" program). And then it would also print out the subgraph of the graph formed by the vertices that are given on the command line. Please add Commenting (code documentation)

Note: The induced subgraph is the graph comprised of the specified vertices together with all edges from the original graph that connect any two of them.

• The input and output of the program should be similar to, or as specified by, the following sample run.

>more graph.txt A B A C C G A G H A B C B H

>java SubGraph graph.txt A C G The graph is A: B C G H B: A C H C: A B G G: A C H: A B The subgraph is A: C G C: A G G: A C

- DETE ILEPSID We also include the methods v() and E() in our API to provide to the client the number of vertices and edges in the graph. Similarly, the methods degree (), hasvertex (), and hasEdge () are useful in client code. We leave the implementation of these methods as exercises, but assume them to be in our Graph API. None of these design decisions are sacrosanct; they are simply the choices that we have made for the code in this book. Some other choices might be appropriate in various situations, and some decisions are still left to implementations. It is wise to carefully consider the choices that you make for design decisions like this and to be prepared to defend them. Graph (PROGRAM 4.5.1) implements this API. Its internal representation is a symbol table of sets: the keys are vertices and the values are the sets of neighborsthe vertices adjacent to the key. This representation uses the two data types ST and SET that we introduced in SECTION 4.4. It has three important properties: Clients can efficiently iterate over the graph vertices. Clients can efficiently iterate over a vertex's neighbors. Memory usage is proportional to the number of edges. A- symbol table set of vertex neighbors A BACH ( ). G AC H A B key value Symbol-table-of-sets graph representation The graph model shows Vertex "A" connected to vertices "H" "G." "B." and "C." Vertex "B" is connected to vertices "C" and "H." Vertex "C" is connected to vertices "A" and "G." The symbol table shows two columns labeled "vertex" and "set of neighbors." The data presented in the table is as follows: Vertex: A; set of neighbors: BCGH. Vertex: B; set of neighbors: A CH. Vertex: C; set of neighbors: A B G. Vertex: G; set of neighbors: A C. Vertex: H; set of neighbors: A B. The vertex "C" is labeled "key" and the set of neighbors A. B. G are marked "value." These properties follow immediately from basic properties of ST and SET. As you will see, these two iterators are at the heart of graph processing. Program 4.5.1 Graph data type Click here to view code image public class Graph private ST> st; public Graph() { st = new ST>(); } public void addEdge (String v, String w) { // Put vin w's SET and win y's SET. if (!st.contains (v)) 3t.put (v, new SET()); if (!st.contains (w)) st.put(w, new SET()); st.get (v).add(w); 676 D- 6 Aa 1 2 ACH ( ). AC A B H value Symbol-table-of-sets graph representation !!! OOO The graph model shows Vertex "A" connected to vertices "H," "G" "B." and "C." Vertex "B" is connected to vertices "C" and "H" Vertex "C" is connected to vertices "A" and "G." The symbol table shows two columns labeled "vertex" and "set of neighbors." The data presented in the table is as follows: Vertex: A: set of neighbors: B C GH. Vertex: B; set of neighbors: A CH. Vertex: C; set of neighbors: AB G. Vertex: G; set of neighbors: A C. Vertex: H; set of neighbors: A B. The vertex "C" is labeled "key" and the set of neighbors A, B, G are marked "value." These properties follow immediately from basic properties of ST and SET. As you will see, these two iterators are at the heart of graph processing. Program 4.5.1 Graph data type Click here to view code image public class Graph private ST> st; public Graph() { st = new ST>(); } public void addEdge (String v, String w) { // Put vin w's SET and win v's SET. if (!st.contains (v)) st.put (v, new SET(); if (!st.contains (w)) st.put(w, new SET()); st.get (v).add (w); st.get (w).add (v); public Iterable adjacent to (String v) { return st.get (v); } public Iterable vertices() { return st.keys); } // See Exercises 4.5.1-4 for v0), E(), degree (), // hasVertex), and hasEdge (). public static void main(String[] args) { // Read edges from standard input; print resulting graph. Graph G = new Graph(); while (!StdIn.isEmpty ( ) G.addEdge (Stdin.readString(), Stdin.readstring()); Stdout.print(G); 3t | symbol table of vertex neighbor sets This implementation uses ST and SET (see SECTION 4.4) to implement the graph data type. Clients build graphs by adding edges and process them by iterating over the vertices and then over the set of vertices adjacent to each vertex. See the text for toString() and a 676 DA 6 Aa 4 v- B st | symbol table of vertex neighbor sets This implementation uses ST and SET (see SECTION 4.4) to implement the graph data type. Clients build graphs by adding edges and process them by iterating over the vertices and then over the set of vertices adjacent to each vertex. See the text for toString() and a matching constructor that reads a graph from a file. more tinyGraph.txt #java Graph >(); In in = new In (filename); while (in.hasNextLine()) String line = in.readLine(); String[] names = line.split(delimiter); for (int i = 1; i > st; public Graph() { st = new ST>(); } public void addEdge (String v, String w) { // Put vin w's SET and win y's SET. if (!st.contains (v)) 3t.put (v, new SET()); if (!st.contains (w)) st.put(w, new SET()); st.get (v).add(w); 676 D- 6 Aa 1 2 ACH ( ). AC A B H value Symbol-table-of-sets graph representation !!! OOO The graph model shows Vertex "A" connected to vertices "H," "G" "B." and "C." Vertex "B" is connected to vertices "C" and "H" Vertex "C" is connected to vertices "A" and "G." The symbol table shows two columns labeled "vertex" and "set of neighbors." The data presented in the table is as follows: Vertex: A: set of neighbors: B C GH. Vertex: B; set of neighbors: A CH. Vertex: C; set of neighbors: AB G. Vertex: G; set of neighbors: A C. Vertex: H; set of neighbors: A B. The vertex "C" is labeled "key" and the set of neighbors A, B, G are marked "value." These properties follow immediately from basic properties of ST and SET. As you will see, these two iterators are at the heart of graph processing. Program 4.5.1 Graph data type Click here to view code image public class Graph private ST> st; public Graph() { st = new ST>(); } public void addEdge (String v, String w) { // Put vin w's SET and win v's SET. if (!st.contains (v)) st.put (v, new SET(); if (!st.contains (w)) st.put(w, new SET()); st.get (v).add (w); st.get (w).add (v); public Iterable adjacent to (String v) { return st.get (v); } public Iterable vertices() { return st.keys); } // See Exercises 4.5.1-4 for v0), E(), degree (), // hasVertex), and hasEdge (). public static void main(String[] args) { // Read edges from standard input; print resulting graph. Graph G = new Graph(); while (!StdIn.isEmpty ( ) G.addEdge (Stdin.readString(), Stdin.readstring()); Stdout.print(G); 3t | symbol table of vertex neighbor sets This implementation uses ST and SET (see SECTION 4.4) to implement the graph data type. Clients build graphs by adding edges and process them by iterating over the vertices and then over the set of vertices adjacent to each vertex. See the text for toString() and a 676 DA 6 Aa 4 v- B st | symbol table of vertex neighbor sets This implementation uses ST and SET (see SECTION 4.4) to implement the graph data type. Clients build graphs by adding edges and process them by iterating over the vertices and then over the set of vertices adjacent to each vertex. See the text for toString() and a matching constructor that reads a graph from a file. more tinyGraph.txt #java Graph >(); In in = new In (filename); while (in.hasNextLine()) String line = in.readLine(); String[] names = line.split(delimiter); for (int i = 1; i