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}