1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.grouplens.grapht.graph;
21
22 import com.google.common.base.Function;
23 import com.google.common.base.Functions;
24 import com.google.common.base.Predicate;
25 import com.google.common.base.Predicates;
26 import com.google.common.collect.Maps;
27 import org.junit.Test;
28
29 import javax.annotation.Nullable;
30 import java.util.HashMap;
31 import java.util.Map;
32
33 import static org.hamcrest.Matchers.*;
34 import static org.junit.Assert.assertThat;
35
36
37
38
39 public class TestDAGNode {
40 @Test
41 public void testBasicLabel() {
42 DAGNode<String,String> node = DAGNode.singleton("foo");
43 assertThat(node, notNullValue());
44 assertThat(node.getLabel(), equalTo("foo"));
45 assertThat(node.getOutgoingEdges(), hasSize(0));
46 assertThat(node.getReachableNodes(),
47 contains(node));
48 assertThat(node.getOutgoingEdgeWithLabel("wombat"),
49 nullValue());
50 }
51
52 @Test
53 public void testSingleEdge() {
54 DAGNode<String,String> foo = DAGNode.singleton("foo");
55 DAGNodeBuilder<String,String> bld = DAGNode.newBuilder("bar");
56 DAGNode<String,String> bar = bld.addEdge(foo, "wombat")
57 .build();
58
59 assertThat(bar.getLabel(), equalTo("bar"));
60 assertThat(bar.getOutgoingEdges(), hasSize(1));
61 DAGEdge<String,String> e = bar.getOutgoingEdges().iterator().next();
62 assertThat(e.getLabel(), equalTo("wombat"));
63 assertThat(e.getTail().getLabel(), equalTo("foo"));
64 assertThat(e.getTail().getOutgoingEdges(), hasSize(0));
65 assertThat(bar.getReachableNodes(),
66 containsInAnyOrder(foo, bar));
67 assertThat(bar.getSortedNodes(),
68 contains(foo, bar));
69 assertThat(bar.getOutgoingEdgeWithLabel("wombat").getTail(),
70 equalTo(foo));
71 }
72
73 @Test
74 public void testGetReverseEdge() {
75 DAGNode<String,String> foo = DAGNode.singleton("foo");
76 DAGNodeBuilder<String,String> bld = DAGNode.newBuilder("bar");
77 bld.addEdge(foo, "wombat");
78 DAGNode<String,String> bar = bld.build();
79
80 assertThat(bar.getIncomingEdges(foo),
81 contains(DAGEdge.create(bar, foo, "wombat")));
82 }
83
84 @Test
85 public void testGetTwoReverseEdges() {
86 DAGNode<String,String> foo = DAGNode.singleton("foo");
87
88 DAGNodeBuilder<String,String> bld = DAGNode.newBuilder("bar");
89 DAGNode<String,String> bar = bld.addEdge(foo, "wombat").build();
90
91 bld = DAGNode.newBuilder("blatz");
92 DAGNode<String,String> blatz = bld.addEdge(foo, "skunk").build();
93
94 bld = DAGNode.newBuilder("head");
95 DAGNode<String,String> head = bld.addEdge(bar, "wumpus")
96 .addEdge(blatz, "woozle")
97 .build();
98
99 assertThat(head.getOutgoingEdges(),
100 hasSize(2));
101
102 assertThat(head.getIncomingEdges(foo),
103 containsInAnyOrder(DAGEdge.create(bar, foo, "wombat"),
104 DAGEdge.create(blatz, foo, "skunk")));
105 assertThat(head.getReachableNodes(),
106 containsInAnyOrder(foo, bar, blatz, head));
107 }
108
109 @Test
110 public void testReplaceSingleNode() {
111 DAGNode<String,String> foo = DAGNode.singleton("foo");
112 DAGNode<String,String> bar = DAGNode.singleton("bar");
113 Map<DAGNode<String,String>,DAGNode<String,String>> mem = Maps.newHashMap();
114 DAGNode<String,String> replaced = foo.replaceNode(foo, bar, mem);
115 assertThat(replaced, equalTo(bar));
116 assertThat(mem, hasEntry(foo, bar));
117 }
118
119 @Test
120 public void testReplaceAbsentNode() {
121 DAGNode<String,String> foo = DAGNode.singleton("foo");
122 DAGNode<String,String> bar = DAGNode.singleton("bar");
123 DAGNode<String,String> blatz = DAGNode.singleton("blatz");
124 Map<DAGNode<String,String>,DAGNode<String,String>> mem = Maps.newHashMap();
125 DAGNode<String,String> replaced = foo.replaceNode(blatz, bar, mem);
126 assertThat(replaced, equalTo(foo));
127 assertThat(mem.size(), equalTo(0));
128 }
129
130 @Test
131 public void testReplaceEdgeNode() {
132 DAGNode<String,String> foo = DAGNode.singleton("foo");
133 DAGNode<String,String> bar = DAGNode.singleton("bar");
134 DAGNode<String,String> graph = DAGNode.<String,String>newBuilder("graph")
135 .addEdge(foo, "wombat")
136 .build();
137 Map<DAGNode<String,String>,DAGNode<String,String>> mem = Maps.newHashMap();
138 DAGNode<String,String> replaced = graph.replaceNode(foo, bar, mem);
139 assertThat(replaced, not(equalTo(graph)));
140 assertThat(mem, hasEntry(foo, bar));
141 assertThat(mem, hasEntry(graph, replaced));
142 assertThat(replaced.getAdjacentNodes(), contains(bar));
143 }
144
145 @Test
146 public void testReplaceDualUseNode() {
147 DAGNode<String,String> foo, fooP, bar, blatz, graph;
148 foo = DAGNode.singleton("foo");
149
150 fooP = DAGNode.<String,String>newBuilder("foo'")
151 .addEdge(foo, "-> foo")
152 .build();
153 bar = DAGNode.<String,String>newBuilder("bar")
154 .addEdge(fooP, "bar -> foo")
155 .build();
156 blatz = DAGNode.<String,String>newBuilder("blatz")
157 .addEdge(fooP, "blatz -> foo")
158 .build();
159 graph = DAGNode.<String,String>newBuilder("graph")
160 .addEdge(bar, "-> bar")
161 .addEdge(blatz, "-> blatz")
162 .build();
163
164 DAGNode<String,String> foo2 = DAGNode.singleton("foo2");
165 HashMap<DAGNode<String,String>,DAGNode<String,String>> memory = Maps.newHashMap();
166 DAGNode<String,String> replaced = graph.replaceNode(foo, foo2, memory);
167 assertThat(replaced, not(sameInstance(graph)));
168
169 assertThat(replaced.getReachableNodes(),
170 hasSize(5));
171 assertThat(foo2, isIn(replaced.getReachableNodes()));
172 assertThat(foo, not(isIn(replaced.getReachableNodes())));
173 assertThat(fooP, not(isIn(replaced.getReachableNodes())));
174 assertThat(replaced.getSortedNodes().get(0),
175 equalTo(foo2));
176 assertThat(replaced.getSortedNodes().get(1).getLabel(),
177 equalTo("foo'"));
178 }
179
180 @Test
181 public void testTransformEdgeNoop() {
182 DAGNode<String,String> foo = DAGNode.singleton("foo");
183 DAGNode<String,String> graph = DAGNode.<String,String>newBuilder("graph")
184 .addEdge(foo, "wombat")
185 .build();
186 DAGNode<String,String> g2 = graph.transformEdges((Function) Functions.constant(null));
187 assertThat(g2, sameInstance(graph));
188 }
189
190 @Test
191 public void testTransformEdgeRewrite() {
192 DAGNode<String,String> foo = DAGNode.singleton("foo");
193 DAGNode<String,String> graph = DAGNode.<String,String>newBuilder("graph")
194 .addEdge(foo, "wombat")
195 .build();
196 DAGNode<String,String> g2 =
197 graph.transformEdges((Function) Functions.constant(DAGEdge.create(graph, foo,"hairball")));
198 assertThat(g2, not(sameInstance(graph)));
199 assertThat(g2.getOutgoingEdge(foo, "hairball"),
200 notNullValue());
201 }
202
203 @Test
204 public void testTransformDeeperEdge() {
205 DAGNode<String,String> foo = DAGNode.singleton("foo");
206 DAGNode<String,String> bar = DAGNode.singleton("bar");
207 DAGNode<String,String> wombat = DAGNode.<String,String>newBuilder("wombat")
208 .addEdge(foo, "wombat")
209 .build();
210 DAGNode<String,String> graph = DAGNode.<String,String>newBuilder("graph")
211 .addEdge(wombat, "wumpus")
212 .addEdge(bar, "woozle")
213 .build();
214 DAGNode<String,String> g2 =
215 graph.transformEdges(new Function<DAGEdge<String, String>, DAGEdge<String, String>>() {
216 @Nullable
217 @Override
218 public DAGEdge<String, String> apply(@Nullable DAGEdge<String, String> input) {
219 if (input != null && input.getLabel().equals("woozle")) {
220 return DAGEdge.create(input.getHead(), input.getTail(), "hatrack");
221 } else {
222 return null;
223 }
224 }
225 });
226 assertThat(g2, not(sameInstance(graph)));
227 assertThat(g2.getOutgoingEdge(bar, "hatrack"),
228 notNullValue());
229 assertThat(g2.getOutgoingEdge(bar, "woozle"),
230 nullValue());
231 assertThat(g2.getOutgoingEdge(wombat, "wumpus"),
232 notNullValue());
233 }
234
235 @Test
236 public void testFindBFSSingletonYes() {
237 DAGNode<String,String> foo = DAGNode.singleton("foo");
238 DAGNode<String,String> needle = foo.findNodeBFS(Predicates.<DAGNode<String, String>>alwaysTrue());
239 assertThat(needle, sameInstance(foo));
240 }
241
242 @Test
243 public void testFindBFSSingletonNo() {
244 DAGNode<String,String> foo = DAGNode.singleton("foo");
245 DAGNode<String,String> needle = foo.findNodeBFS(Predicates.<DAGNode<String, String>>alwaysFalse());
246 assertThat(needle, nullValue());
247 }
248
249 @Test
250 public void testFindBFSChildMatches() {
251 DAGNode<String,String> foo = DAGNode.singleton("foo");
252 DAGNode<String,String> bar = DAGNode.<String,String>newBuilder("bar")
253 .addEdge(foo, "foo")
254 .build();
255 DAGNode<String,String> needle =
256 bar.findNodeBFS(DAGNode.labelMatches(Predicates.equalTo("foo")));
257 assertThat(needle, sameInstance(foo));
258 }
259
260 @Test
261 public void testFindBFSFirstNode() {
262 DAGNode<String,String> foo = DAGNode.singleton("foo");
263 DAGNode<String,String> bar = DAGNode.<String,String>newBuilder("bar")
264 .addEdge(foo, "foo")
265 .build();
266 DAGNode<String,String> needle = bar.findNodeBFS(Predicates.<DAGNode<String, String>>alwaysTrue());
267 assertThat(needle, sameInstance(bar));
268 }
269
270 @Test
271 public void testFindBFSFirstFound() {
272 DAGNode<String,String> foo1 = DAGNode.singleton("foo");
273 DAGNode<String,String> foo2 = DAGNode.singleton("foo");
274 DAGNode<String,String> bar = DAGNode.<String,String>newBuilder("bar")
275 .addEdge(foo1, "hello")
276 .build();
277 DAGNode<String,String> bam = DAGNode.<String,String>newBuilder("bam")
278 .addEdge(bar, "wombat")
279 .addEdge(foo2, "goodbye")
280 .build();
281 DAGNode<String,String> needle = bam.findNodeBFS(DAGNode.labelMatches(Predicates.equalTo("foo")));
282 assertThat(needle, sameInstance(foo2));
283 }
284
285 @Test
286 public void testEdgeBFSSingleYes() {
287 DAGNode<String,String> foo = DAGNode.singleton("foo");
288 DAGNode<String,String> bar = DAGNode.<String,String>newBuilder("bar")
289 .addEdge(foo, "-> foo")
290 .build();
291 DAGEdge<String,String> edge = bar.findEdgeBFS(Predicates.alwaysTrue());
292
293 assertThat(edge, isIn(bar.getOutgoingEdges()));
294 }
295
296 @Test
297 public void testEdgeBFSSingleNo() {
298 DAGNode<String,String> foo = DAGNode.singleton("foo");
299 DAGNode<String,String> bar = DAGNode.<String,String>newBuilder("bar")
300 .addEdge(foo, "-> foo")
301 .build();
302 DAGEdge<String,String> edge = bar.findEdgeBFS(Predicates.alwaysFalse());
303
304 assertThat(edge, nullValue());
305 }
306
307 @Test
308 public void testEdgeBFSByName() {
309 DAGNode<String,String> foo = DAGNode.singleton("foo");
310 DAGNode<String,String> baz = DAGNode.singleton("baz");
311 DAGNode<String,String> bar = DAGNode.<String,String>newBuilder("bar")
312 .addEdge(foo, "-> foo")
313 .addEdge(baz, "-> baz")
314 .build();
315 Predicate<DAGEdge<?, String>> pred = DAGEdge.labelMatches(Predicates.equalTo("-> baz"));
316 DAGEdge<String,String> edge = bar.findEdgeBFS(pred);
317
318 assertThat(edge, isIn(bar.getOutgoingEdges()));
319 assertThat(edge.getTail(), equalTo(baz));
320 assertThat(edge.getLabel(), equalTo("-> baz"));
321 }
322
323 @Test
324 public void testEdgeBFSFirst() {
325 DAGNode<String,String> foo = DAGNode.singleton("foo");
326 DAGNode<String,String> bar = DAGNode.<String,String>newBuilder("bar")
327 .addEdge(foo, "hello")
328 .build();
329 DAGNode<String,String> bam = DAGNode.<String,String>newBuilder("bam")
330 .addEdge(bar, "wombat")
331 .addEdge(foo, "goodbye")
332 .build();
333 DAGEdge<String,String> edge = bam.findEdgeBFS(DAGEdge.tailMatches(Predicates.equalTo(foo)));
334
335 assertThat(edge.getLabel(),
336 equalTo("goodbye"));
337 }
338 }