Question

public class Graph
{
   private ST<String, SET<String>> st;

   public Graph()
   {  st = new ST<String, SET<String>>();  }

   public void addEdge(String v, String w)
   {  // Put v in w's SET and w in v's SET.
      if (!st.contains(v)) st.put(v, new SET<String>());
      if (!st.contains(w)) st.put(w, new SET<String>());
      st.get(v).add(w);
      st.get(w).add(v);
   }

   public Iterable<String> adjacentTo(String v)
   {  return st.get(v);  }

   public Iterable<String> vertices()
   {  return st.keys();  }

   // See Exercises 4.5.1-4 for V(), 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);
   }
}

2. 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. [MO7.2]

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

Answer 1

Code:

package graph;

import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class SubGraph
{
   private ST<String, SET<String>> st;

   // number of edges
   private int E;

   public SubGraph()
   { st = new ST<String, SET<String>>(); }

   public SubGraph(String FileName)
   {
       st = new ST<String, SET<String>>();
       File file = new File(FileName);
       Scanner scanner = null;
       if (file.exists()) {
           FileInputStream fis = null;
       try {
           fis = new FileInputStream(file);
       } catch (FileNotFoundException e) {
           e.printStackTrace();
       }
           scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
       }
       while (scanner.hasNextLine()) {
           String line = scanner.nextLine();
           String[] names = line.split(" ");
           for (int i = 1; i < names.length; i++) {
               addEdge(names[0], names[i]);
           }
       }
   }

   public void addEdge(String v, String w)
   { // Put v in w's SET and w in v's SET.
      if (!st.contains(v)) st.put(v, new SET<String>());
      if (!st.contains(w)) st.put(w, new SET<String>());
      st.get(v).add(w);
      st.get(w).add(v);
   }

   public boolean hasEdge(String v, String w) {
       return st.get(v).contains(w);
   }

   public String toString() {
       StringBuilder s = new StringBuilder();
       for (String v : st) {
           s.append(v + ": ");
           for (String w : st.get(v)) {
               s.append(w + " ");
           }
           s.append('\n');
       }
       return s.toString();
   }

   public Iterable<String> adjacentTo(String v)
   { return st.get(v); }

   public Iterable<String> vertices()
   { return st.keys(); }

   public static void main(String[] args)
   {
      SubGraph G = new SubGraph(args[0]);
      System.out.println("The graph is");
      System.out.println(G.toString());
    
      SubGraph SG = new SubGraph();
    
      for(int i = 1;i < args.length; i++)
      {
          for(int j = 1; j< args.length;j++)
              if(G.hasEdge(args[i], args[j]))
                  SG.addEdge(args[i], args[j]);
      }
    
      System.out.println("\nThe subgraph is");
      System.out.println(SG.toString());
   }
}

CommandLine Arguments:

graph.txt A C G

Output:

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

Note:

1. Place the file 'graph.txt' in the working directory.