001package algs42; 002import stdlib.*; 003import algs35.ST; 004/* *********************************************************************** 005 * Compilation: javac SymbolDigraph.java 006 * Execution: java SymbolDigraph 007 * Dependencies: ST.java Digraph.java In.java 008 * 009 * % java SymbolDigraph routes.txt " " 010 * JFK 011 * MCO 012 * ATL 013 * ORD 014 * ATL 015 * HOU 016 * MCO 017 * LAX 018 * 019 *************************************************************************/ 020 021public class SymbolDigraph { 022 private final ST<String, Integer> st; // string -> index 023 private final String[] keys; // index -> string 024 private final Digraph G; 025 private final String delimiter; 026 027 public SymbolDigraph(String filename, String delimiter) { 028 this.delimiter = delimiter; 029 this.st = new ST<>(); 030 031 // First pass builds the index by reading strings to associate 032 // distinct strings with an index 033 In in = new In(filename); 034 while (in.hasNextLine()) { 035 String[] a = in.readLine().split(delimiter); 036 for (int i = 0; i < a.length; i++) { 037 if (!st.contains(a[i])) 038 st.put(a[i], st.size()); 039 } 040 } 041 042 // inverted index to get string keys in an aray 043 this.keys = new String[st.size()]; 044 for (String name : st.keys()) { 045 keys[st.get(name)] = name; 046 } 047 048 // second pass builds the digraph by connecting first vertex on each 049 // line to all others 050 this.G = new Digraph(st.size()); 051 in = new In(filename); 052 while (in.hasNextLine()) { 053 String[] a = in.readLine().split(delimiter); 054 int v = st.get(a[0]); 055 for (int i = 1; i < a.length; i++) { 056 int w = st.get(a[i]); 057 G.addEdge(v, w); 058 } 059 } 060 } 061 062 public boolean contains(String s) { 063 return st.contains(s); 064 } 065 066 public int index(String s) { 067 return st.get(s); 068 } 069 070 public String name(int v) { 071 return keys[v]; 072 } 073 074 public Digraph G() { 075 return G; 076 } 077 078 public String toString() { 079 StringBuilder s = new StringBuilder(); 080 String NEWLINE = System.getProperty("line.separator"); 081 s.append(G.V() + " vertices, " + G.E() + " edges " + NEWLINE); 082 for (int v = 0; v < G.V(); v++) { 083 s.append(name(v)); 084 for (int w : G.adj (v)) { 085 s.append(delimiter); 086 s.append(name(w)); 087 } 088 s.append(NEWLINE); 089 } 090 return s.toString(); 091 } 092 093 public static void main(String[] args) { 094 args = new String[] { "data/jobs.txt", "/" }; 095 096 String filename = args[0]; 097 String delimiter = args[1]; 098 SymbolDigraph sg = new SymbolDigraph(filename, delimiter); 099 StdOut.println (sg); 100 101 Digraph G = sg.G(); 102 while (!StdIn.isEmpty()) { 103 String t = StdIn.readLine(); 104 for (int v : G.adj(sg.index(t))) { 105 StdOut.println(" " + sg.name(v)); 106 } 107 } 108 } 109}