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