• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2016 The Guava Authors
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.google.common.graph;
18 
19 import static com.google.common.graph.GraphConstants.ENDPOINTS_MISMATCH;
20 import static com.google.common.graph.TestUtil.assertStronglyEquivalent;
21 import static com.google.common.truth.Truth.assertThat;
22 import static com.google.common.truth.Truth8.assertThat;
23 import static org.junit.Assert.fail;
24 
25 import java.util.Optional;
26 import org.junit.After;
27 import org.junit.Test;
28 import org.junit.runner.RunWith;
29 import org.junit.runners.JUnit4;
30 
31 /** Tests for {@link ConfigurableMutableValueGraph} and related functionality. */
32 // TODO(user): Expand coverage and move to proper test suite.
33 @RunWith(JUnit4.class)
34 public final class ValueGraphTest {
35   private static final String DEFAULT = "default";
36 
37   MutableValueGraph<Integer, String> graph;
38 
39   @After
validateGraphState()40   public void validateGraphState() {
41     assertStronglyEquivalent(graph, Graphs.copyOf(graph));
42     assertStronglyEquivalent(graph, ImmutableValueGraph.copyOf(graph));
43 
44     Graph<Integer> asGraph = graph.asGraph();
45     AbstractGraphTest.validateGraph(asGraph);
46     assertThat(graph.nodes()).isEqualTo(asGraph.nodes());
47     assertThat(graph.edges()).isEqualTo(asGraph.edges());
48     assertThat(graph.nodeOrder()).isEqualTo(asGraph.nodeOrder());
49     assertThat(graph.isDirected()).isEqualTo(asGraph.isDirected());
50     assertThat(graph.allowsSelfLoops()).isEqualTo(asGraph.allowsSelfLoops());
51 
52     for (Integer node : graph.nodes()) {
53       assertThat(graph.adjacentNodes(node)).isEqualTo(asGraph.adjacentNodes(node));
54       assertThat(graph.predecessors(node)).isEqualTo(asGraph.predecessors(node));
55       assertThat(graph.successors(node)).isEqualTo(asGraph.successors(node));
56       assertThat(graph.degree(node)).isEqualTo(asGraph.degree(node));
57       assertThat(graph.inDegree(node)).isEqualTo(asGraph.inDegree(node));
58       assertThat(graph.outDegree(node)).isEqualTo(asGraph.outDegree(node));
59 
60       for (Integer otherNode : graph.nodes()) {
61         boolean hasEdge = graph.hasEdgeConnecting(node, otherNode);
62         assertThat(hasEdge).isEqualTo(asGraph.hasEdgeConnecting(node, otherNode));
63         assertThat(graph.edgeValueOrDefault(node, otherNode, null) != null).isEqualTo(hasEdge);
64         assertThat(!graph.edgeValueOrDefault(node, otherNode, DEFAULT).equals(DEFAULT))
65             .isEqualTo(hasEdge);
66       }
67     }
68   }
69 
70   @Test
directedGraph()71   public void directedGraph() {
72     graph = ValueGraphBuilder.directed().allowsSelfLoops(true).build();
73     graph.putEdgeValue(1, 2, "valueA");
74     graph.putEdgeValue(2, 1, "valueB");
75     graph.putEdgeValue(2, 3, "valueC");
76     graph.putEdgeValue(4, 4, "valueD");
77 
78     assertThat(graph.edgeValueOrDefault(1, 2, null)).isEqualTo("valueA");
79     assertThat(graph.edgeValueOrDefault(2, 1, null)).isEqualTo("valueB");
80     assertThat(graph.edgeValueOrDefault(2, 3, null)).isEqualTo("valueC");
81     assertThat(graph.edgeValueOrDefault(4, 4, null)).isEqualTo("valueD");
82     assertThat(graph.edgeValueOrDefault(1, 2, DEFAULT)).isEqualTo("valueA");
83     assertThat(graph.edgeValueOrDefault(2, 1, DEFAULT)).isEqualTo("valueB");
84     assertThat(graph.edgeValueOrDefault(2, 3, DEFAULT)).isEqualTo("valueC");
85     assertThat(graph.edgeValueOrDefault(4, 4, DEFAULT)).isEqualTo("valueD");
86 
87     String toString = graph.toString();
88     assertThat(toString).contains("valueA");
89     assertThat(toString).contains("valueB");
90     assertThat(toString).contains("valueC");
91     assertThat(toString).contains("valueD");
92   }
93 
94   @Test
undirectedGraph()95   public void undirectedGraph() {
96     graph = ValueGraphBuilder.undirected().allowsSelfLoops(true).build();
97     graph.putEdgeValue(1, 2, "valueA");
98     graph.putEdgeValue(2, 1, "valueB"); // overwrites valueA in undirected case
99     graph.putEdgeValue(2, 3, "valueC");
100     graph.putEdgeValue(4, 4, "valueD");
101 
102     assertThat(graph.edgeValueOrDefault(1, 2, null)).isEqualTo("valueB");
103     assertThat(graph.edgeValueOrDefault(2, 1, null)).isEqualTo("valueB");
104     assertThat(graph.edgeValueOrDefault(2, 3, null)).isEqualTo("valueC");
105     assertThat(graph.edgeValueOrDefault(4, 4, null)).isEqualTo("valueD");
106     assertThat(graph.edgeValueOrDefault(1, 2, DEFAULT)).isEqualTo("valueB");
107     assertThat(graph.edgeValueOrDefault(2, 1, DEFAULT)).isEqualTo("valueB");
108     assertThat(graph.edgeValueOrDefault(2, 3, DEFAULT)).isEqualTo("valueC");
109     assertThat(graph.edgeValueOrDefault(4, 4, DEFAULT)).isEqualTo("valueD");
110 
111     String toString = graph.toString();
112     assertThat(toString).doesNotContain("valueA");
113     assertThat(toString).contains("valueB");
114     assertThat(toString).contains("valueC");
115     assertThat(toString).contains("valueD");
116   }
117 
118   @Test
hasEdgeConnecting_directed_correct()119   public void hasEdgeConnecting_directed_correct() {
120     graph = ValueGraphBuilder.directed().build();
121     graph.putEdgeValue(1, 2, "A");
122     assertThat(graph.hasEdgeConnecting(EndpointPair.ordered(1, 2))).isTrue();
123   }
124 
125   @Test
hasEdgeConnecting_directed_backwards()126   public void hasEdgeConnecting_directed_backwards() {
127     graph = ValueGraphBuilder.directed().build();
128     graph.putEdgeValue(1, 2, "A");
129     assertThat(graph.hasEdgeConnecting(EndpointPair.ordered(2, 1))).isFalse();
130   }
131 
132   @Test
hasEdgeConnecting_directed_mismatch()133   public void hasEdgeConnecting_directed_mismatch() {
134     graph = ValueGraphBuilder.directed().build();
135     graph.putEdgeValue(1, 2, "A");
136     assertThat(graph.hasEdgeConnecting(EndpointPair.unordered(1, 2))).isFalse();
137     assertThat(graph.hasEdgeConnecting(EndpointPair.unordered(2, 1))).isFalse();
138   }
139 
140   @Test
hasEdgeConnecting_undirected_correct()141   public void hasEdgeConnecting_undirected_correct() {
142     graph = ValueGraphBuilder.undirected().build();
143     graph.putEdgeValue(1, 2, "A");
144     assertThat(graph.hasEdgeConnecting(EndpointPair.unordered(1, 2))).isTrue();
145   }
146 
147   @Test
hasEdgeConnecting_undirected_backwards()148   public void hasEdgeConnecting_undirected_backwards() {
149     graph = ValueGraphBuilder.undirected().build();
150     graph.putEdgeValue(1, 2, "A");
151     assertThat(graph.hasEdgeConnecting(EndpointPair.unordered(2, 1))).isTrue();
152   }
153 
154   @Test
hasEdgeConnecting_undirected_mismatch()155   public void hasEdgeConnecting_undirected_mismatch() {
156     graph = ValueGraphBuilder.undirected().build();
157     graph.putEdgeValue(1, 2, "A");
158     assertThat(graph.hasEdgeConnecting(EndpointPair.ordered(1, 2))).isTrue();
159     assertThat(graph.hasEdgeConnecting(EndpointPair.ordered(2, 1))).isTrue();
160   }
161 
162   @Test
edgeValue_directed_correct()163   public void edgeValue_directed_correct() {
164     graph = ValueGraphBuilder.directed().build();
165     graph.putEdgeValue(1, 2, "A");
166     assertThat(graph.edgeValue(EndpointPair.ordered(1, 2))).hasValue("A");
167   }
168 
169   @Test
edgeValue_directed_backwards()170   public void edgeValue_directed_backwards() {
171     graph = ValueGraphBuilder.directed().build();
172     graph.putEdgeValue(1, 2, "A");
173     assertThat(graph.edgeValue(EndpointPair.ordered(2, 1))).isEmpty();
174   }
175 
176   @Test
edgeValue_directed_mismatch()177   public void edgeValue_directed_mismatch() {
178     graph = ValueGraphBuilder.directed().build();
179     graph.putEdgeValue(1, 2, "A");
180     try {
181       Optional<String> unused = graph.edgeValue(EndpointPair.unordered(1, 2));
182       unused = graph.edgeValue(EndpointPair.unordered(2, 1));
183       fail("Expected IllegalArgumentException: " + ENDPOINTS_MISMATCH);
184     } catch (IllegalArgumentException e) {
185       assertThat(e).hasMessageThat().contains(ENDPOINTS_MISMATCH);
186     }
187   }
188 
189   @Test
edgeValue_undirected_correct()190   public void edgeValue_undirected_correct() {
191     graph = ValueGraphBuilder.undirected().build();
192     graph.putEdgeValue(1, 2, "A");
193     assertThat(graph.edgeValue(EndpointPair.unordered(1, 2))).hasValue("A");
194   }
195 
196   @Test
edgeValue_undirected_backwards()197   public void edgeValue_undirected_backwards() {
198     graph = ValueGraphBuilder.undirected().build();
199     graph.putEdgeValue(1, 2, "A");
200     assertThat(graph.edgeValue(EndpointPair.unordered(2, 1))).hasValue("A");
201   }
202 
203   @Test
edgeValue_undirected_mismatch()204   public void edgeValue_undirected_mismatch() {
205     graph = ValueGraphBuilder.undirected().build();
206     graph.putEdgeValue(1, 2, "A");
207     assertThat(graph.edgeValue(EndpointPair.ordered(1, 2))).hasValue("A");
208     assertThat(graph.edgeValue(EndpointPair.ordered(2, 1))).hasValue("A");
209   }
210 
211   @Test
edgeValueOrDefault_directed_correct()212   public void edgeValueOrDefault_directed_correct() {
213     graph = ValueGraphBuilder.directed().build();
214     graph.putEdgeValue(1, 2, "A");
215     assertThat(graph.edgeValueOrDefault(EndpointPair.ordered(1, 2), "default")).isEqualTo("A");
216   }
217 
218   @Test
edgeValueOrDefault_directed_backwards()219   public void edgeValueOrDefault_directed_backwards() {
220     graph = ValueGraphBuilder.directed().build();
221     graph.putEdgeValue(1, 2, "A");
222     assertThat(graph.edgeValueOrDefault(EndpointPair.ordered(2, 1), "default"))
223         .isEqualTo("default");
224   }
225 
226   @Test
edgeValueOrDefault_directed_mismatch()227   public void edgeValueOrDefault_directed_mismatch() {
228     graph = ValueGraphBuilder.directed().build();
229     graph.putEdgeValue(1, 2, "A");
230     try {
231       String unused = graph.edgeValueOrDefault(EndpointPair.unordered(1, 2), "default");
232       unused = graph.edgeValueOrDefault(EndpointPair.unordered(2, 1), "default");
233       fail("Expected IllegalArgumentException: " + ENDPOINTS_MISMATCH);
234     } catch (IllegalArgumentException e) {
235       assertThat(e).hasMessageThat().contains(ENDPOINTS_MISMATCH);
236     }
237   }
238 
239   @Test
edgeValueOrDefault_undirected_correct()240   public void edgeValueOrDefault_undirected_correct() {
241     graph = ValueGraphBuilder.undirected().build();
242     graph.putEdgeValue(1, 2, "A");
243     assertThat(graph.edgeValueOrDefault(EndpointPair.unordered(1, 2), "default")).isEqualTo("A");
244   }
245 
246   @Test
edgeValueOrDefault_undirected_backwards()247   public void edgeValueOrDefault_undirected_backwards() {
248     graph = ValueGraphBuilder.undirected().build();
249     graph.putEdgeValue(1, 2, "A");
250     assertThat(graph.edgeValueOrDefault(EndpointPair.unordered(2, 1), "default")).isEqualTo("A");
251   }
252 
253   @Test
edgeValueOrDefault_undirected_mismatch()254   public void edgeValueOrDefault_undirected_mismatch() {
255     graph = ValueGraphBuilder.undirected().build();
256     graph.putEdgeValue(1, 2, "A");
257     assertThat(graph.edgeValueOrDefault(EndpointPair.ordered(2, 1), "default")).isEqualTo("A");
258     assertThat(graph.edgeValueOrDefault(EndpointPair.ordered(2, 1), "default")).isEqualTo("A");
259   }
260 
261   @Test
putEdgeValue_directed()262   public void putEdgeValue_directed() {
263     graph = ValueGraphBuilder.directed().build();
264 
265     assertThat(graph.putEdgeValue(1, 2, "valueA")).isNull();
266     assertThat(graph.putEdgeValue(2, 1, "valueB")).isNull();
267     assertThat(graph.putEdgeValue(1, 2, "valueC")).isEqualTo("valueA");
268     assertThat(graph.putEdgeValue(2, 1, "valueD")).isEqualTo("valueB");
269   }
270 
271   @Test
putEdgeValue_directed_orderMismatch()272   public void putEdgeValue_directed_orderMismatch() {
273     graph = ValueGraphBuilder.directed().build();
274     try {
275       graph.putEdgeValue(EndpointPair.unordered(1, 2), "irrelevant");
276       fail("Expected IllegalArgumentException: " + ENDPOINTS_MISMATCH);
277     } catch (IllegalArgumentException e) {
278       assertThat(e).hasMessageThat().contains(ENDPOINTS_MISMATCH);
279     }
280   }
281 
282   @Test
putEdgeValue_undirected_orderMismatch()283   public void putEdgeValue_undirected_orderMismatch() {
284     graph = ValueGraphBuilder.undirected().build();
285     assertThat(graph.putEdgeValue(EndpointPair.ordered(1, 2), "irrelevant")).isNull();
286   }
287 
288   @Test
putEdgeValue_undirected()289   public void putEdgeValue_undirected() {
290     graph = ValueGraphBuilder.undirected().build();
291 
292     assertThat(graph.putEdgeValue(1, 2, "valueA")).isNull();
293     assertThat(graph.putEdgeValue(2, 1, "valueB")).isEqualTo("valueA");
294     assertThat(graph.putEdgeValue(1, 2, "valueC")).isEqualTo("valueB");
295     assertThat(graph.putEdgeValue(2, 1, "valueD")).isEqualTo("valueC");
296   }
297 
298   @Test
removeEdge_directed()299   public void removeEdge_directed() {
300     graph = ValueGraphBuilder.directed().build();
301     graph.putEdgeValue(1, 2, "valueA");
302     graph.putEdgeValue(2, 1, "valueB");
303     graph.putEdgeValue(2, 3, "valueC");
304 
305     assertThat(graph.removeEdge(1, 2)).isEqualTo("valueA");
306     assertThat(graph.removeEdge(1, 2)).isNull();
307     assertThat(graph.removeEdge(2, 1)).isEqualTo("valueB");
308     assertThat(graph.removeEdge(2, 1)).isNull();
309     assertThat(graph.removeEdge(2, 3)).isEqualTo("valueC");
310     assertThat(graph.removeEdge(2, 3)).isNull();
311   }
312 
313   @Test
removeEdge_undirected()314   public void removeEdge_undirected() {
315     graph = ValueGraphBuilder.undirected().build();
316     graph.putEdgeValue(1, 2, "valueA");
317     graph.putEdgeValue(2, 1, "valueB");
318     graph.putEdgeValue(2, 3, "valueC");
319 
320     assertThat(graph.removeEdge(1, 2)).isEqualTo("valueB");
321     assertThat(graph.removeEdge(1, 2)).isNull();
322     assertThat(graph.removeEdge(2, 1)).isNull();
323     assertThat(graph.removeEdge(2, 3)).isEqualTo("valueC");
324     assertThat(graph.removeEdge(2, 3)).isNull();
325   }
326 
327   @Test
removeEdge_directed_orderMismatch()328   public void removeEdge_directed_orderMismatch() {
329     graph = ValueGraphBuilder.directed().build();
330     graph.putEdgeValue(1, 2, "1->2");
331     graph.putEdgeValue(2, 1, "2->1");
332     try {
333       graph.removeEdge(EndpointPair.unordered(1, 2));
334       graph.removeEdge(EndpointPair.unordered(2, 1));
335       fail("Expected IllegalArgumentException: " + ENDPOINTS_MISMATCH);
336     } catch (IllegalArgumentException e) {
337       assertThat(e).hasMessageThat().contains(ENDPOINTS_MISMATCH);
338     }
339   }
340 
341   @Test
removeEdge_undirected_orderMismatch()342   public void removeEdge_undirected_orderMismatch() {
343     graph = ValueGraphBuilder.undirected().build();
344     graph.putEdgeValue(1, 2, "1-2");
345     assertThat(graph.removeEdge(EndpointPair.ordered(1, 2))).isEqualTo("1-2");
346   }
347 
348   @Test
edgeValue_missing()349   public void edgeValue_missing() {
350     graph = ValueGraphBuilder.directed().build();
351 
352     assertThat(graph.edgeValueOrDefault(1, 2, DEFAULT)).isEqualTo(DEFAULT);
353     assertThat(graph.edgeValueOrDefault(2, 1, DEFAULT)).isEqualTo(DEFAULT);
354     assertThat(graph.edgeValue(1, 2).orElse(DEFAULT)).isEqualTo(DEFAULT);
355     assertThat(graph.edgeValue(2, 1).orElse(DEFAULT)).isEqualTo(DEFAULT);
356     assertThat(graph.edgeValueOrDefault(1, 2, null)).isNull();
357     assertThat(graph.edgeValueOrDefault(2, 1, null)).isNull();
358     assertThat(graph.edgeValue(1, 2).orElse(null)).isNull();
359     assertThat(graph.edgeValue(2, 1).orElse(null)).isNull();
360 
361     graph.putEdgeValue(1, 2, "valueA");
362     graph.putEdgeValue(2, 1, "valueB");
363     assertThat(graph.edgeValueOrDefault(1, 2, DEFAULT)).isEqualTo("valueA");
364     assertThat(graph.edgeValueOrDefault(2, 1, DEFAULT)).isEqualTo("valueB");
365     assertThat(graph.edgeValueOrDefault(1, 2, null)).isEqualTo("valueA");
366     assertThat(graph.edgeValueOrDefault(2, 1, null)).isEqualTo("valueB");
367     assertThat(graph.edgeValue(1, 2).get()).isEqualTo("valueA");
368     assertThat(graph.edgeValue(2, 1).get()).isEqualTo("valueB");
369 
370     graph.removeEdge(1, 2);
371     graph.putEdgeValue(2, 1, "valueC");
372     assertThat(graph.edgeValueOrDefault(1, 2, DEFAULT)).isEqualTo(DEFAULT);
373     assertThat(graph.edgeValueOrDefault(2, 1, DEFAULT)).isEqualTo("valueC");
374     assertThat(graph.edgeValue(1, 2).orElse(DEFAULT)).isEqualTo(DEFAULT);
375     assertThat(graph.edgeValueOrDefault(1, 2, null)).isNull();
376     assertThat(graph.edgeValueOrDefault(2, 1, null)).isEqualTo("valueC");
377     assertThat(graph.edgeValue(1, 2).orElse(null)).isNull();
378     assertThat(graph.edgeValue(2, 1).get()).isEqualTo("valueC");
379   }
380 
381   @Test
equivalence_considersEdgeValue()382   public void equivalence_considersEdgeValue() {
383     graph = ValueGraphBuilder.undirected().build();
384     graph.putEdgeValue(1, 2, "valueA");
385 
386     MutableValueGraph<Integer, String> otherGraph = ValueGraphBuilder.undirected().build();
387     otherGraph.putEdgeValue(1, 2, "valueA");
388     assertThat(graph).isEqualTo(otherGraph);
389 
390     otherGraph.putEdgeValue(1, 2, "valueB");
391     assertThat(graph).isNotEqualTo(otherGraph); // values differ
392   }
393 }
394