View Javadoc

1   /*
2    * Grapht, an open source dependency injector.
3    * Copyright 2014-2015 various contributors (see CONTRIBUTORS.txt)
4    * Copyright 2010-2014 Regents of the University of Minnesota
5    *
6    * This program is free software; you can redistribute it and/or modify
7    * it under the terms of the GNU Lesser General Public License as
8    * published by the Free Software Foundation; either version 2.1 of the
9    * License, or (at your option) any later version.
10   *
11   * This program is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13   * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
14   * details.
15   *
16   * You should have received a copy of the GNU General Public License along with
17   * this program; if not, write to the Free Software Foundation, Inc., 51
18   * Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
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   * @author <a href="http://www.grouplens.org">GroupLens Research</a>
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         // this node should be replaced once, not twice
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         // if we have > 5 nodes, then fooP was duplicated!
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         // we should have just found the only edge
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         // no edge to find
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         // we should find the correct edge
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         // we should find the first edge
335         assertThat(edge.getLabel(),
336                    equalTo("goodbye"));
337     }
338 }