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 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 assertThrows( 403 IllegalArgumentException.class, 404 () -> inducedSubgraph(undirectedGraph, ImmutableSet.of(N1))); 405 } 406 407 @Test copyOf_nullArgument()408 public void copyOf_nullArgument() { 409 assertThrows(NullPointerException.class, () -> copyOf((Graph<?>) null)); 410 } 411 412 @Test copyOf_directedGraph()413 public void copyOf_directedGraph() { 414 Graph<Integer> directedGraph = buildDirectedGraph(); 415 416 Graph<Integer> copy = copyOf(directedGraph); 417 assertThat(copy).isEqualTo(directedGraph); 418 } 419 420 @Test copyOf_undirectedGraph()421 public void copyOf_undirectedGraph() { 422 Graph<Integer> undirectedGraph = buildUndirectedGraph(); 423 424 Graph<Integer> copy = copyOf(undirectedGraph); 425 assertThat(copy).isEqualTo(undirectedGraph); 426 } 427 428 @Test copyOf_directedValueGraph()429 public void copyOf_directedValueGraph() { 430 ValueGraph<Integer, String> directedGraph = buildDirectedValueGraph(); 431 432 ValueGraph<Integer, String> copy = copyOf(directedGraph); 433 assertThat(copy).isEqualTo(directedGraph); 434 } 435 436 @Test copyOf_undirectedValueGraph()437 public void copyOf_undirectedValueGraph() { 438 ValueGraph<Integer, String> undirectedGraph = buildUndirectedValueGraph(); 439 440 ValueGraph<Integer, String> copy = copyOf(undirectedGraph); 441 assertThat(copy).isEqualTo(undirectedGraph); 442 } 443 444 @Test copyOf_directedNetwork()445 public void copyOf_directedNetwork() { 446 Network<Integer, String> directedGraph = buildDirectedNetwork(); 447 448 Network<Integer, String> copy = copyOf(directedGraph); 449 assertThat(copy).isEqualTo(directedGraph); 450 } 451 452 @Test copyOf_undirectedNetwork()453 public void copyOf_undirectedNetwork() { 454 Network<Integer, String> undirectedGraph = buildUndirectedNetwork(); 455 456 Network<Integer, String> copy = copyOf(undirectedGraph); 457 assertThat(copy).isEqualTo(undirectedGraph); 458 } 459 460 // Graph creation tests 461 462 @Test createDirected()463 public void createDirected() { 464 MutableNetwork<Integer, String> directedGraph = NetworkBuilder.directed().build(); 465 assertThat(directedGraph.nodes()).isEmpty(); 466 assertThat(directedGraph.edges()).isEmpty(); 467 assertThat(directedGraph.addEdge(N1, N2, E12)).isTrue(); 468 assertThat(directedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 469 assertThat(directedGraph.edgesConnecting(N2, N1)).isEmpty(); 470 471 // By default, parallel edges are not allowed. 472 IllegalArgumentException e = 473 assertThrows(IllegalArgumentException.class, () -> directedGraph.addEdge(N1, N2, E12_A)); 474 assertThat(e.getMessage()).contains(ERROR_PARALLEL_EDGE); 475 476 // By default, self-loop edges are not allowed. 477 e = assertThrows(IllegalArgumentException.class, () -> directedGraph.addEdge(N1, N1, E11)); 478 assertThat(e).hasMessageThat().contains(ERROR_SELF_LOOP); 479 } 480 481 @Test createUndirected()482 public void createUndirected() { 483 MutableNetwork<Integer, String> undirectedGraph = NetworkBuilder.undirected().build(); 484 assertThat(undirectedGraph.nodes()).isEmpty(); 485 assertThat(undirectedGraph.edges()).isEmpty(); 486 assertThat(undirectedGraph.addEdge(N1, N2, E12)).isTrue(); 487 assertThat(undirectedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 488 assertThat(undirectedGraph.edgesConnecting(N2, N1)).isEqualTo(ImmutableSet.of(E12)); 489 490 // By default, parallel edges are not allowed. 491 IllegalArgumentException e = 492 assertThrows(IllegalArgumentException.class, () -> undirectedGraph.addEdge(N1, N2, E12_A)); 493 assertThat(e.getMessage()).contains(ERROR_PARALLEL_EDGE); 494 e = assertThrows(IllegalArgumentException.class, () -> undirectedGraph.addEdge(N2, N1, E21)); 495 assertThat(e.getMessage()).contains(ERROR_PARALLEL_EDGE); 496 497 // By default, self-loop edges are not allowed. 498 e = assertThrows(IllegalArgumentException.class, () -> undirectedGraph.addEdge(N1, N1, E11)); 499 assertThat(e).hasMessageThat().contains(ERROR_SELF_LOOP); 500 } 501 502 @Test createDirected_multigraph()503 public void createDirected_multigraph() { 504 MutableNetwork<Integer, String> directedMultigraph = 505 NetworkBuilder.directed().allowsParallelEdges(true).build(); 506 assertThat(directedMultigraph.addEdge(N1, N2, E12)).isTrue(); 507 assertThat(directedMultigraph.addEdge(N1, N2, E12_A)).isTrue(); 508 assertThat(directedMultigraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12, E12_A)); 509 assertThat(directedMultigraph.edgesConnecting(N2, N1)).isEmpty(); 510 } 511 512 @Test createUndirected_multigraph()513 public void createUndirected_multigraph() { 514 MutableNetwork<Integer, String> undirectedMultigraph = 515 NetworkBuilder.undirected().allowsParallelEdges(true).build(); 516 assertThat(undirectedMultigraph.addEdge(N1, N2, E12)).isTrue(); 517 assertThat(undirectedMultigraph.addEdge(N1, N2, E12_A)).isTrue(); 518 assertThat(undirectedMultigraph.addEdge(N2, N1, E21)).isTrue(); 519 assertThat(undirectedMultigraph.edgesConnecting(N1, N2)) 520 .isEqualTo(ImmutableSet.of(E12, E12_A, E21)); 521 } 522 523 @Test createDirected_expectedNodeCount()524 public void createDirected_expectedNodeCount() { 525 MutableNetwork<Integer, String> directedGraph = 526 NetworkBuilder.directed().expectedNodeCount(NODE_COUNT).build(); 527 assertThat(directedGraph.addEdge(N1, N2, E12)).isTrue(); 528 assertThat(directedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 529 assertThat(directedGraph.edgesConnecting(N2, N1)).isEmpty(); 530 } 531 532 @Test createUndirected_expectedNodeCount()533 public void createUndirected_expectedNodeCount() { 534 MutableNetwork<Integer, String> undirectedGraph = 535 NetworkBuilder.undirected().expectedNodeCount(NODE_COUNT).build(); 536 assertThat(undirectedGraph.addEdge(N1, N2, E12)).isTrue(); 537 assertThat(undirectedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 538 assertThat(undirectedGraph.edgesConnecting(N2, N1)).isEqualTo(ImmutableSet.of(E12)); 539 } 540 541 @Test builder_expectedNodeCount_negative()542 public void builder_expectedNodeCount_negative() { 543 IllegalArgumentException e = 544 assertThrows( 545 IllegalArgumentException.class, () -> NetworkBuilder.directed().expectedNodeCount(-1)); 546 assertThat(e.getMessage()).contains(ERROR_NEGATIVE_COUNT); 547 } 548 549 @Test createDirected_expectedEdgeCount()550 public void createDirected_expectedEdgeCount() { 551 MutableNetwork<Integer, String> directedGraph = 552 NetworkBuilder.directed().expectedEdgeCount(EDGE_COUNT).build(); 553 assertThat(directedGraph.addEdge(N1, N2, E12)).isTrue(); 554 assertThat(directedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 555 assertThat(directedGraph.edgesConnecting(N2, N1)).isEmpty(); 556 } 557 558 @Test createUndirected_expectedEdgeCount()559 public void createUndirected_expectedEdgeCount() { 560 MutableNetwork<Integer, String> undirectedGraph = 561 NetworkBuilder.undirected().expectedEdgeCount(EDGE_COUNT).build(); 562 assertThat(undirectedGraph.addEdge(N1, N2, E12)).isTrue(); 563 assertThat(undirectedGraph.edgesConnecting(N1, N2)).isEqualTo(ImmutableSet.of(E12)); 564 assertThat(undirectedGraph.edgesConnecting(N2, N1)).isEqualTo(ImmutableSet.of(E12)); 565 } 566 567 @Test builder_expectedEdgeCount_negative()568 public void builder_expectedEdgeCount_negative() { 569 IllegalArgumentException e = 570 assertThrows( 571 IllegalArgumentException.class, () -> NetworkBuilder.directed().expectedEdgeCount(-1)); 572 assertThat(e.getMessage()).contains(ERROR_NEGATIVE_COUNT); 573 } 574 checkTransitiveClosure(Graph<N> originalGraph, Graph<N> expectedClosure)575 private static <N> void checkTransitiveClosure(Graph<N> originalGraph, Graph<N> expectedClosure) { 576 for (N node : originalGraph.nodes()) { 577 assertThat(reachableNodes(originalGraph, node)).isEqualTo(expectedClosure.successors(node)); 578 } 579 assertThat(transitiveClosure(originalGraph)).isEqualTo(expectedClosure); 580 } 581 buildDirectedGraph()582 private static MutableGraph<Integer> buildDirectedGraph() { 583 MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(true).build(); 584 directedGraph.putEdge(N1, N1); 585 directedGraph.putEdge(N1, N2); 586 directedGraph.putEdge(N2, N1); 587 588 return directedGraph; 589 } 590 buildUndirectedGraph()591 private static MutableGraph<Integer> buildUndirectedGraph() { 592 MutableGraph<Integer> undirectedGraph = GraphBuilder.undirected().allowsSelfLoops(true).build(); 593 undirectedGraph.putEdge(N1, N1); 594 undirectedGraph.putEdge(N1, N2); 595 undirectedGraph.putEdge(N2, N1); 596 597 return undirectedGraph; 598 } 599 buildDirectedValueGraph()600 private static MutableValueGraph<Integer, String> buildDirectedValueGraph() { 601 MutableValueGraph<Integer, String> directedGraph = 602 ValueGraphBuilder.directed().allowsSelfLoops(true).build(); 603 directedGraph.putEdgeValue(N1, N1, E11); 604 directedGraph.putEdgeValue(N1, N2, E12); 605 directedGraph.putEdgeValue(N2, N1, E21); 606 607 return directedGraph; 608 } 609 buildUndirectedValueGraph()610 private static MutableValueGraph<Integer, String> buildUndirectedValueGraph() { 611 MutableValueGraph<Integer, String> undirectedGraph = 612 ValueGraphBuilder.undirected().allowsSelfLoops(true).build(); 613 undirectedGraph.putEdgeValue(N1, N1, E11); 614 undirectedGraph.putEdgeValue(N1, N2, E12); 615 undirectedGraph.putEdgeValue(N2, N1, E21); // overwrites E12 616 617 return undirectedGraph; 618 } 619 buildDirectedNetwork()620 private static MutableNetwork<Integer, String> buildDirectedNetwork() { 621 MutableNetwork<Integer, String> directedGraph = 622 NetworkBuilder.directed().allowsParallelEdges(true).allowsSelfLoops(true).build(); 623 directedGraph.addEdge(N1, N1, E11); 624 directedGraph.addEdge(N1, N2, E12); 625 directedGraph.addEdge(N1, N1, E11_A); 626 directedGraph.addEdge(N1, N2, E12_A); 627 directedGraph.addEdge(N2, N1, E21); 628 629 return directedGraph; 630 } 631 buildUndirectedNetwork()632 private static MutableNetwork<Integer, String> buildUndirectedNetwork() { 633 MutableNetwork<Integer, String> undirectedGraph = 634 NetworkBuilder.undirected().allowsParallelEdges(true).allowsSelfLoops(true).build(); 635 undirectedGraph.addEdge(N1, N1, E11); 636 undirectedGraph.addEdge(N1, N2, E12); 637 undirectedGraph.addEdge(N1, N1, E11_A); 638 undirectedGraph.addEdge(N1, N2, E12_A); 639 undirectedGraph.addEdge(N2, N1, E21); 640 641 return undirectedGraph; 642 } 643 } 644