1 /* 2 3 * Copyright (C) 2017 The Guava Authors 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 package com.google.common.graph; 19 20 import static com.google.common.base.Preconditions.checkArgument; 21 import static com.google.common.base.Preconditions.checkNotNull; 22 import static com.google.common.collect.Lists.charactersOf; 23 import static com.google.common.truth.Truth.assertThat; 24 import static org.junit.Assert.assertThrows; 25 26 import com.google.common.collect.HashMultiset; 27 import com.google.common.collect.ImmutableList; 28 import com.google.common.collect.ImmutableMultimap; 29 import com.google.common.collect.Iterables; 30 import com.google.common.collect.Multiset; 31 import com.google.common.collect.Ordering; 32 import com.google.common.primitives.Chars; 33 import org.junit.Test; 34 import org.junit.runner.RunWith; 35 import org.junit.runners.JUnit4; 36 37 @RunWith(JUnit4.class) 38 public class TraverserTest { 39 40 /** 41 * The undirected graph in the {@link Traverser#breadthFirst(Object)} javadoc: 42 * 43 * <pre>{@code 44 * b ---- a ---- d 45 * | | 46 * | | 47 * e ---- c ---- f 48 * }</pre> 49 */ 50 private static final SuccessorsFunction<Character> JAVADOC_GRAPH = 51 createUndirectedGraph("ba", "ad", "be", "ac", "ec", "cf"); 52 53 /** 54 * A diamond shaped directed graph (arrows going down): 55 * 56 * <pre>{@code 57 * a 58 * / \ 59 * b c 60 * \ / 61 * d 62 * }</pre> 63 */ 64 private static final SuccessorsFunction<Character> DIAMOND_GRAPH = 65 createDirectedGraph("ab", "ac", "bd", "cd"); 66 67 /** 68 * Same as {@link #DIAMOND_GRAPH}, but with an extra c->a edge and some self edges: 69 * 70 * <pre>{@code 71 * a<> 72 * / \\ 73 * b c 74 * \ / 75 * d<> 76 * }</pre> 77 * 78 * {@code <>} indicates a self-loop 79 */ 80 private static final SuccessorsFunction<Character> MULTI_GRAPH = 81 createDirectedGraph("aa", "dd", "ab", "ac", "ca", "cd", "bd"); 82 83 /** A directed graph with a single cycle: a -> b -> c -> d -> a. */ 84 private static final SuccessorsFunction<Character> CYCLE_GRAPH = 85 createDirectedGraph("ab", "bc", "cd", "da"); 86 87 /** 88 * Same as {@link #CYCLE_GRAPH}, but with an extra a->c edge. 89 * 90 * <pre>{@code 91 * |--------------| 92 * v | 93 * a -> b -> c -> d 94 * | ^ 95 * |---------| 96 * }</pre> 97 */ 98 private static final SuccessorsFunction<Character> TWO_CYCLES_GRAPH = 99 createDirectedGraph("ab", "ac", "bc", "cd", "da"); 100 101 /** 102 * A tree-shaped graph that looks as follows (all edges are directed facing downwards): 103 * 104 * <pre>{@code 105 * h 106 * /|\ 107 * / | \ 108 * / | \ 109 * d e g 110 * /|\ | 111 * / | \ | 112 * a b c f 113 * }</pre> 114 */ 115 private static final SuccessorsFunction<Character> TREE = 116 createDirectedGraph("hd", "he", "hg", "da", "db", "dc", "gf"); 117 118 /** 119 * Two disjoint tree-shaped graphs that look as follows (all edges are directed facing downwards): 120 * 121 * <pre>{@code 122 * a c 123 * | | 124 * | | 125 * b d 126 * }</pre> 127 */ 128 private static final SuccessorsFunction<Character> TWO_TREES = createDirectedGraph("ab", "cd"); 129 130 /** 131 * A graph consisting of a single root {@code a}: 132 * 133 * <pre>{@code 134 * a 135 * }</pre> 136 */ 137 private static final SuccessorsFunction<Character> SINGLE_ROOT = createSingleRootGraph(); 138 139 /** 140 * A graph that is not a tree (for example, it has two antiparallel edge between {@code e} and 141 * {@code f} and thus has a cycle) but is a valid input to {@link Traverser#forTree} when starting 142 * e.g. at node {@code a} (all edges without an arrow are directed facing downwards): 143 * 144 * <pre>{@code 145 * a 146 * / 147 * b e <----> f 148 * / \ / 149 * c d 150 * }</pre> 151 */ 152 private static final SuccessorsFunction<Character> CYCLIC_GRAPH_CONTAINING_TREE = 153 createDirectedGraph("ab", "bc", "bd", "ed", "ef", "fe"); 154 155 /** 156 * A graph that is not a tree (for example, {@code h} is reachable from {@code f} via both {@code 157 * e} and {@code g}) but is a valid input to {@link Traverser#forTree} when starting e.g. at node 158 * {@code a} (all edges are directed facing downwards): 159 * 160 * <pre>{@code 161 * a f 162 * / / \ 163 * b e g 164 * / \ / \ / 165 * c d h 166 * }</pre> 167 */ 168 private static final SuccessorsFunction<Character> GRAPH_CONTAINING_TREE_AND_DIAMOND = 169 createDirectedGraph("ab", "fe", "fg", "bc", "bd", "ed", "eh", "gh"); 170 171 @Test forGraph_breadthFirst_javadocExample_canBeIteratedMultipleTimes()172 public void forGraph_breadthFirst_javadocExample_canBeIteratedMultipleTimes() { 173 Iterable<Character> result = Traverser.forGraph(JAVADOC_GRAPH).breadthFirst('a'); 174 175 assertEqualCharNodes(result, "abcdef"); 176 assertEqualCharNodes(result, "abcdef"); 177 } 178 179 @Test forGraph_breadthFirstIterable_javadocExample_canBeIteratedMultipleTimes()180 public void forGraph_breadthFirstIterable_javadocExample_canBeIteratedMultipleTimes() { 181 Iterable<Character> result = Traverser.forGraph(JAVADOC_GRAPH).breadthFirst(charactersOf("bf")); 182 183 assertEqualCharNodes(result, "bfaecd"); 184 assertEqualCharNodes(result, "bfaecd"); 185 } 186 187 @Test forGraph_breadthFirst_infinite()188 public void forGraph_breadthFirst_infinite() { 189 Iterable<Integer> result = 190 Traverser.forGraph(fixedSuccessors(Iterables.cycle(1, 2, 3))).breadthFirst(0); 191 assertThat(Iterables.limit(result, 4)).containsExactly(0, 1, 2, 3).inOrder(); 192 } 193 194 @Test forGraph_breadthFirst_diamond()195 public void forGraph_breadthFirst_diamond() { 196 Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); 197 assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); 198 assertEqualCharNodes(traverser.breadthFirst('b'), "bd"); 199 assertEqualCharNodes(traverser.breadthFirst('c'), "cd"); 200 assertEqualCharNodes(traverser.breadthFirst('d'), "d"); 201 } 202 203 @Test forGraph_breadthFirstIterable_diamond()204 public void forGraph_breadthFirstIterable_diamond() { 205 Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); 206 assertEqualCharNodes(traverser.breadthFirst(charactersOf("")), ""); 207 assertEqualCharNodes(traverser.breadthFirst(charactersOf("bc")), "bcd"); 208 assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd"); 209 assertEqualCharNodes(traverser.breadthFirst(charactersOf("acdb")), "acdb"); 210 assertEqualCharNodes(traverser.breadthFirst(charactersOf("db")), "db"); 211 } 212 213 @Test forGraph_breadthFirst_multiGraph()214 public void forGraph_breadthFirst_multiGraph() { 215 Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); 216 assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); 217 assertEqualCharNodes(traverser.breadthFirst('b'), "bd"); 218 assertEqualCharNodes(traverser.breadthFirst('c'), "cadb"); 219 assertEqualCharNodes(traverser.breadthFirst('d'), "d"); 220 } 221 222 @Test forGraph_breadthFirstIterable_multiGraph()223 public void forGraph_breadthFirstIterable_multiGraph() { 224 Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); 225 assertEqualCharNodes(traverser.breadthFirst(charactersOf("ac")), "acbd"); 226 assertEqualCharNodes(traverser.breadthFirst(charactersOf("cb")), "cbad"); 227 assertEqualCharNodes(traverser.breadthFirst(charactersOf("db")), "db"); 228 assertEqualCharNodes(traverser.breadthFirst(charactersOf("d")), "d"); 229 } 230 231 @Test forGraph_breadthFirst_cycle()232 public void forGraph_breadthFirst_cycle() { 233 Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); 234 assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); 235 assertEqualCharNodes(traverser.breadthFirst('b'), "bcda"); 236 assertEqualCharNodes(traverser.breadthFirst('c'), "cdab"); 237 assertEqualCharNodes(traverser.breadthFirst('d'), "dabc"); 238 } 239 240 @Test forGraph_breadthFirstIterable_cycle()241 public void forGraph_breadthFirstIterable_cycle() { 242 Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); 243 assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd"); 244 assertEqualCharNodes(traverser.breadthFirst(charactersOf("bd")), "bdca"); 245 assertEqualCharNodes(traverser.breadthFirst(charactersOf("dc")), "dcab"); 246 assertEqualCharNodes(traverser.breadthFirst(charactersOf("bc")), "bcda"); 247 } 248 249 @Test forGraph_breadthFirst_twoCycles()250 public void forGraph_breadthFirst_twoCycles() { 251 Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); 252 assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); 253 assertEqualCharNodes(traverser.breadthFirst('b'), "bcda"); 254 assertEqualCharNodes(traverser.breadthFirst('c'), "cdab"); 255 assertEqualCharNodes(traverser.breadthFirst('d'), "dabc"); 256 } 257 258 @Test forGraph_breadthFirstIterable_twoCycles()259 public void forGraph_breadthFirstIterable_twoCycles() { 260 Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); 261 assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd"); 262 assertEqualCharNodes(traverser.breadthFirst(charactersOf("bd")), "bdca"); 263 assertEqualCharNodes(traverser.breadthFirst(charactersOf("dc")), "dcab"); 264 assertEqualCharNodes(traverser.breadthFirst(charactersOf("bc")), "bcda"); 265 } 266 267 @Test forGraph_breadthFirst_tree()268 public void forGraph_breadthFirst_tree() throws Exception { 269 Traverser<Character> traverser = Traverser.forGraph(TREE); 270 271 assertEqualCharNodes(traverser.breadthFirst('h'), "hdegabcf"); 272 assertEqualCharNodes(traverser.breadthFirst('d'), "dabc"); 273 assertEqualCharNodes(traverser.breadthFirst('a'), "a"); 274 } 275 276 @Test forGraph_breadthFirstIterable_tree()277 public void forGraph_breadthFirstIterable_tree() throws Exception { 278 Traverser<Character> traverser = Traverser.forGraph(TREE); 279 280 assertEqualCharNodes(traverser.breadthFirst(charactersOf("hg")), "hgdefabc"); 281 assertEqualCharNodes(traverser.breadthFirst(charactersOf("gd")), "gdfabc"); 282 assertEqualCharNodes(traverser.breadthFirst(charactersOf("bdgh")), "bdghacfe"); 283 } 284 285 @Test forGraph_breadthFirst_twoTrees()286 public void forGraph_breadthFirst_twoTrees() { 287 Iterable<Character> result = Traverser.forGraph(TWO_TREES).breadthFirst('a'); 288 289 assertEqualCharNodes(result, "ab"); 290 } 291 292 @Test forGraph_breadthFirstIterable_twoTrees()293 public void forGraph_breadthFirstIterable_twoTrees() { 294 assertEqualCharNodes(Traverser.forGraph(TWO_TREES).breadthFirst(charactersOf("a")), "ab"); 295 assertEqualCharNodes(Traverser.forGraph(TWO_TREES).breadthFirst(charactersOf("ac")), "acbd"); 296 } 297 298 @Test forGraph_breadthFirst_singleRoot()299 public void forGraph_breadthFirst_singleRoot() { 300 Iterable<Character> result = Traverser.forGraph(SINGLE_ROOT).breadthFirst('a'); 301 302 assertEqualCharNodes(result, "a"); 303 } 304 305 @Test forGraph_breadthFirstIterable_singleRoot()306 public void forGraph_breadthFirstIterable_singleRoot() { 307 Iterable<Character> result = Traverser.forGraph(SINGLE_ROOT).breadthFirst(charactersOf("a")); 308 309 assertEqualCharNodes(result, "a"); 310 } 311 312 @Test forGraph_breadthFirst_emptyGraph()313 public void forGraph_breadthFirst_emptyGraph() { 314 assertThrows( 315 IllegalArgumentException.class, 316 () -> Traverser.forGraph(createDirectedGraph()).breadthFirst('a')); 317 } 318 319 /** 320 * Checks that the elements of the iterable are calculated on the fly. Concretely, that means that 321 * {@link SuccessorsFunction#successors(Object)} can only be called for a subset of all nodes. 322 */ 323 @Test forGraph_breadthFirstIterable_emptyGraph()324 public void forGraph_breadthFirstIterable_emptyGraph() { 325 assertEqualCharNodes( 326 Traverser.forGraph(createDirectedGraph()).breadthFirst(charactersOf("")), ""); 327 assertThrows( 328 IllegalArgumentException.class, 329 () -> Traverser.forGraph(createDirectedGraph()).breadthFirst(charactersOf("a"))); 330 } 331 332 /** 333 * Checks that the elements of the iterable are calculated on the fly. Concretely, that means that 334 * {@link SuccessorsFunction#successors(Object)} can only be called for a subset of all nodes. 335 */ 336 @Test forGraph_breadthFirst_iterableIsLazy()337 public void forGraph_breadthFirst_iterableIsLazy() { 338 RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); 339 Iterable<Character> result = Traverser.forGraph(graph).breadthFirst('a'); 340 341 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 342 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b'); 343 344 // Iterate again to see if calculation is done again 345 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 346 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b'); 347 } 348 349 @Test forGraph_breadthFirstIterable_iterableIsLazy()350 public void forGraph_breadthFirstIterable_iterableIsLazy() { 351 RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); 352 Iterable<Character> result = Traverser.forGraph(graph).breadthFirst(charactersOf("ab")); 353 354 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 355 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'b'); 356 357 // Iterate again to see if calculation is done again 358 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 359 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b', 'b'); 360 } 361 362 @Test forGraph_depthFirstPreOrder_javadocExample_canBeIteratedMultipleTimes()363 public void forGraph_depthFirstPreOrder_javadocExample_canBeIteratedMultipleTimes() { 364 Iterable<Character> result = Traverser.forGraph(JAVADOC_GRAPH).depthFirstPreOrder('a'); 365 366 assertEqualCharNodes(result, "abecfd"); 367 assertEqualCharNodes(result, "abecfd"); 368 } 369 370 @Test forGraph_depthFirstPreOrderIterable_javadocExample_canBeIteratedMultipleTimes()371 public void forGraph_depthFirstPreOrderIterable_javadocExample_canBeIteratedMultipleTimes() { 372 Iterable<Character> result = 373 Traverser.forGraph(JAVADOC_GRAPH).depthFirstPreOrder(charactersOf("bc")); 374 375 assertEqualCharNodes(result, "bacefd"); 376 assertEqualCharNodes(result, "bacefd"); 377 } 378 379 @Test forGraph_depthFirstPreOrder_infinite()380 public void forGraph_depthFirstPreOrder_infinite() { 381 Iterable<Integer> result = 382 Traverser.forGraph(fixedSuccessors(Iterables.cycle(1, 2, 3))).depthFirstPreOrder(0); 383 assertThat(Iterables.limit(result, 3)).containsExactly(0, 1, 2).inOrder(); 384 } 385 386 @Test forGraph_depthFirstPreOrder_diamond()387 public void forGraph_depthFirstPreOrder_diamond() { 388 Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); 389 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abdc"); 390 assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bd"); 391 assertEqualCharNodes(traverser.depthFirstPreOrder('c'), "cd"); 392 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "d"); 393 } 394 395 @Test forGraph_depthFirstPreOrderIterable_diamond()396 public void forGraph_depthFirstPreOrderIterable_diamond() { 397 Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); 398 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("")), ""); 399 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bc")), "bdc"); 400 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abdc"); 401 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("acdb")), "abdc"); 402 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("db")), "db"); 403 } 404 405 @Test forGraph_depthFirstPreOrder_multigraph()406 public void forGraph_depthFirstPreOrder_multigraph() { 407 Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); 408 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abdc"); 409 assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bd"); 410 assertEqualCharNodes(traverser.depthFirstPreOrder('c'), "cabd"); 411 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "d"); 412 } 413 414 @Test forGraph_depthFirstPreOrderIterable_multigraph()415 public void forGraph_depthFirstPreOrderIterable_multigraph() { 416 Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); 417 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("ac")), "abdc"); 418 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("cb")), "cabd"); 419 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("db")), "db"); 420 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("d")), "d"); 421 } 422 423 @Test forGraph_depthFirstPreOrder_cycle()424 public void forGraph_depthFirstPreOrder_cycle() { 425 Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); 426 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abcd"); 427 assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bcda"); 428 assertEqualCharNodes(traverser.depthFirstPreOrder('c'), "cdab"); 429 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "dabc"); 430 } 431 432 @Test forGraph_depthFirstPreOrderIterable_cycle()433 public void forGraph_depthFirstPreOrderIterable_cycle() { 434 Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); 435 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abcd"); 436 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bd")), "bcda"); 437 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("dc")), "dabc"); 438 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bc")), "bcda"); 439 } 440 441 @Test forGraph_depthFirstPreOrder_twoCycles()442 public void forGraph_depthFirstPreOrder_twoCycles() { 443 Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); 444 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abcd"); 445 assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bcda"); 446 assertEqualCharNodes(traverser.depthFirstPreOrder('c'), "cdab"); 447 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "dabc"); 448 } 449 450 @Test forGraph_depthFirstPreOrderIterable_twoCycles()451 public void forGraph_depthFirstPreOrderIterable_twoCycles() { 452 Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); 453 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abcd"); 454 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bd")), "bcda"); 455 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("dc")), "dabc"); 456 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bc")), "bcda"); 457 } 458 459 @Test forGraph_depthFirstPreOrder_tree()460 public void forGraph_depthFirstPreOrder_tree() throws Exception { 461 Traverser<Character> traverser = Traverser.forGraph(TREE); 462 463 assertEqualCharNodes(traverser.depthFirstPreOrder('h'), "hdabcegf"); 464 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "dabc"); 465 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "a"); 466 } 467 468 @Test forGraph_depthFirstPreOrderIterable_tree()469 public void forGraph_depthFirstPreOrderIterable_tree() throws Exception { 470 Traverser<Character> traverser = Traverser.forGraph(TREE); 471 472 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("hg")), "hdabcegf"); 473 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("gd")), "gfdabc"); 474 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bdgh")), "bdacgfhe"); 475 } 476 477 @Test forGraph_depthFirstPreOrder_twoTrees()478 public void forGraph_depthFirstPreOrder_twoTrees() { 479 Iterable<Character> result = Traverser.forGraph(TWO_TREES).depthFirstPreOrder('a'); 480 481 assertEqualCharNodes(result, "ab"); 482 } 483 484 @Test forGraph_depthFirstPreOrderIterable_twoTrees()485 public void forGraph_depthFirstPreOrderIterable_twoTrees() { 486 assertEqualCharNodes(Traverser.forGraph(TWO_TREES).depthFirstPreOrder(charactersOf("a")), "ab"); 487 assertEqualCharNodes( 488 Traverser.forGraph(TWO_TREES).depthFirstPreOrder(charactersOf("ac")), "abcd"); 489 } 490 491 @Test forGraph_depthFirstPreOrder_singleRoot()492 public void forGraph_depthFirstPreOrder_singleRoot() { 493 Iterable<Character> result = Traverser.forGraph(SINGLE_ROOT).depthFirstPreOrder('a'); 494 495 assertEqualCharNodes(result, "a"); 496 } 497 498 @Test forGraph_depthFirstPreOrderIterable_singleRoot()499 public void forGraph_depthFirstPreOrderIterable_singleRoot() { 500 Iterable<Character> result = 501 Traverser.forGraph(SINGLE_ROOT).depthFirstPreOrder(charactersOf("a")); 502 503 assertEqualCharNodes(result, "a"); 504 } 505 506 @Test forGraph_depthFirstPreOrder_emptyGraph()507 public void forGraph_depthFirstPreOrder_emptyGraph() { 508 assertThrows( 509 IllegalArgumentException.class, 510 () -> Traverser.forGraph(createDirectedGraph()).depthFirstPreOrder('a')); 511 } 512 513 @Test forGraph_depthFirstPreOrderIterable_emptyGraph()514 public void forGraph_depthFirstPreOrderIterable_emptyGraph() { 515 assertEqualCharNodes( 516 Traverser.forGraph(createDirectedGraph()).depthFirstPreOrder(charactersOf("")), ""); 517 assertThrows( 518 IllegalArgumentException.class, 519 () -> Traverser.forGraph(createDirectedGraph()).depthFirstPreOrder(charactersOf("a"))); 520 } 521 522 @Test forGraph_depthFirstPreOrder_iterableIsLazy()523 public void forGraph_depthFirstPreOrder_iterableIsLazy() { 524 RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); 525 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPreOrder('a'); 526 527 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 528 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b'); 529 530 // Iterate again to see if calculation is done again 531 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 532 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b'); 533 } 534 535 @Test forGraph_depthFirstPreOrderIterable_iterableIsLazy()536 public void forGraph_depthFirstPreOrderIterable_iterableIsLazy() { 537 RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); 538 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPreOrder(charactersOf("ac")); 539 540 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 541 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'c'); 542 543 // Iterate again to see if calculation is done again 544 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 545 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b', 'c'); 546 } 547 548 @Test forGraph_depthFirstPostOrder_javadocExample_canBeIteratedMultipleTimes()549 public void forGraph_depthFirstPostOrder_javadocExample_canBeIteratedMultipleTimes() { 550 Iterable<Character> result = Traverser.forGraph(JAVADOC_GRAPH).depthFirstPostOrder('a'); 551 assertEqualCharNodes(result, "fcebda"); 552 assertEqualCharNodes(result, "fcebda"); 553 } 554 555 @Test forGraph_depthFirstPostOrderIterable_javadocExample_canBeIteratedMultipleTimes()556 public void forGraph_depthFirstPostOrderIterable_javadocExample_canBeIteratedMultipleTimes() { 557 Iterable<Character> result = 558 Traverser.forGraph(JAVADOC_GRAPH).depthFirstPostOrder(charactersOf("bf")); 559 assertEqualCharNodes(result, "efcdab"); 560 assertEqualCharNodes(result, "efcdab"); 561 } 562 563 @Test forGraph_depthFirstPostOrder_diamond()564 public void forGraph_depthFirstPostOrder_diamond() { 565 Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); 566 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "dbca"); 567 assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "db"); 568 assertEqualCharNodes(traverser.depthFirstPostOrder('c'), "dc"); 569 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "d"); 570 } 571 572 @Test forGraph_depthFirstPostOrderIterable_diamond()573 public void forGraph_depthFirstPostOrderIterable_diamond() { 574 Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); 575 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("")), ""); 576 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bc")), "dbc"); 577 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "dbca"); 578 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("acdb")), "dbca"); 579 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("db")), "db"); 580 } 581 582 @Test forGraph_depthFirstPostOrder_multigraph()583 public void forGraph_depthFirstPostOrder_multigraph() { 584 Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); 585 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "dbca"); 586 assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "db"); 587 assertEqualCharNodes(traverser.depthFirstPostOrder('c'), "dbac"); 588 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "d"); 589 } 590 591 @Test forGraph_depthFirstPostOrderIterable_multigraph()592 public void forGraph_depthFirstPostOrderIterable_multigraph() { 593 Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); 594 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("ac")), "dbca"); 595 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("cb")), "dbac"); 596 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("db")), "db"); 597 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("d")), "d"); 598 } 599 600 @Test forGraph_depthFirstPostOrder_cycle()601 public void forGraph_depthFirstPostOrder_cycle() { 602 Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); 603 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "dcba"); 604 assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "adcb"); 605 assertEqualCharNodes(traverser.depthFirstPostOrder('c'), "badc"); 606 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "cbad"); 607 } 608 609 @Test forGraph_depthFirstPostOrderIterable_cycle()610 public void forGraph_depthFirstPostOrderIterable_cycle() { 611 Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); 612 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "dcba"); 613 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bd")), "adcb"); 614 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("dc")), "cbad"); 615 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bc")), "adcb"); 616 } 617 618 @Test forGraph_depthFirstPostOrder_twoCycles()619 public void forGraph_depthFirstPostOrder_twoCycles() { 620 Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); 621 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "dcba"); 622 assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "adcb"); 623 assertEqualCharNodes(traverser.depthFirstPostOrder('c'), "badc"); 624 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "cbad"); 625 } 626 627 @Test forGraph_depthFirstPostOrderIterable_twoCycles()628 public void forGraph_depthFirstPostOrderIterable_twoCycles() { 629 Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); 630 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "dcba"); 631 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bd")), "adcb"); 632 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("dc")), "cbad"); 633 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bc")), "adcb"); 634 } 635 636 @Test forGraph_depthFirstPostOrder_tree()637 public void forGraph_depthFirstPostOrder_tree() throws Exception { 638 Traverser<Character> traverser = Traverser.forGraph(TREE); 639 640 assertEqualCharNodes(traverser.depthFirstPostOrder('h'), "abcdefgh"); 641 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "abcd"); 642 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "a"); 643 } 644 645 @Test forGraph_depthFirstPostOrderIterable_tree()646 public void forGraph_depthFirstPostOrderIterable_tree() throws Exception { 647 Traverser<Character> traverser = Traverser.forGraph(TREE); 648 649 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("hg")), "abcdefgh"); 650 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("gd")), "fgabcd"); 651 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bdgh")), "bacdfgeh"); 652 } 653 654 @Test forGraph_depthFirstPostOrder_twoTrees()655 public void forGraph_depthFirstPostOrder_twoTrees() { 656 Iterable<Character> result = Traverser.forGraph(TWO_TREES).depthFirstPostOrder('a'); 657 658 assertEqualCharNodes(result, "ba"); 659 } 660 661 @Test forGraph_depthFirstPostOrderIterable_twoTrees()662 public void forGraph_depthFirstPostOrderIterable_twoTrees() { 663 assertEqualCharNodes( 664 Traverser.forGraph(TWO_TREES).depthFirstPostOrder(charactersOf("a")), "ba"); 665 assertEqualCharNodes( 666 Traverser.forGraph(TWO_TREES).depthFirstPostOrder(charactersOf("ac")), "badc"); 667 } 668 669 @Test forGraph_depthFirstPostOrder_singleRoot()670 public void forGraph_depthFirstPostOrder_singleRoot() { 671 Iterable<Character> result = Traverser.forGraph(SINGLE_ROOT).depthFirstPostOrder('a'); 672 673 assertEqualCharNodes(result, "a"); 674 } 675 676 @Test forGraph_depthFirstPostOrderIterable_singleRoot()677 public void forGraph_depthFirstPostOrderIterable_singleRoot() { 678 Iterable<Character> result = 679 Traverser.forGraph(SINGLE_ROOT).depthFirstPostOrder(charactersOf("a")); 680 681 assertEqualCharNodes(result, "a"); 682 } 683 684 @Test forGraph_depthFirstPostOrder_emptyGraph()685 public void forGraph_depthFirstPostOrder_emptyGraph() { 686 assertThrows( 687 IllegalArgumentException.class, 688 () -> Traverser.forGraph(createDirectedGraph()).depthFirstPostOrder('a')); 689 } 690 691 @Test forGraph_depthFirstPostOrderIterable_emptyGraph()692 public void forGraph_depthFirstPostOrderIterable_emptyGraph() { 693 assertEqualCharNodes( 694 Traverser.forGraph(createDirectedGraph()).depthFirstPostOrder(charactersOf("")), ""); 695 assertThrows( 696 IllegalArgumentException.class, 697 () -> Traverser.forGraph(createDirectedGraph()).depthFirstPostOrder(charactersOf("a"))); 698 } 699 700 @Test forGraph_depthFirstPostOrder_iterableIsLazy()701 public void forGraph_depthFirstPostOrder_iterableIsLazy() { 702 RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); 703 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPostOrder('a'); 704 705 assertEqualCharNodes(Iterables.limit(result, 2), "db"); 706 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'd'); 707 708 // Iterate again to see if calculation is done again 709 assertEqualCharNodes(Iterables.limit(result, 2), "db"); 710 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b', 'd', 'd'); 711 } 712 713 @Test forGraph_depthFirstPostOrderIterable_iterableIsLazy()714 public void forGraph_depthFirstPostOrderIterable_iterableIsLazy() { 715 RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); 716 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPostOrder(charactersOf("ac")); 717 718 assertEqualCharNodes(Iterables.limit(result, 2), "db"); 719 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'c', 'd'); 720 721 // Iterate again to see if calculation is done again 722 assertEqualCharNodes(Iterables.limit(result, 2), "db"); 723 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b', 'c', 'd', 'd'); 724 } 725 726 @Test 727 @SuppressWarnings("CheckReturnValue") forTree_acceptsDirectedGraph()728 public void forTree_acceptsDirectedGraph() throws Exception { 729 MutableGraph<String> graph = GraphBuilder.directed().build(); 730 graph.putEdge("a", "b"); 731 732 Traverser.forTree(graph); // Does not throw 733 } 734 735 @Test forTree_withUndirectedGraph_throws()736 public void forTree_withUndirectedGraph_throws() throws Exception { 737 MutableGraph<String> graph = GraphBuilder.undirected().build(); 738 graph.putEdge("a", "b"); 739 740 assertThrows(IllegalArgumentException.class, () -> Traverser.forTree(graph)); 741 } 742 743 @Test 744 @SuppressWarnings("CheckReturnValue") forTree_acceptsDirectedValueGraph()745 public void forTree_acceptsDirectedValueGraph() throws Exception { 746 MutableValueGraph<String, Integer> valueGraph = ValueGraphBuilder.directed().build(); 747 valueGraph.putEdgeValue("a", "b", 11); 748 749 Traverser.forTree(valueGraph); // Does not throw 750 } 751 752 @Test forTree_withUndirectedValueGraph_throws()753 public void forTree_withUndirectedValueGraph_throws() throws Exception { 754 MutableValueGraph<String, Integer> valueGraph = ValueGraphBuilder.undirected().build(); 755 valueGraph.putEdgeValue("a", "b", 11); 756 757 assertThrows(IllegalArgumentException.class, () -> Traverser.forTree(valueGraph)); 758 } 759 760 @Test 761 @SuppressWarnings("CheckReturnValue") forTree_acceptsDirectedNetwork()762 public void forTree_acceptsDirectedNetwork() throws Exception { 763 MutableNetwork<String, Integer> network = NetworkBuilder.directed().build(); 764 network.addEdge("a", "b", 11); 765 766 Traverser.forTree(network); // Does not throw 767 } 768 769 @Test forTree_withUndirectedNetwork_throws()770 public void forTree_withUndirectedNetwork_throws() throws Exception { 771 MutableNetwork<String, Integer> network = NetworkBuilder.undirected().build(); 772 network.addEdge("a", "b", 11); 773 774 assertThrows(IllegalArgumentException.class, () -> Traverser.forTree(network)); 775 } 776 777 @Test forTree_breadthFirst_infinite()778 public void forTree_breadthFirst_infinite() { 779 Iterable<Integer> result = 780 Traverser.forTree(fixedSuccessors(Iterables.cycle(1, 2, 3))).breadthFirst(0); 781 assertThat(Iterables.limit(result, 8)).containsExactly(0, 1, 2, 3, 1, 2, 3, 1).inOrder(); 782 } 783 784 @Test forTree_breadthFirst_tree()785 public void forTree_breadthFirst_tree() throws Exception { 786 Traverser<Character> traverser = Traverser.forTree(TREE); 787 788 assertEqualCharNodes(traverser.breadthFirst('h'), "hdegabcf"); 789 assertEqualCharNodes(traverser.breadthFirst('d'), "dabc"); 790 assertEqualCharNodes(traverser.breadthFirst('a'), "a"); 791 } 792 793 @Test forTree_breadthFirstIterable_tree()794 public void forTree_breadthFirstIterable_tree() throws Exception { 795 Traverser<Character> traverser = Traverser.forTree(TREE); 796 797 assertEqualCharNodes(traverser.breadthFirst(charactersOf("")), ""); 798 assertEqualCharNodes(traverser.breadthFirst(charactersOf("h")), "hdegabcf"); 799 assertEqualCharNodes(traverser.breadthFirst(charactersOf("gd")), "gdfabc"); 800 assertEqualCharNodes(traverser.breadthFirst(charactersOf("age")), "agef"); 801 } 802 803 @Test forTree_breadthFirst_cyclicGraphContainingTree()804 public void forTree_breadthFirst_cyclicGraphContainingTree() throws Exception { 805 Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); 806 807 assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); 808 assertEqualCharNodes(traverser.breadthFirst('b'), "bcd"); 809 assertEqualCharNodes(traverser.breadthFirst('d'), "d"); 810 } 811 812 @Test forTree_breadthFirstIterable_cyclicGraphContainingTree()813 public void forTree_breadthFirstIterable_cyclicGraphContainingTree() throws Exception { 814 Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); 815 816 assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd"); 817 assertEqualCharNodes(traverser.breadthFirst(charactersOf("b")), "bcd"); 818 assertEqualCharNodes(traverser.breadthFirst(charactersOf("cd")), "cd"); 819 } 820 821 @Test forTree_breadthFirst_graphContainingTreeAndDiamond()822 public void forTree_breadthFirst_graphContainingTreeAndDiamond() throws Exception { 823 Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); 824 825 assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); 826 assertEqualCharNodes(traverser.breadthFirst('b'), "bcd"); 827 assertEqualCharNodes(traverser.breadthFirst('d'), "d"); 828 } 829 830 @Test forTree_breadthFirstIterable_graphContainingTreeAndDiamond()831 public void forTree_breadthFirstIterable_graphContainingTreeAndDiamond() throws Exception { 832 Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); 833 834 assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd"); 835 assertEqualCharNodes(traverser.breadthFirst(charactersOf("bg")), "bgcdh"); 836 assertEqualCharNodes(traverser.breadthFirst(charactersOf("ga")), "gahbcd"); 837 } 838 839 @Test forTree_breadthFirst_twoTrees()840 public void forTree_breadthFirst_twoTrees() { 841 Iterable<Character> result = Traverser.forTree(TWO_TREES).breadthFirst('a'); 842 843 assertEqualCharNodes(result, "ab"); 844 } 845 846 @Test forTree_breadthFirstIterable_twoTrees()847 public void forTree_breadthFirstIterable_twoTrees() { 848 assertEqualCharNodes(Traverser.forTree(TWO_TREES).breadthFirst(charactersOf("a")), "ab"); 849 assertEqualCharNodes(Traverser.forTree(TWO_TREES).breadthFirst(charactersOf("ca")), "cadb"); 850 } 851 852 @Test forTree_breadthFirst_singleRoot()853 public void forTree_breadthFirst_singleRoot() { 854 Iterable<Character> result = Traverser.forTree(SINGLE_ROOT).breadthFirst('a'); 855 856 assertEqualCharNodes(result, "a"); 857 } 858 859 @Test forTree_breadthFirstIterable_singleRoot()860 public void forTree_breadthFirstIterable_singleRoot() { 861 Iterable<Character> result = Traverser.forTree(SINGLE_ROOT).breadthFirst(charactersOf("a")); 862 863 assertEqualCharNodes(result, "a"); 864 } 865 866 @Test forTree_breadthFirst_emptyGraph()867 public void forTree_breadthFirst_emptyGraph() { 868 assertThrows( 869 IllegalArgumentException.class, 870 () -> Traverser.forTree(createDirectedGraph()).breadthFirst('a')); 871 } 872 873 @Test forTree_breadthFirstIterable_emptyGraph()874 public void forTree_breadthFirstIterable_emptyGraph() { 875 assertEqualCharNodes( 876 Traverser.forTree(createDirectedGraph()).breadthFirst(charactersOf("")), ""); 877 assertThrows( 878 IllegalArgumentException.class, 879 () -> Traverser.forTree(createDirectedGraph()).breadthFirst(charactersOf("a"))); 880 } 881 882 @Test forTree_breadthFirst_iterableIsLazy()883 public void forTree_breadthFirst_iterableIsLazy() { 884 RequestSavingGraph graph = new RequestSavingGraph(TREE); 885 Iterable<Character> result = Traverser.forGraph(graph).breadthFirst('h'); 886 887 assertEqualCharNodes(Iterables.limit(result, 2), "hd"); 888 assertThat(graph.requestedNodes).containsExactly('h', 'h', 'd'); 889 890 // Iterate again to see if calculation is done again 891 assertEqualCharNodes(Iterables.limit(result, 2), "hd"); 892 assertThat(graph.requestedNodes).containsExactly('h', 'h', 'h', 'd', 'd'); 893 } 894 895 @Test forTree_breadthFirstIterable_iterableIsLazy()896 public void forTree_breadthFirstIterable_iterableIsLazy() { 897 RequestSavingGraph graph = new RequestSavingGraph(TREE); 898 Iterable<Character> result = Traverser.forGraph(graph).breadthFirst(charactersOf("dg")); 899 900 assertEqualCharNodes(Iterables.limit(result, 3), "dga"); 901 assertThat(graph.requestedNodes).containsExactly('a', 'd', 'd', 'g', 'g'); 902 903 // Iterate again to see if calculation is done again 904 assertEqualCharNodes(Iterables.limit(result, 3), "dga"); 905 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'd', 'd', 'd', 'g', 'g', 'g'); 906 } 907 908 @Test forTree_depthFirstPreOrder_infinite()909 public void forTree_depthFirstPreOrder_infinite() { 910 Iterable<Integer> result = 911 Traverser.forTree(fixedSuccessors(Iterables.cycle(1, 2, 3))).depthFirstPreOrder(0); 912 assertThat(Iterables.limit(result, 3)).containsExactly(0, 1, 1).inOrder(); 913 } 914 915 @Test forTree_depthFirstPreOrderIterable_tree()916 public void forTree_depthFirstPreOrderIterable_tree() throws Exception { 917 Traverser<Character> traverser = Traverser.forTree(TREE); 918 919 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("h")), "hdabcegf"); 920 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("d")), "dabc"); 921 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "a"); 922 } 923 924 @Test forTree_depthFirstPreOrderIterableIterable_tree()925 public void forTree_depthFirstPreOrderIterableIterable_tree() throws Exception { 926 Traverser<Character> traverser = Traverser.forTree(TREE); 927 928 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("")), ""); 929 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("h")), "hdabcegf"); 930 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("gd")), "gfdabc"); 931 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("age")), "agfe"); 932 } 933 934 @Test forTree_depthFirstPreOrder_cyclicGraphContainingTree()935 public void forTree_depthFirstPreOrder_cyclicGraphContainingTree() throws Exception { 936 Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); 937 938 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abcd"); 939 assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bcd"); 940 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "d"); 941 } 942 943 @Test forTree_depthFirstPreOrderIterable_cyclicGraphContainingTree()944 public void forTree_depthFirstPreOrderIterable_cyclicGraphContainingTree() throws Exception { 945 Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); 946 947 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abcd"); 948 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("b")), "bcd"); 949 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("cd")), "cd"); 950 } 951 952 @Test forTree_depthFirstPreOrder_graphContainingTreeAndDiamond()953 public void forTree_depthFirstPreOrder_graphContainingTreeAndDiamond() throws Exception { 954 Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); 955 956 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abcd"); 957 assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bcd"); 958 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "d"); 959 } 960 961 @Test forTree_depthFirstPreOrderIterable_graphContainingTreeAndDiamond()962 public void forTree_depthFirstPreOrderIterable_graphContainingTreeAndDiamond() throws Exception { 963 Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); 964 965 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abcd"); 966 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bg")), "bcdgh"); 967 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("ga")), "ghabcd"); 968 } 969 970 @Test forTree_depthFirstPreOrder_twoTrees()971 public void forTree_depthFirstPreOrder_twoTrees() { 972 Iterable<Character> result = Traverser.forTree(TWO_TREES).depthFirstPreOrder('a'); 973 974 assertEqualCharNodes(result, "ab"); 975 } 976 977 @Test forTree_depthFirstPreOrderIterable_twoTrees()978 public void forTree_depthFirstPreOrderIterable_twoTrees() { 979 assertEqualCharNodes(Traverser.forTree(TWO_TREES).depthFirstPreOrder(charactersOf("a")), "ab"); 980 assertEqualCharNodes( 981 Traverser.forTree(TWO_TREES).depthFirstPreOrder(charactersOf("ca")), "cdab"); 982 } 983 984 @Test forTree_depthFirstPreOrder_singleRoot()985 public void forTree_depthFirstPreOrder_singleRoot() { 986 Iterable<Character> result = Traverser.forTree(SINGLE_ROOT).depthFirstPreOrder('a'); 987 988 assertEqualCharNodes(result, "a"); 989 } 990 991 @Test forTree_depthFirstPreOrderIterable_singleRoot()992 public void forTree_depthFirstPreOrderIterable_singleRoot() { 993 Iterable<Character> result = 994 Traverser.forTree(SINGLE_ROOT).depthFirstPreOrder(charactersOf("a")); 995 996 assertEqualCharNodes(result, "a"); 997 } 998 999 @Test forTree_depthFirstPreOrder_emptyGraph()1000 public void forTree_depthFirstPreOrder_emptyGraph() { 1001 assertThrows( 1002 IllegalArgumentException.class, 1003 () -> Traverser.forTree(createDirectedGraph()).depthFirstPreOrder('a')); 1004 } 1005 1006 @Test forTree_depthFirstPreOrderIterable_emptyGraph()1007 public void forTree_depthFirstPreOrderIterable_emptyGraph() { 1008 assertEqualCharNodes( 1009 Traverser.forTree(createDirectedGraph()).depthFirstPreOrder(charactersOf("")), ""); 1010 assertThrows( 1011 IllegalArgumentException.class, 1012 () -> Traverser.forTree(createDirectedGraph()).depthFirstPreOrder(charactersOf("a"))); 1013 } 1014 1015 @Test forTree_depthFirstPreOrder_iterableIsLazy()1016 public void forTree_depthFirstPreOrder_iterableIsLazy() { 1017 RequestSavingGraph graph = new RequestSavingGraph(TREE); 1018 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPreOrder('h'); 1019 1020 assertEqualCharNodes(Iterables.limit(result, 2), "hd"); 1021 assertThat(graph.requestedNodes).containsExactly('h', 'h', 'd'); 1022 1023 // Iterate again to see if calculation is done again 1024 assertEqualCharNodes(Iterables.limit(result, 2), "hd"); 1025 assertThat(graph.requestedNodes).containsExactly('h', 'h', 'h', 'd', 'd'); 1026 } 1027 1028 @Test forTree_depthFirstPreOrderIterable_iterableIsLazy()1029 public void forTree_depthFirstPreOrderIterable_iterableIsLazy() { 1030 RequestSavingGraph graph = new RequestSavingGraph(TREE); 1031 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPreOrder(charactersOf("dg")); 1032 1033 assertEqualCharNodes(Iterables.limit(result, 2), "da"); 1034 assertThat(graph.requestedNodes).containsExactly('a', 'd', 'd', 'g'); 1035 1036 // Iterate again to see if calculation is done again 1037 assertEqualCharNodes(Iterables.limit(result, 2), "da"); 1038 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'd', 'd', 'd', 'g'); 1039 } 1040 1041 @Test forTree_depthFirstPostOrder_tree()1042 public void forTree_depthFirstPostOrder_tree() throws Exception { 1043 Traverser<Character> traverser = Traverser.forTree(TREE); 1044 1045 assertEqualCharNodes(traverser.depthFirstPostOrder('h'), "abcdefgh"); 1046 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "abcd"); 1047 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "a"); 1048 } 1049 1050 @Test forTree_depthFirstPostOrderIterable_tree()1051 public void forTree_depthFirstPostOrderIterable_tree() throws Exception { 1052 Traverser<Character> traverser = Traverser.forTree(TREE); 1053 1054 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("")), ""); 1055 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("h")), "abcdefgh"); 1056 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("gd")), "fgabcd"); 1057 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("age")), "afge"); 1058 } 1059 1060 @Test forTree_depthFirstPostOrder_cyclicGraphContainingTree()1061 public void forTree_depthFirstPostOrder_cyclicGraphContainingTree() throws Exception { 1062 Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); 1063 1064 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "cdba"); 1065 assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "cdb"); 1066 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "d"); 1067 } 1068 1069 @Test forTree_depthFirstPostOrderIterable_cyclicGraphContainingTree()1070 public void forTree_depthFirstPostOrderIterable_cyclicGraphContainingTree() throws Exception { 1071 Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); 1072 1073 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "cdba"); 1074 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("b")), "cdb"); 1075 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("cd")), "cd"); 1076 } 1077 1078 @Test forTree_depthFirstPostOrder_graphContainingTreeAndDiamond()1079 public void forTree_depthFirstPostOrder_graphContainingTreeAndDiamond() throws Exception { 1080 Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); 1081 1082 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "cdba"); 1083 assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "cdb"); 1084 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "d"); 1085 } 1086 1087 @Test forTree_depthFirstPostOrderIterable_graphContainingTreeAndDiamond()1088 public void forTree_depthFirstPostOrderIterable_graphContainingTreeAndDiamond() throws Exception { 1089 Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); 1090 1091 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "cdba"); 1092 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bg")), "cdbhg"); 1093 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("ga")), "hgcdba"); 1094 } 1095 1096 @Test forTree_depthFirstPostOrder_twoTrees()1097 public void forTree_depthFirstPostOrder_twoTrees() { 1098 Iterable<Character> result = Traverser.forTree(TWO_TREES).depthFirstPostOrder('a'); 1099 1100 assertEqualCharNodes(result, "ba"); 1101 } 1102 1103 @Test forTree_depthFirstPostOrderIterable_twoTrees()1104 public void forTree_depthFirstPostOrderIterable_twoTrees() { 1105 assertEqualCharNodes(Traverser.forTree(TWO_TREES).depthFirstPostOrder(charactersOf("a")), "ba"); 1106 assertEqualCharNodes( 1107 Traverser.forTree(TWO_TREES).depthFirstPostOrder(charactersOf("ca")), "dcba"); 1108 } 1109 1110 @Test forTree_depthFirstPostOrder_singleRoot()1111 public void forTree_depthFirstPostOrder_singleRoot() { 1112 Iterable<Character> result = Traverser.forTree(SINGLE_ROOT).depthFirstPostOrder('a'); 1113 1114 assertEqualCharNodes(result, "a"); 1115 } 1116 1117 @Test forTree_depthFirstPostOrderIterable_singleRoot()1118 public void forTree_depthFirstPostOrderIterable_singleRoot() { 1119 Iterable<Character> result = 1120 Traverser.forTree(SINGLE_ROOT).depthFirstPostOrder(charactersOf("a")); 1121 1122 assertEqualCharNodes(result, "a"); 1123 } 1124 1125 @Test forTree_depthFirstPostOrder_emptyGraph()1126 public void forTree_depthFirstPostOrder_emptyGraph() { 1127 assertThrows( 1128 IllegalArgumentException.class, 1129 () -> Traverser.forTree(createDirectedGraph()).depthFirstPostOrder('a')); 1130 } 1131 1132 @Test forTree_depthFirstPostOrderIterable_emptyGraph()1133 public void forTree_depthFirstPostOrderIterable_emptyGraph() { 1134 assertEqualCharNodes( 1135 Traverser.forTree(createDirectedGraph()).depthFirstPostOrder(charactersOf("")), ""); 1136 assertThrows( 1137 IllegalArgumentException.class, 1138 () -> Traverser.forTree(createDirectedGraph()).depthFirstPostOrder(charactersOf("a"))); 1139 } 1140 1141 @Test forTree_depthFirstPostOrder_iterableIsLazy()1142 public void forTree_depthFirstPostOrder_iterableIsLazy() { 1143 RequestSavingGraph graph = new RequestSavingGraph(TREE); 1144 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPostOrder('h'); 1145 1146 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 1147 assertThat(graph.requestedNodes).containsExactly('h', 'h', 'd', 'a', 'b'); 1148 1149 // Iterate again to see if calculation is done again 1150 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 1151 assertThat(graph.requestedNodes).containsExactly('h', 'h', 'h', 'd', 'd', 'a', 'a', 'b', 'b'); 1152 } 1153 1154 @Test forTree_depthFirstPostOrderIterable_iterableIsLazy()1155 public void forTree_depthFirstPostOrderIterable_iterableIsLazy() { 1156 RequestSavingGraph graph = new RequestSavingGraph(TREE); 1157 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPostOrder(charactersOf("dg")); 1158 1159 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 1160 assertThat(graph.requestedNodes).containsExactly('a', 'b', 'd', 'd', 'g'); 1161 1162 // Iterate again to see if calculation is done again 1163 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 1164 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'b', 'd', 'd', 'd', 'g'); 1165 } 1166 createDirectedGraph(String... edges)1167 private static SuccessorsFunction<Character> createDirectedGraph(String... edges) { 1168 return createGraph(/* directed= */ true, edges); 1169 } 1170 createUndirectedGraph(String... edges)1171 private static SuccessorsFunction<Character> createUndirectedGraph(String... edges) { 1172 return createGraph(/* directed= */ false, edges); 1173 } 1174 1175 /** 1176 * Creates a graph from a list of node pairs (encoded as strings, e.g. "ab" means that this graph 1177 * has an edge between 'a' and 'b'). 1178 * 1179 * <p>The {@code successors} are always returned in alphabetical order. 1180 */ createGraph(boolean directed, String... edges)1181 private static SuccessorsFunction<Character> createGraph(boolean directed, String... edges) { 1182 ImmutableMultimap.Builder<Character, Character> graphMapBuilder = ImmutableMultimap.builder(); 1183 for (String edge : edges) { 1184 checkArgument( 1185 edge.length() == 2, "Expecting each edge to consist of 2 characters but got %s", edge); 1186 char node1 = edge.charAt(0); 1187 char node2 = edge.charAt(1); 1188 graphMapBuilder.put(node1, node2); 1189 if (!directed) { 1190 graphMapBuilder.put(node2, node1); 1191 } 1192 } 1193 final ImmutableMultimap<Character, Character> graphMap = graphMapBuilder.build(); 1194 1195 return new SuccessorsFunction<Character>() { 1196 @Override 1197 public Iterable<? extends Character> successors(Character node) { 1198 checkArgument( 1199 graphMap.containsKey(node) || graphMap.containsValue(node), 1200 "Node %s is not an element of this graph", 1201 node); 1202 return Ordering.natural().immutableSortedCopy(graphMap.get(node)); 1203 } 1204 }; 1205 } 1206 1207 private static ImmutableGraph<Character> createSingleRootGraph() { 1208 MutableGraph<Character> graph = GraphBuilder.directed().build(); 1209 graph.addNode('a'); 1210 return ImmutableGraph.copyOf(graph); 1211 } 1212 1213 private static void assertEqualCharNodes(Iterable<Character> result, String expectedCharacters) { 1214 assertThat(ImmutableList.copyOf(result)) 1215 .containsExactlyElementsIn(Chars.asList(expectedCharacters.toCharArray())) 1216 .inOrder(); 1217 } 1218 1219 private static class RequestSavingGraph implements SuccessorsFunction<Character> { 1220 private final SuccessorsFunction<Character> delegate; 1221 final Multiset<Character> requestedNodes = HashMultiset.create(); 1222 1223 RequestSavingGraph(SuccessorsFunction<Character> delegate) { 1224 this.delegate = checkNotNull(delegate); 1225 } 1226 1227 @Override 1228 public Iterable<? extends Character> successors(Character node) { 1229 requestedNodes.add(node); 1230 return delegate.successors(node); 1231 } 1232 } 1233 1234 private static <N> SuccessorsFunction<N> fixedSuccessors(final Iterable<N> successors) { 1235 return new SuccessorsFunction<N>() { 1236 @Override 1237 public Iterable<N> successors(N n) { 1238 return successors; 1239 } 1240 }; 1241 } 1242 } 1243