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