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