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}