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.edgeConnectingOrNull(N1, N2)).isNull(); 323 324 for (Integer node : directedGraph.nodes()) { 325 assertThat(directedGraph.inDegree(node)).isSameInstanceAs(transpose.outDegree(node)); 326 assertThat(directedGraph.outDegree(node)).isSameInstanceAs(transpose.inDegree(node)); 327 } 328 329 directedGraph.addEdge(N2, N1, E21); 330 // View should be updated. 331 assertThat(transpose.edgesConnecting(N1, N2)).containsExactly(E21); 332 assertThat(transpose.edgeConnectingOrNull(N1, N2)).isEqualTo(E21); 333 334 AbstractNetworkTest.validateNetwork(transpose); 335 } 336 337 @Test inducedSubgraph_graph()338 public void inducedSubgraph_graph() { 339 Set<Integer> nodeSubset = ImmutableSet.of(N1, N2, N4); 340 341 MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(true).build(); 342 directedGraph.putEdge(N1, N2); 343 directedGraph.putEdge(N2, N1); 344 directedGraph.putEdge(N1, N3); // only incident to one node in nodeSubset 345 directedGraph.putEdge(N4, N4); 346 directedGraph.putEdge(5, 6); // not incident to any node in nodeSubset 347 348 MutableGraph<Integer> expectedSubgraph = GraphBuilder.directed().allowsSelfLoops(true).build(); 349 expectedSubgraph.putEdge(N1, N2); 350 expectedSubgraph.putEdge(N2, N1); 351 expectedSubgraph.putEdge(N4, N4); 352 353 assertThat(inducedSubgraph(directedGraph, nodeSubset)).isEqualTo(expectedSubgraph); 354 } 355 356 @Test inducedSubgraph_valueGraph()357 public void inducedSubgraph_valueGraph() { 358 Set<Integer> nodeSubset = ImmutableSet.of(N1, N2, N4); 359 360 MutableValueGraph<Integer, String> directedGraph = 361 ValueGraphBuilder.directed().allowsSelfLoops(true).build(); 362 directedGraph.putEdgeValue(N1, N2, E12); 363 directedGraph.putEdgeValue(N2, N1, E21); 364 directedGraph.putEdgeValue(N1, N3, E13); // only incident to one node in nodeSubset 365 directedGraph.putEdgeValue(N4, N4, E44); 366 directedGraph.putEdgeValue(5, 6, "5-6"); // not incident to any node in nodeSubset 367 368 MutableValueGraph<Integer, String> expectedSubgraph = 369 ValueGraphBuilder.directed().allowsSelfLoops(true).build(); 370 expectedSubgraph.putEdgeValue(N1, N2, E12); 371 expectedSubgraph.putEdgeValue(N2, N1, E21); 372 expectedSubgraph.putEdgeValue(N4, N4, E44); 373 374 assertThat(inducedSubgraph(directedGraph, nodeSubset)).isEqualTo(expectedSubgraph); 375 } 376 377 @Test inducedSubgraph_network()378 public void inducedSubgraph_network() { 379 Set<Integer> nodeSubset = ImmutableSet.of(N1, N2, N4); 380 381 MutableNetwork<Integer, String> directedGraph = 382 NetworkBuilder.directed().allowsSelfLoops(true).build(); 383 directedGraph.addEdge(N1, N2, E12); 384 directedGraph.addEdge(N2, N1, E21); 385 directedGraph.addEdge(N1, N3, E13); // only incident to one node in nodeSubset 386 directedGraph.addEdge(N4, N4, E44); 387 directedGraph.addEdge(5, 6, "5-6"); // not incident to any node in nodeSubset 388 389 MutableNetwork<Integer, String> expectedSubgraph = 390 NetworkBuilder.directed().allowsSelfLoops(true).build(); 391 expectedSubgraph.addEdge(N1, N2, E12); 392 expectedSubgraph.addEdge(N2, N1, E21); 393 expectedSubgraph.addEdge(N4, N4, E44); 394 395 assertThat(inducedSubgraph(directedGraph, nodeSubset)).isEqualTo(expectedSubgraph); 396 } 397 398 @Test inducedSubgraph_nodeNotInGraph()399 public void inducedSubgraph_nodeNotInGraph() { 400 MutableNetwork<Integer, String> undirectedGraph = NetworkBuilder.undirected().build(); 401 402 try { 403 inducedSubgraph(undirectedGraph, ImmutableSet.of(N1)); 404 fail("Should have rejected getting induced subgraph with node not in original graph."); 405 } catch (IllegalArgumentException expected) { 406 } 407 } 408 409 @Test copyOf_nullArgument()410 public void copyOf_nullArgument() { 411 try { 412 copyOf((Graph<?>) null); 413 fail("Should have rejected a null graph."); 414 } catch (NullPointerException expected) { 415 } 416 } 417 418 @Test copyOf_directedGraph()419 public void copyOf_directedGraph() { 420 Graph<Integer> directedGraph = buildDirectedGraph(); 421 422 Graph<Integer> copy = copyOf(directedGraph); 423 assertThat(copy).isEqualTo(directedGraph); 424 } 425 426 @Test copyOf_undirectedGraph()427 public void copyOf_undirectedGraph() { 428 Graph<Integer> undirectedGraph = buildUndirectedGraph(); 429 430 Graph<Integer> copy = copyOf(undirectedGraph); 431 assertThat(copy).isEqualTo(undirectedGraph); 432 } 433 434 @Test copyOf_directedValueGraph()435 public void copyOf_directedValueGraph() { 436 ValueGraph<Integer, String> directedGraph = buildDirectedValueGraph(); 437 438 ValueGraph<Integer, String> copy = copyOf(directedGraph); 439 assertThat(copy).isEqualTo(directedGraph); 440 } 441 442 @Test copyOf_undirectedValueGraph()443 public void copyOf_undirectedValueGraph() { 444 ValueGraph<Integer, String> undirectedGraph = buildUndirectedValueGraph(); 445 446 ValueGraph<Integer, String> copy = copyOf(undirectedGraph); 447 assertThat(copy).isEqualTo(undirectedGraph); 448 } 449 450 @Test copyOf_directedNetwork()451 public void copyOf_directedNetwork() { 452 Network<Integer, String> directedGraph = buildDirectedNetwork(); 453 454 Network<Integer, String> copy = copyOf(directedGraph); 455 assertThat(copy).isEqualTo(directedGraph); 456 } 457 458 @Test copyOf_undirectedNetwork()459 public void copyOf_undirectedNetwork() { 460 Network<Integer, String> undirectedGraph = buildUndirectedNetwork(); 461 462 Network<Integer, String> copy = copyOf(undirectedGraph); 463 assertThat(copy).isEqualTo(undirectedGraph); 464 } 465 466 // Graph creation tests 467 468 @Test createDirected()469 public void createDirected() { 470 MutableNetwork<Integer, String> directedGraph = NetworkBuilder.directed().build(); 471 assertThat(directedGraph.nodes()).isEmpty(); 472 assertThat(directedGraph.edges()).isEmpty(); 473 assertThat(directedGraph.addEdge(N1, N2, E12)).isTrue(); 474 assertThat(directedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 475 assertThat(directedGraph.edgesConnecting(N2, N1)).isEmpty(); 476 477 // By default, parallel edges are not allowed. 478 try { 479 directedGraph.addEdge(N1, N2, E12_A); 480 fail(ERROR_ADDED_PARALLEL_EDGE); 481 } catch (IllegalArgumentException e) { 482 assertThat(e.getMessage()).contains(ERROR_PARALLEL_EDGE); 483 } 484 485 // By default, self-loop edges are not allowed. 486 try { 487 directedGraph.addEdge(N1, N1, E11); 488 fail(ERROR_ADDED_SELF_LOOP); 489 } catch (IllegalArgumentException e) { 490 assertThat(e).hasMessageThat().contains(ERROR_SELF_LOOP); 491 } 492 } 493 494 @Test createUndirected()495 public void createUndirected() { 496 MutableNetwork<Integer, String> undirectedGraph = NetworkBuilder.undirected().build(); 497 assertThat(undirectedGraph.nodes()).isEmpty(); 498 assertThat(undirectedGraph.edges()).isEmpty(); 499 assertThat(undirectedGraph.addEdge(N1, N2, E12)).isTrue(); 500 assertThat(undirectedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 501 assertThat(undirectedGraph.edgesConnecting(N2, N1)).isEqualTo(ImmutableSet.of(E12)); 502 503 // By default, parallel edges are not allowed. 504 try { 505 undirectedGraph.addEdge(N1, N2, E12_A); 506 fail(ERROR_ADDED_PARALLEL_EDGE); 507 } catch (IllegalArgumentException e) { 508 assertThat(e.getMessage()).contains(ERROR_PARALLEL_EDGE); 509 } 510 try { 511 undirectedGraph.addEdge(N2, N1, E21); 512 fail(ERROR_ADDED_PARALLEL_EDGE); 513 } catch (IllegalArgumentException e) { 514 assertThat(e.getMessage()).contains(ERROR_PARALLEL_EDGE); 515 } 516 517 // By default, self-loop edges are not allowed. 518 try { 519 undirectedGraph.addEdge(N1, N1, E11); 520 fail(ERROR_ADDED_SELF_LOOP); 521 } catch (IllegalArgumentException e) { 522 assertThat(e).hasMessageThat().contains(ERROR_SELF_LOOP); 523 } 524 } 525 526 @Test createDirected_multigraph()527 public void createDirected_multigraph() { 528 MutableNetwork<Integer, String> directedMultigraph = 529 NetworkBuilder.directed().allowsParallelEdges(true).build(); 530 assertThat(directedMultigraph.addEdge(N1, N2, E12)).isTrue(); 531 assertThat(directedMultigraph.addEdge(N1, N2, E12_A)).isTrue(); 532 assertThat(directedMultigraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12, E12_A)); 533 assertThat(directedMultigraph.edgesConnecting(N2, N1)).isEmpty(); 534 } 535 536 @Test createUndirected_multigraph()537 public void createUndirected_multigraph() { 538 MutableNetwork<Integer, String> undirectedMultigraph = 539 NetworkBuilder.undirected().allowsParallelEdges(true).build(); 540 assertThat(undirectedMultigraph.addEdge(N1, N2, E12)).isTrue(); 541 assertThat(undirectedMultigraph.addEdge(N1, N2, E12_A)).isTrue(); 542 assertThat(undirectedMultigraph.addEdge(N2, N1, E21)).isTrue(); 543 assertThat(undirectedMultigraph.edgesConnecting(N1, N2)) 544 .isEqualTo(ImmutableSet.of(E12, E12_A, E21)); 545 } 546 547 @Test createDirected_expectedNodeCount()548 public void createDirected_expectedNodeCount() { 549 MutableNetwork<Integer, String> directedGraph = 550 NetworkBuilder.directed().expectedNodeCount(NODE_COUNT).build(); 551 assertThat(directedGraph.addEdge(N1, N2, E12)).isTrue(); 552 assertThat(directedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 553 assertThat(directedGraph.edgesConnecting(N2, N1)).isEmpty(); 554 } 555 556 @Test createUndirected_expectedNodeCount()557 public void createUndirected_expectedNodeCount() { 558 MutableNetwork<Integer, String> undirectedGraph = 559 NetworkBuilder.undirected().expectedNodeCount(NODE_COUNT).build(); 560 assertThat(undirectedGraph.addEdge(N1, N2, E12)).isTrue(); 561 assertThat(undirectedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 562 assertThat(undirectedGraph.edgesConnecting(N2, N1)).isEqualTo(ImmutableSet.of(E12)); 563 } 564 565 @Test builder_expectedNodeCount_negative()566 public void builder_expectedNodeCount_negative() { 567 try { 568 NetworkBuilder.directed().expectedNodeCount(-1); 569 fail("Should have rejected negative expected node count."); 570 } catch (IllegalArgumentException e) { 571 assertThat(e.getMessage()).contains(ERROR_NEGATIVE_COUNT); 572 } 573 } 574 575 @Test createDirected_expectedEdgeCount()576 public void createDirected_expectedEdgeCount() { 577 MutableNetwork<Integer, String> directedGraph = 578 NetworkBuilder.directed().expectedEdgeCount(EDGE_COUNT).build(); 579 assertThat(directedGraph.addEdge(N1, N2, E12)).isTrue(); 580 assertThat(directedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 581 assertThat(directedGraph.edgesConnecting(N2, N1)).isEmpty(); 582 } 583 584 @Test createUndirected_expectedEdgeCount()585 public void createUndirected_expectedEdgeCount() { 586 MutableNetwork<Integer, String> undirectedGraph = 587 NetworkBuilder.undirected().expectedEdgeCount(EDGE_COUNT).build(); 588 assertThat(undirectedGraph.addEdge(N1, N2, E12)).isTrue(); 589 assertThat(undirectedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 590 assertThat(undirectedGraph.edgesConnecting(N2, N1)).isEqualTo(ImmutableSet.of(E12)); 591 } 592 593 @Test builder_expectedEdgeCount_negative()594 public void builder_expectedEdgeCount_negative() { 595 try { 596 NetworkBuilder.directed().expectedEdgeCount(-1); 597 fail("Should have rejected negative expected edge count."); 598 } catch (IllegalArgumentException e) { 599 assertThat(e.getMessage()).contains(ERROR_NEGATIVE_COUNT); 600 } 601 } 602 checkTransitiveClosure(Graph<N> originalGraph, Graph<N> expectedClosure)603 private static <N> void checkTransitiveClosure(Graph<N> originalGraph, Graph<N> expectedClosure) { 604 for (N node : originalGraph.nodes()) { 605 assertThat(reachableNodes(originalGraph, node)).isEqualTo(expectedClosure.successors(node)); 606 } 607 assertThat(transitiveClosure(originalGraph)).isEqualTo(expectedClosure); 608 } 609 buildDirectedGraph()610 private static MutableGraph<Integer> buildDirectedGraph() { 611 MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(true).build(); 612 directedGraph.putEdge(N1, N1); 613 directedGraph.putEdge(N1, N2); 614 directedGraph.putEdge(N2, N1); 615 616 return directedGraph; 617 } 618 buildUndirectedGraph()619 private static MutableGraph<Integer> buildUndirectedGraph() { 620 MutableGraph<Integer> undirectedGraph = GraphBuilder.undirected().allowsSelfLoops(true).build(); 621 undirectedGraph.putEdge(N1, N1); 622 undirectedGraph.putEdge(N1, N2); 623 undirectedGraph.putEdge(N2, N1); 624 625 return undirectedGraph; 626 } 627 buildDirectedValueGraph()628 private static MutableValueGraph<Integer, String> buildDirectedValueGraph() { 629 MutableValueGraph<Integer, String> directedGraph = 630 ValueGraphBuilder.directed().allowsSelfLoops(true).build(); 631 directedGraph.putEdgeValue(N1, N1, E11); 632 directedGraph.putEdgeValue(N1, N2, E12); 633 directedGraph.putEdgeValue(N2, N1, E21); 634 635 return directedGraph; 636 } 637 buildUndirectedValueGraph()638 private static MutableValueGraph<Integer, String> buildUndirectedValueGraph() { 639 MutableValueGraph<Integer, String> undirectedGraph = 640 ValueGraphBuilder.undirected().allowsSelfLoops(true).build(); 641 undirectedGraph.putEdgeValue(N1, N1, E11); 642 undirectedGraph.putEdgeValue(N1, N2, E12); 643 undirectedGraph.putEdgeValue(N2, N1, E21); // overwrites E12 644 645 return undirectedGraph; 646 } 647 buildDirectedNetwork()648 private static MutableNetwork<Integer, String> buildDirectedNetwork() { 649 MutableNetwork<Integer, String> directedGraph = 650 NetworkBuilder.directed().allowsParallelEdges(true).allowsSelfLoops(true).build(); 651 directedGraph.addEdge(N1, N1, E11); 652 directedGraph.addEdge(N1, N2, E12); 653 directedGraph.addEdge(N1, N1, E11_A); 654 directedGraph.addEdge(N1, N2, E12_A); 655 directedGraph.addEdge(N2, N1, E21); 656 657 return directedGraph; 658 } 659 buildUndirectedNetwork()660 private static MutableNetwork<Integer, String> buildUndirectedNetwork() { 661 MutableNetwork<Integer, String> undirectedGraph = 662 NetworkBuilder.undirected().allowsParallelEdges(true).allowsSelfLoops(true).build(); 663 undirectedGraph.addEdge(N1, N1, E11); 664 undirectedGraph.addEdge(N1, N2, E12); 665 undirectedGraph.addEdge(N1, N1, E11_A); 666 undirectedGraph.addEdge(N1, N2, E12_A); 667 undirectedGraph.addEdge(N2, N1, E21); 668 669 return undirectedGraph; 670 } 671 } 672