001package algs41;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac DegreesOfSeparation.java
005 *  Execution:    java DegreesOfSeparation filename delimiter source
006 *  Dependencies: SymbolGraph.java Graph.java BreadthFirstPaths.java StdOut.java
007 *  Data files:   http://algs4.cs.princeton.edu/41undirected/routes.txt
008 *                http://algs4.cs.princeton.edu/41undirected/movies.txt
009 *
010 *
011 *  %  java DegreesOfSeparation routes.txt " " "JFK"
012 *  LAS
013 *     JFK
014 *     ORD
015 *     DEN
016 *     LAS
017 *  DFW
018 *     JFK
019 *     ORD
020 *     DFW
021 *  EWR
022 *     Not in database.
023 *
024 *  % java DegreesOfSeparation movies.txt "/" "Bacon, Kevin"
025 *  Kidman, Nicole
026 *     Bacon, Kevin
027 *     Woodsman, The (2004)
028 *     Grier, David Alan
029 *     Bewitched (2005)
030 *     Kidman, Nicole
031 *  Grant, Cary
032 *     Bacon, Kevin
033 *     Planes, Trains & Automobiles (1987)
034 *     Martin, Steve (I)
035 *     Dead Men Don't Wear Plaid (1982)
036 *     Grant, Cary
037 *
038 *  % java DegreesOfSeparation movies.txt "/" "Animal House (1978)"
039 *  Titanic (1997)
040 *     Animal House (1978)
041 *     Allen, Karen (I)
042 *     Raiders of the Lost Ark (1981)
043 *     Taylor, Rocky (I)
044 *     Titanic (1997)
045 *  To Catch a Thief (1955)
046 *     Animal House (1978)
047 *     Vernon, John (I)
048 *     Topaz (1969)
049 *     Hitchcock, Alfred (I)
050 *     To Catch a Thief (1955)
051 *
052 *************************************************************************/
053
054public class DegreesOfSeparation {
055        public static void main(String[] args) {
056                args =  new String[] { "data/routes.txt", " ", "JFK" };
057                StdIn.fromString ("LAS\nDEN\n");
058
059//              args = new String[] { "data/movies.txt", "/", "Bacon, Kevin" };
060//              StdIn.fromString (""
061//                              + "Kidman, Nicole\n"
062//                              + "Belushi, John\n"
063//                              + "Winslet, Kate\n"
064//                              + "Grant, Cary\n"
065//                              + "Olofsson, Joakim\n"
066//                              + "Bacon, Kevin\n"
067//                              );
068
069                String filename  = args[0];
070                String delimiter = args[1];
071                String source    = args[2];
072
073                // StdOut.println("Source: " + source);
074
075                SymbolGraph sg = new SymbolGraph(filename, delimiter);
076                Graph G = sg.G();
077                if (!sg.contains(source)) {
078                        StdOut.println(source + " not in database." + G.V());
079                        return;
080                }
081
082                int s = sg.index(source);
083                //G.toGraphviz ("g.png");
084                BreadthFirstPaths bfs = new BreadthFirstPaths(G, s);
085                //DepthFirstPaths bfs = new DepthFirstPaths(G, s);
086
087                while (!StdIn.isEmpty()) {
088                        String sink = StdIn.readLine();
089                        if (sg.contains(sink)) {
090                                StdOut.println(sink + ":");
091                                int t = sg.index(sink);
092                                if (bfs.hasPathTo(t)) {
093                                        for (int v : bfs.pathTo(t)) {
094                                                StdOut.println("   " + sg.name(v));
095                                        }
096                                } else {
097                                        StdOut.println(sink + " not connected");
098                                }
099                        } else {
100                                if (!"".equals (sink)) StdOut.println(sink + " not in database..");
101                        }
102                }
103        }
104}