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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package edu.caltech.cs2.project08;
import edu.caltech.cs2.datastructures.Graph;
import org.hamcrest.MatcherAssert;
import org.hamcrest.collection.IsIterableContainingInAnyOrder;
import org.junit.jupiter.api.*;
import java.io.File;
import java.io.FileNotFoundException;
import java.time.Duration;
import java.util.*;
import static org.junit.jupiter.api.Assertions.*;
@Tag("C")
@DisplayName("Test graph of shared appearances in Marvel comic books (MarvelTests)")
public class MarvelTests {
private static Graph<String, Integer> MARVEL_GRAPH;
private static final int COMMON_TIMEOUT_MS = 1500;
@BeforeAll
public static void populateMarvelGraph() {
MARVEL_GRAPH = new Graph<>();
Set<String> characters = new HashSet<>();
Map<String, List<String>> books = new HashMap<>();
try {
MarvelParser.parseData("data/marvel/marvel.tsv", characters, books);
} catch (Exception e) {
fail("Could not read input file.");
}
for (String c : characters) {
MARVEL_GRAPH.addVertex(c);
}
for (String book : books.keySet()) {
// This will add symmetric edges automatically - no need to add undirected edge
for (String c1 : books.get(book)) {
for (String c2 : books.get(book)) {
if (!c1.equals(c2)) {
Integer num = MARVEL_GRAPH.adjacent(c1, c2);
if (num == null) {
num = 0;
}
MARVEL_GRAPH.addEdge(c1, c2, num + 1);
}
}
}
}
}
@Test
@Order(0)
@DisplayName("Test that characters with no co-appearances do not have neighbors - neighbor isEmpty")
public void testSingletons() {
List<String> singletons = new ArrayList<>();
for (String c : MARVEL_GRAPH.vertices()) {
if (MARVEL_GRAPH.neighbors(c).isEmpty()) {
singletons.add(c);
}
}
loadAndMatch(singletons, "data/marvel/singletons_output");
}
@Test
@Order(1)
@DisplayName("Look for characters that appear with many other characters - neighbor size")
public void testPopular() {
List<String> populars = new ArrayList<>();
for (String c : MARVEL_GRAPH.vertices()) {
if (MARVEL_GRAPH.neighbors(c).size() > 20) {
populars.add(c);
}
}
loadAndMatch(populars, "data/marvel/popular_output");
}
@Test
@Order(2)
@DisplayName("Test that there are no loops (self-edges) in the graph")
public void testNoLoops() {
for (String c : MARVEL_GRAPH.vertices()) {
assertNull(MARVEL_GRAPH.adjacent(c, c),
"There is a loop (self-edge) in the graph, when there should be none.");
}
}
// THIS TEST MUST BE RUN LAST - IT HAS SIDE EFFECTS ON THE STATIC GRAPH
@Test
@Order(3)
@DisplayName("Look for co-appearances that appear in many issues together - edge weights")
public void testCommon() {
Assertions.assertTimeout(Duration.ofMillis(COMMON_TIMEOUT_MS), this::runCommon);
}
public void runCommon() {
List<String> common = new ArrayList<>();
for (String c1 : MARVEL_GRAPH.vertices()) {
Set<String> toRemove = new HashSet<>();
for (String c2 : MARVEL_GRAPH.neighbors(c1)) {
Integer edge = MARVEL_GRAPH.adjacent(c1, c2);
Integer symedge = MARVEL_GRAPH.adjacent(c2, c1);
assertNotNull(edge, "An existing edge is null");
assertNotNull(symedge, "An existing edge is not symmetric in the graph");
toRemove.add(c2);
// Sort here to ignore dependency on hashing order
if (edge > 80) {
if (c1.compareTo(c2) < 0) {
common.add(c1.strip() + " --" + edge + "-- " + c2.strip());
}
else {
common.add(c2.strip() + " --" + edge + "-- " + c1.strip());
}
}
}
// Process removals separately to prevent modifying neighbors while iterating on it
for (String c2 : toRemove) {
Integer symedge = MARVEL_GRAPH.adjacent(c2, c1);
MARVEL_GRAPH.removeEdge(c1, c2);
assertNull(MARVEL_GRAPH.adjacent(c1, c2), "An edge is not null after removal");
assertEquals(symedge, MARVEL_GRAPH.adjacent(c2, c1), "An edge is null after its symmetric edge is removed");
MARVEL_GRAPH.removeEdge(c2, c1);
assertNull(MARVEL_GRAPH.adjacent(c2, c1), "An edge is not null after removal");
}
assertTrue(MARVEL_GRAPH.neighbors(c1).isEmpty(), "After removing all of a vertex's neighbors, neighbors() is non-empty");
}
loadAndMatch(common, "data/marvel/common_output");
}
private void loadAndMatch(List<String> actual, String filename) {
List<String> expected = new ArrayList<>();
Scanner fr = null;
try {
fr = new Scanner(new File(filename));
} catch (FileNotFoundException e) {
fail("Could not open test results file.");
}
while (fr.hasNextLine()) {
String l = fr.nextLine();
// is edge - sort to remove dependence on directionality for correctness
if (l.contains("--")) {
String[] spl = l.split("--");
String v1 = spl[0].strip();
String v2 = spl[2].strip();
String e = spl[1];
if (v1.compareTo(v2) < 0) {
l = v1 + " --" + e + "-- " + v2;
}
else {
l = v2 + " --" + e + "-- " + v1;
}
}
expected.add(l);
}
MatcherAssert.assertThat(actual,
IsIterableContainingInAnyOrder.containsInAnyOrder(expected.toArray()));
}
}