-
Notifications
You must be signed in to change notification settings - Fork 3
/
SixDegreesKevinBacon.java
78 lines (57 loc) · 2 KB
/
SixDegreesKevinBacon.java
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
package Examples;
import Graphs.BreadthFirstSearch;
import Graphs.SymbolGraph;
import Graphs.UndirectedGraph;
import java.util.HashMap;
public class SixDegreesKevinBacon {
private BreadthFirstSearch breadthFirstSearch;
private SymbolGraph graph;
public SixDegreesKevinBacon(String pathToFile, String delimiter, String source) {
graph = new SymbolGraph(pathToFile, delimiter);
if (!graph.contains(source)) {
throw new Error("The from is not in the list.");
}
UndirectedGraph tempGraph = graph.graph();
BreadthFirstSearch breadthFirstSearch = new BreadthFirstSearch(tempGraph, graph.index(source));
HashMap m = new HashMap();
}
/**
* Given the path to the file, returns the degree
* between Kevin Bacon and the given actor/actress.
* We recommend using the file provided at
* http://algs4.cs.princeton.edu/41undirected/movies.txt,
* otherwise modifications are needed.
*
* @param pathToFile, the path to the file
*/
public SixDegreesKevinBacon(String pathToFile, String delimiter) {
this(pathToFile, delimiter, "Kevin Bacon");
}
/**
* Returns the degree of separation between the source
* and the given name.
*
* @param name, the name
*/
public int separation(String name) {
return breadthFirstSearch.distTo(graph.index(name));
}
/**
* Print the chain from the source to the given name
*
* @param name
*/
public void printChain(String name) {
if (!graph.contains(name)) {
System.out.println("The list doesn't contain " + name);
}
if (!breadthFirstSearch.hasPathTo(graph.index(name))) {
System.out.println("No path to " + name);
}
if (breadthFirstSearch.hasPathTo(graph.index(name))) {
for (Integer vertex : breadthFirstSearch.pathTo(graph.index(name))) {
System.out.println(graph.name(vertex));
}
}
}
}