DegreesOfSeparation.java
5.35 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
/******************************************************************************
* Compilation: javac DegreesOfSeparation.java
* Execution: java DegreesOfSeparation filename delimiter source
* Dependencies: SymbolGraph.java Graph.java BreadthFirstPaths.java StdOut.java
* Data files: http://algs4.cs.princeton.edu/41graph/routes.txt
* http://algs4.cs.princeton.edu/41graph/movies.txt
*
*
* % java DegreesOfSeparation routes.txt " " "JFK"
* LAS
* JFK
* ORD
* DEN
* LAS
* DFW
* JFK
* ORD
* DFW
* EWR
* Not in database.
*
* % java DegreesOfSeparation movies.txt "/" "Bacon, Kevin"
* Kidman, Nicole
* Bacon, Kevin
* Woodsman, The (2004)
* Grier, David Alan
* Bewitched (2005)
* Kidman, Nicole
* Grant, Cary
* Bacon, Kevin
* Planes, Trains & Automobiles (1987)
* Martin, Steve (I)
* Dead Men Don't Wear Plaid (1982)
* Grant, Cary
*
* % java DegreesOfSeparation movies.txt "/" "Animal House (1978)"
* Titanic (1997)
* Animal House (1978)
* Allen, Karen (I)
* Raiders of the Lost Ark (1981)
* Taylor, Rocky (I)
* Titanic (1997)
* To Catch a Thief (1955)
* Animal House (1978)
* Vernon, John (I)
* Topaz (1969)
* Hitchcock, Alfred (I)
* To Catch a Thief (1955)
*
******************************************************************************/
package edu.princeton.cs.algs4;
/**
* The {@code DegreesOfSeparation} class provides a client for finding
* the degree of separation between one distinguished individual and
* every other individual in a social network.
* As an example, if the social network consists of actors in which
* two actors are connected by a link if they appeared in the same movie,
* and Kevin Bacon is the distinguished individual, then the client
* computes the Kevin Bacon number of every actor in the network.
* <p>
* The running time is proportional to the number of individuals and
* connections in the network. If the connections are given implicitly,
* as in the movie network example (where every two actors are connected
* if they appear in the same movie), the efficiency of the algorithm
* is improved by allowing both movie and actor vertices and connecting
* each movie to all of the actors that appear in that movie.
* <p>
* For additional documentation,
* see <a href="http://algs4.cs.princeton.edu/41graph">Section 4.1</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class DegreesOfSeparation {
// this class cannot be instantiated
private DegreesOfSeparation() { }
/**
* Reads in a social network from a file, and then repeatedly reads in
* individuals from standard input and prints out their degrees of
* separation.
* Takes three command-line arguments: the name of a file,
* a delimiter, and the name of the distinguished individual.
* Each line in the file contains the name of a vertex, followed by a
* list of the names of the vertices adjacent to that vertex,
* separated by the delimiter.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
String filename = args[0];
String delimiter = args[1];
String source = args[2];
// StdOut.println("Source: " + source);
SymbolGraph sg = new SymbolGraph(filename, delimiter);
Graph G = sg.graph();
if (!sg.contains(source)) {
StdOut.println(source + " not in database.");
return;
}
int s = sg.indexOf(source);
BreadthFirstPaths bfs = new BreadthFirstPaths(G, s);
while (!StdIn.isEmpty()) {
String sink = StdIn.readLine();
if (sg.contains(sink)) {
int t = sg.indexOf(sink);
if (bfs.hasPathTo(t)) {
for (int v : bfs.pathTo(t)) {
StdOut.println(" " + sg.nameOf(v));
}
}
else {
StdOut.println("Not connected");
}
}
else {
StdOut.println(" Not in database.");
}
}
}
}
/******************************************************************************
* Copyright 2002-2016, Robert Sedgewick and Kevin Wayne.
*
* This file is part of algs4.jar, which accompanies the textbook
*
* Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
* Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
* http://algs4.cs.princeton.edu
*
*
* algs4.jar is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* algs4.jar is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with algs4.jar. If not, see http://www.gnu.org/licenses.
******************************************************************************/