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}