1 /* 2 * Copyright (C) 2014 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.Graphs.copyOf; 20 import static com.google.common.graph.Graphs.inducedSubgraph; 21 import static com.google.common.graph.Graphs.reachableNodes; 22 import static com.google.common.graph.Graphs.transitiveClosure; 23 import static com.google.common.graph.Graphs.transpose; 24 import static com.google.common.truth.Truth.assertThat; 25 import static org.junit.Assert.fail; 26 27 import com.google.common.collect.ImmutableSet; 28 import java.util.Set; 29 import org.junit.Test; 30 import org.junit.runner.RunWith; 31 import org.junit.runners.JUnit4; 32 33 /** 34 * Tests for {@link Graphs}. Tests assume that the implementation of the method {@code addEdge} adds 35 * the missing nodes to the graph, then adds the edge between them. 36 */ 37 @RunWith(JUnit4.class) 38 public class GraphsTest { 39 private static final Integer N1 = 1; 40 private static final Integer N2 = 2; 41 private static final Integer N3 = 3; 42 private static final Integer N4 = 4; 43 private static final String E11 = "1-1"; 44 private static final String E11_A = "1-1a"; 45 private static final String E12 = "1-2"; 46 private static final String E12_A = "1-2a"; 47 private static final String E12_B = "1-2b"; 48 private static final String E21 = "2-1"; 49 private static final String E13 = "1-3"; 50 private static final String E31 = "3-1"; 51 private static final String E34 = "3-4"; 52 private static final String E44 = "4-4"; 53 private static final int NODE_COUNT = 20; 54 private static final int EDGE_COUNT = 20; 55 // TODO(user): Consider adding both error messages from here and {@link AbstractNetworkTest} 56 // in one class (may be a utility class for error messages). 57 private static final String ERROR_PARALLEL_EDGE = "connected by a different edge"; 58 private static final String ERROR_NEGATIVE_COUNT = "is non-negative"; 59 private static final String ERROR_ADDED_PARALLEL_EDGE = 60 "Should not be allowed to add a parallel edge."; 61 private static final String ERROR_ADDED_SELF_LOOP = 62 "Should not be allowed to add a self-loop edge."; 63 static final String ERROR_SELF_LOOP = "self-loops are not allowed"; 64 65 @Test transitiveClosure_directedGraph()66 public void transitiveClosure_directedGraph() { 67 MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(false).build(); 68 directedGraph.putEdge(N1, N2); 69 directedGraph.putEdge(N1, N3); 70 directedGraph.putEdge(N2, N3); 71 directedGraph.addNode(N4); 72 73 MutableGraph<Integer> expectedClosure = GraphBuilder.directed().allowsSelfLoops(true).build(); 74 expectedClosure.putEdge(N1, N1); 75 expectedClosure.putEdge(N1, N2); 76 expectedClosure.putEdge(N1, N3); 77 expectedClosure.putEdge(N2, N2); 78 expectedClosure.putEdge(N2, N3); 79 expectedClosure.putEdge(N3, N3); 80 expectedClosure.putEdge(N4, N4); 81 82 checkTransitiveClosure(directedGraph, expectedClosure); 83 } 84 85 @Test transitiveClosure_undirectedGraph()86 public void transitiveClosure_undirectedGraph() { 87 MutableGraph<Integer> undirectedGraph = 88 GraphBuilder.undirected().allowsSelfLoops(false).build(); 89 undirectedGraph.putEdge(N1, N2); 90 undirectedGraph.putEdge(N1, N3); 91 undirectedGraph.putEdge(N2, N3); 92 undirectedGraph.addNode(N4); 93 94 MutableGraph<Integer> expectedClosure = GraphBuilder.undirected().allowsSelfLoops(true).build(); 95 expectedClosure.putEdge(N1, N1); 96 expectedClosure.putEdge(N1, N2); 97 expectedClosure.putEdge(N1, N3); 98 expectedClosure.putEdge(N2, N2); 99 expectedClosure.putEdge(N2, N3); 100 expectedClosure.putEdge(N3, N3); 101 expectedClosure.putEdge(N4, N4); 102 103 checkTransitiveClosure(undirectedGraph, expectedClosure); 104 } 105 106 @Test transitiveClosure_directedPathGraph()107 public void transitiveClosure_directedPathGraph() { 108 MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(false).build(); 109 directedGraph.putEdge(N1, N2); 110 directedGraph.putEdge(N2, N3); 111 directedGraph.putEdge(N3, N4); 112 113 MutableGraph<Integer> expectedClosure = GraphBuilder.directed().allowsSelfLoops(true).build(); 114 expectedClosure.putEdge(N1, N1); 115 expectedClosure.putEdge(N1, N2); 116 expectedClosure.putEdge(N1, N3); 117 expectedClosure.putEdge(N1, N4); 118 expectedClosure.putEdge(N2, N2); 119 expectedClosure.putEdge(N2, N3); 120 expectedClosure.putEdge(N2, N4); 121 expectedClosure.putEdge(N3, N3); 122 expectedClosure.putEdge(N3, N4); 123 expectedClosure.putEdge(N4, N4); 124 125 checkTransitiveClosure(directedGraph, expectedClosure); 126 } 127 128 @Test transitiveClosure_undirectedPathGraph()129 public void transitiveClosure_undirectedPathGraph() { 130 MutableGraph<Integer> undirectedGraph = 131 GraphBuilder.undirected().allowsSelfLoops(false).build(); 132 undirectedGraph.putEdge(N1, N2); 133 undirectedGraph.putEdge(N2, N3); 134 undirectedGraph.putEdge(N3, N4); 135 136 MutableGraph<Integer> expectedClosure = GraphBuilder.undirected().allowsSelfLoops(true).build(); 137 expectedClosure.putEdge(N1, N1); 138 expectedClosure.putEdge(N1, N2); 139 expectedClosure.putEdge(N1, N3); 140 expectedClosure.putEdge(N1, N4); 141 expectedClosure.putEdge(N2, N2); 142 expectedClosure.putEdge(N2, N3); 143 expectedClosure.putEdge(N2, N4); 144 expectedClosure.putEdge(N3, N3); 145 expectedClosure.putEdge(N3, N4); 146 expectedClosure.putEdge(N4, N4); 147 148 checkTransitiveClosure(undirectedGraph, expectedClosure); 149 } 150 151 @Test transitiveClosure_directedCycleGraph()152 public void transitiveClosure_directedCycleGraph() { 153 MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(false).build(); 154 directedGraph.putEdge(N1, N2); 155 directedGraph.putEdge(N2, N3); 156 directedGraph.putEdge(N3, N4); 157 directedGraph.putEdge(N4, N1); 158 159 MutableGraph<Integer> expectedClosure = GraphBuilder.directed().allowsSelfLoops(true).build(); 160 expectedClosure.putEdge(N1, N1); 161 expectedClosure.putEdge(N1, N2); 162 expectedClosure.putEdge(N1, N3); 163 expectedClosure.putEdge(N1, N4); 164 expectedClosure.putEdge(N2, N1); 165 expectedClosure.putEdge(N2, N2); 166 expectedClosure.putEdge(N2, N3); 167 expectedClosure.putEdge(N2, N4); 168 expectedClosure.putEdge(N3, N1); 169 expectedClosure.putEdge(N3, N2); 170 expectedClosure.putEdge(N3, N3); 171 expectedClosure.putEdge(N3, N4); 172 expectedClosure.putEdge(N4, N1); 173 expectedClosure.putEdge(N4, N2); 174 expectedClosure.putEdge(N4, N3); 175 expectedClosure.putEdge(N4, N4); 176 177 checkTransitiveClosure(directedGraph, expectedClosure); 178 } 179 180 @Test transitiveClosure_undirectedCycleGraph()181 public void transitiveClosure_undirectedCycleGraph() { 182 MutableGraph<Integer> undirectedGraph = 183 GraphBuilder.undirected().allowsSelfLoops(false).build(); 184 undirectedGraph.putEdge(N1, N2); 185 undirectedGraph.putEdge(N2, N3); 186 undirectedGraph.putEdge(N3, N4); 187 undirectedGraph.putEdge(N4, N1); 188 189 MutableGraph<Integer> expectedClosure = GraphBuilder.undirected().allowsSelfLoops(true).build(); 190 expectedClosure.putEdge(N1, N1); 191 expectedClosure.putEdge(N1, N2); 192 expectedClosure.putEdge(N1, N3); 193 expectedClosure.putEdge(N1, N4); 194 expectedClosure.putEdge(N2, N2); 195 expectedClosure.putEdge(N2, N3); 196 expectedClosure.putEdge(N2, N4); 197 expectedClosure.putEdge(N3, N3); 198 expectedClosure.putEdge(N3, N4); 199 expectedClosure.putEdge(N4, N4); 200 201 checkTransitiveClosure(undirectedGraph, expectedClosure); 202 } 203 204 @Test transpose_undirectedGraph()205 public void transpose_undirectedGraph() { 206 MutableGraph<Integer> undirectedGraph = GraphBuilder.undirected().build(); 207 undirectedGraph.putEdge(N1, N2); 208 209 assertThat(transpose(undirectedGraph)).isSameInstanceAs(undirectedGraph); 210 } 211 212 @Test transpose_directedGraph()213 public void transpose_directedGraph() { 214 MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(true).build(); 215 directedGraph.putEdge(N1, N3); 216 directedGraph.putEdge(N3, N1); 217 directedGraph.putEdge(N1, N2); 218 directedGraph.putEdge(N1, N1); 219 directedGraph.putEdge(N3, N4); 220 221 MutableGraph<Integer> expectedTranspose = GraphBuilder.directed().allowsSelfLoops(true).build(); 222 expectedTranspose.putEdge(N3, N1); 223 expectedTranspose.putEdge(N1, N3); 224 expectedTranspose.putEdge(N2, N1); 225 expectedTranspose.putEdge(N1, N1); 226 expectedTranspose.putEdge(N4, N3); 227 228 Graph<Integer> transpose = transpose(directedGraph); 229 assertThat(transpose).isEqualTo(expectedTranspose); 230 assertThat(transpose(transpose)).isSameInstanceAs(directedGraph); 231 AbstractGraphTest.validateGraph(transpose); 232 233 for (Integer node : directedGraph.nodes()) { 234 assertThat(directedGraph.inDegree(node)).isSameInstanceAs(transpose.outDegree(node)); 235 assertThat(directedGraph.outDegree(node)).isSameInstanceAs(transpose.inDegree(node)); 236 } 237 238 assertThat(transpose.successors(N1)).doesNotContain(N2); 239 directedGraph.putEdge(N2, N1); 240 // View should be updated. 241 assertThat(transpose.successors(N1)).contains(N2); 242 AbstractGraphTest.validateGraph(transpose); 243 } 244 245 @Test transpose_undirectedValueGraph()246 public void transpose_undirectedValueGraph() { 247 MutableValueGraph<Integer, String> undirectedGraph = ValueGraphBuilder.undirected().build(); 248 undirectedGraph.putEdgeValue(N1, N2, E12); 249 250 assertThat(transpose(undirectedGraph)).isSameInstanceAs(undirectedGraph); 251 } 252 253 @Test transpose_directedValueGraph()254 public void transpose_directedValueGraph() { 255 MutableValueGraph<Integer, String> directedGraph = 256 ValueGraphBuilder.directed().allowsSelfLoops(true).build(); 257 directedGraph.putEdgeValue(N1, N3, E13); 258 directedGraph.putEdgeValue(N3, N1, E31); 259 directedGraph.putEdgeValue(N1, N2, E12); 260 directedGraph.putEdgeValue(N1, N1, E11); 261 directedGraph.putEdgeValue(N3, N4, E34); 262 263 MutableValueGraph<Integer, String> expectedTranspose = 264 ValueGraphBuilder.directed().allowsSelfLoops(true).build(); 265 expectedTranspose.putEdgeValue(N3, N1, E13); 266 expectedTranspose.putEdgeValue(N1, N3, E31); 267 expectedTranspose.putEdgeValue(N2, N1, E12); 268 expectedTranspose.putEdgeValue(N1, N1, E11); 269 expectedTranspose.putEdgeValue(N4, N3, E34); 270 271 ValueGraph<Integer, String> transpose = transpose(directedGraph); 272 assertThat(transpose).isEqualTo(expectedTranspose); 273 assertThat(transpose(transpose)).isSameInstanceAs(directedGraph); 274 AbstractGraphTest.validateGraph(transpose.asGraph()); 275 276 assertThat(transpose.edgeValueOrDefault(N1, N2, null)).isNull(); 277 for (Integer node : directedGraph.nodes()) { 278 assertThat(directedGraph.inDegree(node)).isSameInstanceAs(transpose.outDegree(node)); 279 assertThat(directedGraph.outDegree(node)).isSameInstanceAs(transpose.inDegree(node)); 280 } 281 282 directedGraph.putEdgeValue(N2, N1, E21); 283 // View should be updated. 284 assertThat(transpose.edgeValueOrDefault(N1, N2, null)).isEqualTo(E21); 285 AbstractGraphTest.validateGraph(transpose.asGraph()); 286 } 287 288 @Test transpose_undirectedNetwork()289 public void transpose_undirectedNetwork() { 290 MutableNetwork<Integer, String> undirectedGraph = NetworkBuilder.undirected().build(); 291 undirectedGraph.addEdge(N1, N2, E12); 292 293 assertThat(transpose(undirectedGraph)).isSameInstanceAs(undirectedGraph); 294 } 295 296 @Test transpose_directedNetwork()297 public void transpose_directedNetwork() { 298 MutableNetwork<Integer, String> directedGraph = 299 NetworkBuilder.directed().allowsParallelEdges(true).allowsSelfLoops(true).build(); 300 directedGraph.addEdge(N1, N3, E13); 301 directedGraph.addEdge(N3, N1, E31); 302 directedGraph.addEdge(N1, N2, E12); 303 directedGraph.addEdge(N1, N2, E12_A); 304 directedGraph.addEdge(N1, N1, E11); 305 directedGraph.addEdge(N3, N4, E34); 306 307 MutableNetwork<Integer, String> expectedTranspose = 308 NetworkBuilder.directed().allowsParallelEdges(true).allowsSelfLoops(true).build(); 309 expectedTranspose.addEdge(N3, N1, E13); 310 expectedTranspose.addEdge(N1, N3, E31); 311 expectedTranspose.addEdge(N2, N1, E12); 312 expectedTranspose.addEdge(N2, N1, E12_A); 313 expectedTranspose.addEdge(N1, N1, E11); 314 expectedTranspose.addEdge(N4, N3, E34); 315 316 Network<Integer, String> transpose = transpose(directedGraph); 317 assertThat(transpose).isEqualTo(expectedTranspose); 318 assertThat(transpose(transpose)).isSameInstanceAs(directedGraph); 319 AbstractNetworkTest.validateNetwork(transpose); 320 321 assertThat(transpose.edgesConnecting(N1, N2)).isEmpty(); 322 assertThat(transpose.edgeConnecting(N1, N2).isPresent()).isFalse(); 323 assertThat(transpose.edgeConnectingOrNull(N1, N2)).isNull(); 324 325 for (Integer node : directedGraph.nodes()) { 326 assertThat(directedGraph.inDegree(node)).isSameInstanceAs(transpose.outDegree(node)); 327 assertThat(directedGraph.outDegree(node)).isSameInstanceAs(transpose.inDegree(node)); 328 } 329 330 directedGraph.addEdge(N2, N1, E21); 331 // View should be updated. 332 assertThat(transpose.edgesConnecting(N1, N2)).containsExactly(E21); 333 assertThat(transpose.edgeConnecting(N1, N2).get()).isEqualTo(E21); 334 assertThat(transpose.edgeConnectingOrNull(N1, N2)).isEqualTo(E21); 335 AbstractNetworkTest.validateNetwork(transpose); 336 } 337 338 @Test inducedSubgraph_graph()339 public void inducedSubgraph_graph() { 340 Set<Integer> nodeSubset = ImmutableSet.of(N1, N2, N4); 341 342 MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(true).build(); 343 directedGraph.putEdge(N1, N2); 344 directedGraph.putEdge(N2, N1); 345 directedGraph.putEdge(N1, N3); // only incident to one node in nodeSubset 346 directedGraph.putEdge(N4, N4); 347 directedGraph.putEdge(5, 6); // not incident to any node in nodeSubset 348 349 MutableGraph<Integer> expectedSubgraph = GraphBuilder.directed().allowsSelfLoops(true).build(); 350 expectedSubgraph.putEdge(N1, N2); 351 expectedSubgraph.putEdge(N2, N1); 352 expectedSubgraph.putEdge(N4, N4); 353 354 assertThat(inducedSubgraph(directedGraph, nodeSubset)).isEqualTo(expectedSubgraph); 355 } 356 357 @Test inducedSubgraph_valueGraph()358 public void inducedSubgraph_valueGraph() { 359 Set<Integer> nodeSubset = ImmutableSet.of(N1, N2, N4); 360 361 MutableValueGraph<Integer, String> directedGraph = 362 ValueGraphBuilder.directed().allowsSelfLoops(true).build(); 363 directedGraph.putEdgeValue(N1, N2, E12); 364 directedGraph.putEdgeValue(N2, N1, E21); 365 directedGraph.putEdgeValue(N1, N3, E13); // only incident to one node in nodeSubset 366 directedGraph.putEdgeValue(N4, N4, E44); 367 directedGraph.putEdgeValue(5, 6, "5-6"); // not incident to any node in nodeSubset 368 369 MutableValueGraph<Integer, String> expectedSubgraph = 370 ValueGraphBuilder.directed().allowsSelfLoops(true).build(); 371 expectedSubgraph.putEdgeValue(N1, N2, E12); 372 expectedSubgraph.putEdgeValue(N2, N1, E21); 373 expectedSubgraph.putEdgeValue(N4, N4, E44); 374 375 assertThat(inducedSubgraph(directedGraph, nodeSubset)).isEqualTo(expectedSubgraph); 376 } 377 378 @Test inducedSubgraph_network()379 public void inducedSubgraph_network() { 380 Set<Integer> nodeSubset = ImmutableSet.of(N1, N2, N4); 381 382 MutableNetwork<Integer, String> directedGraph = 383 NetworkBuilder.directed().allowsSelfLoops(true).build(); 384 directedGraph.addEdge(N1, N2, E12); 385 directedGraph.addEdge(N2, N1, E21); 386 directedGraph.addEdge(N1, N3, E13); // only incident to one node in nodeSubset 387 directedGraph.addEdge(N4, N4, E44); 388 directedGraph.addEdge(5, 6, "5-6"); // not incident to any node in nodeSubset 389 390 MutableNetwork<Integer, String> expectedSubgraph = 391 NetworkBuilder.directed().allowsSelfLoops(true).build(); 392 expectedSubgraph.addEdge(N1, N2, E12); 393 expectedSubgraph.addEdge(N2, N1, E21); 394 expectedSubgraph.addEdge(N4, N4, E44); 395 396 assertThat(inducedSubgraph(directedGraph, nodeSubset)).isEqualTo(expectedSubgraph); 397 } 398 399 @Test inducedSubgraph_nodeNotInGraph()400 public void inducedSubgraph_nodeNotInGraph() { 401 MutableNetwork<Integer, String> undirectedGraph = NetworkBuilder.undirected().build(); 402 403 try { 404 inducedSubgraph(undirectedGraph, ImmutableSet.of(N1)); 405 fail("Should have rejected getting induced subgraph with node not in original graph."); 406 } catch (IllegalArgumentException expected) { 407 } 408 } 409 410 @Test copyOf_nullArgument()411 public void copyOf_nullArgument() { 412 try { 413 copyOf((Graph<?>) null); 414 fail("Should have rejected a null graph."); 415 } catch (NullPointerException expected) { 416 } 417 } 418 419 @Test copyOf_directedGraph()420 public void copyOf_directedGraph() { 421 Graph<Integer> directedGraph = buildDirectedGraph(); 422 423 Graph<Integer> copy = copyOf(directedGraph); 424 assertThat(copy).isEqualTo(directedGraph); 425 } 426 427 @Test copyOf_undirectedGraph()428 public void copyOf_undirectedGraph() { 429 Graph<Integer> undirectedGraph = buildUndirectedGraph(); 430 431 Graph<Integer> copy = copyOf(undirectedGraph); 432 assertThat(copy).isEqualTo(undirectedGraph); 433 } 434 435 @Test copyOf_directedValueGraph()436 public void copyOf_directedValueGraph() { 437 ValueGraph<Integer, String> directedGraph = buildDirectedValueGraph(); 438 439 ValueGraph<Integer, String> copy = copyOf(directedGraph); 440 assertThat(copy).isEqualTo(directedGraph); 441 } 442 443 @Test copyOf_undirectedValueGraph()444 public void copyOf_undirectedValueGraph() { 445 ValueGraph<Integer, String> undirectedGraph = buildUndirectedValueGraph(); 446 447 ValueGraph<Integer, String> copy = copyOf(undirectedGraph); 448 assertThat(copy).isEqualTo(undirectedGraph); 449 } 450 451 @Test copyOf_directedNetwork()452 public void copyOf_directedNetwork() { 453 Network<Integer, String> directedGraph = buildDirectedNetwork(); 454 455 Network<Integer, String> copy = copyOf(directedGraph); 456 assertThat(copy).isEqualTo(directedGraph); 457 } 458 459 @Test copyOf_undirectedNetwork()460 public void copyOf_undirectedNetwork() { 461 Network<Integer, String> undirectedGraph = buildUndirectedNetwork(); 462 463 Network<Integer, String> copy = copyOf(undirectedGraph); 464 assertThat(copy).isEqualTo(undirectedGraph); 465 } 466 467 // Graph creation tests 468 469 @Test createDirected()470 public void createDirected() { 471 MutableNetwork<Integer, String> directedGraph = NetworkBuilder.directed().build(); 472 assertThat(directedGraph.nodes()).isEmpty(); 473 assertThat(directedGraph.edges()).isEmpty(); 474 assertThat(directedGraph.addEdge(N1, N2, E12)).isTrue(); 475 assertThat(directedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 476 assertThat(directedGraph.edgesConnecting(N2, N1)).isEmpty(); 477 478 // By default, parallel edges are not allowed. 479 try { 480 directedGraph.addEdge(N1, N2, E12_A); 481 fail(ERROR_ADDED_PARALLEL_EDGE); 482 } catch (IllegalArgumentException e) { 483 assertThat(e.getMessage()).contains(ERROR_PARALLEL_EDGE); 484 } 485 486 // By default, self-loop edges are not allowed. 487 try { 488 directedGraph.addEdge(N1, N1, E11); 489 fail(ERROR_ADDED_SELF_LOOP); 490 } catch (IllegalArgumentException e) { 491 assertThat(e).hasMessageThat().contains(ERROR_SELF_LOOP); 492 } 493 } 494 495 @Test createUndirected()496 public void createUndirected() { 497 MutableNetwork<Integer, String> undirectedGraph = NetworkBuilder.undirected().build(); 498 assertThat(undirectedGraph.nodes()).isEmpty(); 499 assertThat(undirectedGraph.edges()).isEmpty(); 500 assertThat(undirectedGraph.addEdge(N1, N2, E12)).isTrue(); 501 assertThat(undirectedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 502 assertThat(undirectedGraph.edgesConnecting(N2, N1)).isEqualTo(ImmutableSet.of(E12)); 503 504 // By default, parallel edges are not allowed. 505 try { 506 undirectedGraph.addEdge(N1, N2, E12_A); 507 fail(ERROR_ADDED_PARALLEL_EDGE); 508 } catch (IllegalArgumentException e) { 509 assertThat(e.getMessage()).contains(ERROR_PARALLEL_EDGE); 510 } 511 try { 512 undirectedGraph.addEdge(N2, N1, E21); 513 fail(ERROR_ADDED_PARALLEL_EDGE); 514 } catch (IllegalArgumentException e) { 515 assertThat(e.getMessage()).contains(ERROR_PARALLEL_EDGE); 516 } 517 518 // By default, self-loop edges are not allowed. 519 try { 520 undirectedGraph.addEdge(N1, N1, E11); 521 fail(ERROR_ADDED_SELF_LOOP); 522 } catch (IllegalArgumentException e) { 523 assertThat(e).hasMessageThat().contains(ERROR_SELF_LOOP); 524 } 525 } 526 527 @Test createDirected_multigraph()528 public void createDirected_multigraph() { 529 MutableNetwork<Integer, String> directedMultigraph = 530 NetworkBuilder.directed().allowsParallelEdges(true).build(); 531 assertThat(directedMultigraph.addEdge(N1, N2, E12)).isTrue(); 532 assertThat(directedMultigraph.addEdge(N1, N2, E12_A)).isTrue(); 533 assertThat(directedMultigraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12, E12_A)); 534 assertThat(directedMultigraph.edgesConnecting(N2, N1)).isEmpty(); 535 } 536 537 @Test createUndirected_multigraph()538 public void createUndirected_multigraph() { 539 MutableNetwork<Integer, String> undirectedMultigraph = 540 NetworkBuilder.undirected().allowsParallelEdges(true).build(); 541 assertThat(undirectedMultigraph.addEdge(N1, N2, E12)).isTrue(); 542 assertThat(undirectedMultigraph.addEdge(N1, N2, E12_A)).isTrue(); 543 assertThat(undirectedMultigraph.addEdge(N2, N1, E21)).isTrue(); 544 assertThat(undirectedMultigraph.edgesConnecting(N1, N2)) 545 .isEqualTo(ImmutableSet.of(E12, E12_A, E21)); 546 } 547 548 @Test createDirected_expectedNodeCount()549 public void createDirected_expectedNodeCount() { 550 MutableNetwork<Integer, String> directedGraph = 551 NetworkBuilder.directed().expectedNodeCount(NODE_COUNT).build(); 552 assertThat(directedGraph.addEdge(N1, N2, E12)).isTrue(); 553 assertThat(directedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 554 assertThat(directedGraph.edgesConnecting(N2, N1)).isEmpty(); 555 } 556 557 @Test createUndirected_expectedNodeCount()558 public void createUndirected_expectedNodeCount() { 559 MutableNetwork<Integer, String> undirectedGraph = 560 NetworkBuilder.undirected().expectedNodeCount(NODE_COUNT).build(); 561 assertThat(undirectedGraph.addEdge(N1, N2, E12)).isTrue(); 562 assertThat(undirectedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 563 assertThat(undirectedGraph.edgesConnecting(N2, N1)).isEqualTo(ImmutableSet.of(E12)); 564 } 565 566 @Test builder_expectedNodeCount_negative()567 public void builder_expectedNodeCount_negative() { 568 try { 569 NetworkBuilder.directed().expectedNodeCount(-1); 570 fail("Should have rejected negative expected node count."); 571 } catch (IllegalArgumentException e) { 572 assertThat(e.getMessage()).contains(ERROR_NEGATIVE_COUNT); 573 } 574 } 575 576 @Test createDirected_expectedEdgeCount()577 public void createDirected_expectedEdgeCount() { 578 MutableNetwork<Integer, String> directedGraph = 579 NetworkBuilder.directed().expectedEdgeCount(EDGE_COUNT).build(); 580 assertThat(directedGraph.addEdge(N1, N2, E12)).isTrue(); 581 assertThat(directedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 582 assertThat(directedGraph.edgesConnecting(N2, N1)).isEmpty(); 583 } 584 585 @Test createUndirected_expectedEdgeCount()586 public void createUndirected_expectedEdgeCount() { 587 MutableNetwork<Integer, String> undirectedGraph = 588 NetworkBuilder.undirected().expectedEdgeCount(EDGE_COUNT).build(); 589 assertThat(undirectedGraph.addEdge(N1, N2, E12)).isTrue(); 590 assertThat(undirectedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 591 assertThat(undirectedGraph.edgesConnecting(N2, N1)).isEqualTo(ImmutableSet.of(E12)); 592 } 593 594 @Test builder_expectedEdgeCount_negative()595 public void builder_expectedEdgeCount_negative() { 596 try { 597 NetworkBuilder.directed().expectedEdgeCount(-1); 598 fail("Should have rejected negative expected edge count."); 599 } catch (IllegalArgumentException e) { 600 assertThat(e.getMessage()).contains(ERROR_NEGATIVE_COUNT); 601 } 602 } 603 checkTransitiveClosure(Graph<N> originalGraph, Graph<N> expectedClosure)604 private static <N> void checkTransitiveClosure(Graph<N> originalGraph, Graph<N> expectedClosure) { 605 for (N node : originalGraph.nodes()) { 606 assertThat(reachableNodes(originalGraph, node)).isEqualTo(expectedClosure.successors(node)); 607 } 608 assertThat(transitiveClosure(originalGraph)).isEqualTo(expectedClosure); 609 } 610 buildDirectedGraph()611 private static MutableGraph<Integer> buildDirectedGraph() { 612 MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(true).build(); 613 directedGraph.putEdge(N1, N1); 614 directedGraph.putEdge(N1, N2); 615 directedGraph.putEdge(N2, N1); 616 617 return directedGraph; 618 } 619 buildUndirectedGraph()620 private static MutableGraph<Integer> buildUndirectedGraph() { 621 MutableGraph<Integer> undirectedGraph = GraphBuilder.undirected().allowsSelfLoops(true).build(); 622 undirectedGraph.putEdge(N1, N1); 623 undirectedGraph.putEdge(N1, N2); 624 undirectedGraph.putEdge(N2, N1); 625 626 return undirectedGraph; 627 } 628 buildDirectedValueGraph()629 private static MutableValueGraph<Integer, String> buildDirectedValueGraph() { 630 MutableValueGraph<Integer, String> directedGraph = 631 ValueGraphBuilder.directed().allowsSelfLoops(true).build(); 632 directedGraph.putEdgeValue(N1, N1, E11); 633 directedGraph.putEdgeValue(N1, N2, E12); 634 directedGraph.putEdgeValue(N2, N1, E21); 635 636 return directedGraph; 637 } 638 buildUndirectedValueGraph()639 private static MutableValueGraph<Integer, String> buildUndirectedValueGraph() { 640 MutableValueGraph<Integer, String> undirectedGraph = 641 ValueGraphBuilder.undirected().allowsSelfLoops(true).build(); 642 undirectedGraph.putEdgeValue(N1, N1, E11); 643 undirectedGraph.putEdgeValue(N1, N2, E12); 644 undirectedGraph.putEdgeValue(N2, N1, E21); // overwrites E12 645 646 return undirectedGraph; 647 } 648 buildDirectedNetwork()649 private static MutableNetwork<Integer, String> buildDirectedNetwork() { 650 MutableNetwork<Integer, String> directedGraph = 651 NetworkBuilder.directed().allowsParallelEdges(true).allowsSelfLoops(true).build(); 652 directedGraph.addEdge(N1, N1, E11); 653 directedGraph.addEdge(N1, N2, E12); 654 directedGraph.addEdge(N1, N1, E11_A); 655 directedGraph.addEdge(N1, N2, E12_A); 656 directedGraph.addEdge(N2, N1, E21); 657 658 return directedGraph; 659 } 660 buildUndirectedNetwork()661 private static MutableNetwork<Integer, String> buildUndirectedNetwork() { 662 MutableNetwork<Integer, String> undirectedGraph = 663 NetworkBuilder.undirected().allowsParallelEdges(true).allowsSelfLoops(true).build(); 664 undirectedGraph.addEdge(N1, N1, E11); 665 undirectedGraph.addEdge(N1, N2, E12); 666 undirectedGraph.addEdge(N1, N1, E11_A); 667 undirectedGraph.addEdge(N1, N2, E12_A); 668 undirectedGraph.addEdge(N2, N1, E21); 669 670 return undirectedGraph; 671 } 672 } 673