001package algs41; 002import stdlib.*; 003import algs35.ST; 004/* *********************************************************************** 005 * Compilation: javac SymbolGraph.java 006 * Execution: java SymbolGraph filename.txt delimiter 007 * Dependencies: ST.java Graph.java In.java StdIn.java StdOut.java 008 * Data files: http://algs4.cs.princeton.edu/41undirected/routes.txt 009 * http://algs4.cs.princeton.edu/41undirected/movies.txt 010 * 011 * % java SymbolGraph routes.txt " " 012 * JFK 013 * MCO 014 * ATL 015 * ORD 016 * LAX 017 * PHX 018 * LAS 019 * 020 * % java SymbolGraph movies.txt "/" 021 * Tin Men (1987) 022 * Hershey, Barbara 023 * Geppi, Cindy 024 * Jones, Kathy (II) 025 * Herr, Marcia 026 * ... 027 * Blumenfeld, Alan 028 * DeBoy, David 029 * Bacon, Kevin 030 * Woodsman, The (2004) 031 * Wild Things (1998) 032 * Where the Truth Lies (2005) 033 * Tremors (1990) 034 * ... 035 * Apollo 13 (1995) 036 * Animal House (1978) 037 * 038 *************************************************************************/ 039 040public class SymbolGraph { 041 private final ST<String, Integer> st; // string -> index 042 private final String[] keys; // index -> string 043 private final Graph G; 044 045 public SymbolGraph(String filename, String delimiter) { 046 st = new ST<>(); 047 048 // First pass builds the index by reading strings to associate 049 // distinct strings with an index 050 In in = new In(filename); 051 while (in.hasNextLine()) { 052 String[] a = in.readLine().split(delimiter); 053 for (int i = 0; i < a.length; i++) { 054 if (!st.contains(a[i])) 055 st.put(a[i], st.size()); 056 } 057 } 058 059 // inverted index to get string keys in an aray 060 keys = new String[st.size()]; 061 for (String name : st.keys()) { 062 keys[st.get(name)] = name; 063 } 064 065 // second pass builds the graph by connecting first vertex on each 066 // line to all others 067 G = new Graph(st.size()); 068 in = new In(filename); 069 while (in.hasNextLine()) { 070 String[] a = in.readLine().split(delimiter); 071 int v = st.get(a[0]); 072 for (int i = 1; i < a.length; i++) { 073 int w = st.get(a[i]); 074 G.addEdge(v, w); 075 } 076 } 077 } 078 079 public boolean contains(String s) { 080 return st.contains(s); 081 } 082 083 public int index(String s) { 084 return st.get(s); 085 } 086 087 public String name(int v) { 088 return keys[v]; 089 } 090 091 public Graph G() { 092 return G; 093 } 094 095 public String toString() { 096 StringBuilder s = new StringBuilder(); 097 String NEWLINE = System.getProperty("line.separator"); 098 s.append(G.V() + " vertices, " + G.E() + " edges " + NEWLINE); 099 for (int v = 0; v < G.V(); v++) { 100 s.append(name(v) + ": "); 101 for (int w : G.adj(v)) { 102 s.append(name(w) + " "); 103 } 104 s.append(NEWLINE); 105 } 106 return s.toString(); 107 } 108 109 public static void main(String[] args) { 110 //args = new String[] { "data/movies.txt", "/" }; 111 args = new String[] { "data/routes.txt", " " }; 112 113 String filename = args[0]; 114 String delimiter = args[1]; 115 SymbolGraph sg = new SymbolGraph(filename, delimiter); 116 StdOut.println (sg); 117 118 Graph G = sg.G(); 119 StdOut.println (G); 120 while (StdIn.hasNextLine()) { 121 String source = StdIn.readLine(); 122 if (sg.contains (source)) { 123 int s = sg.index(source); 124 for (int v : G.adj(s)) { 125 StdOut.println(" " + v + " " + sg.name(v)); 126 } 127 } else { 128 if (!"".equals(source)) StdOut.println(source + " not found"); 129 } 130 } 131 } 132}