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.fail; 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 try { 315 Traverser.forGraph(createDirectedGraph()).breadthFirst('a'); 316 fail("Expected IllegalArgumentException"); 317 } catch (IllegalArgumentException expected) { 318 } 319 } 320 321 /** 322 * Checks that the elements of the iterable are calculated on the fly. Concretely, that means that 323 * {@link SuccessorsFunction#successors(Object)} can only be called for a subset of all nodes. 324 */ 325 @Test forGraph_breadthFirstIterable_emptyGraph()326 public void forGraph_breadthFirstIterable_emptyGraph() { 327 assertEqualCharNodes( 328 Traverser.forGraph(createDirectedGraph()).breadthFirst(charactersOf("")), ""); 329 try { 330 Traverser.forGraph(createDirectedGraph()).breadthFirst(charactersOf("a")); 331 fail("Expected IllegalArgumentException"); 332 } catch (IllegalArgumentException expected) { 333 } 334 } 335 336 /** 337 * Checks that the elements of the iterable are calculated on the fly. Concretely, that means that 338 * {@link SuccessorsFunction#successors(Object)} can only be called for a subset of all nodes. 339 */ 340 @Test forGraph_breadthFirst_iterableIsLazy()341 public void forGraph_breadthFirst_iterableIsLazy() { 342 RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); 343 Iterable<Character> result = Traverser.forGraph(graph).breadthFirst('a'); 344 345 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 346 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b'); 347 348 // Iterate again to see if calculation is done again 349 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 350 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b'); 351 } 352 353 @Test forGraph_breadthFirstIterable_iterableIsLazy()354 public void forGraph_breadthFirstIterable_iterableIsLazy() { 355 RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); 356 Iterable<Character> result = Traverser.forGraph(graph).breadthFirst(charactersOf("ab")); 357 358 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 359 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'b'); 360 361 // Iterate again to see if calculation is done again 362 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 363 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b', 'b'); 364 } 365 366 @Test forGraph_depthFirstPreOrder_javadocExample_canBeIteratedMultipleTimes()367 public void forGraph_depthFirstPreOrder_javadocExample_canBeIteratedMultipleTimes() { 368 Iterable<Character> result = Traverser.forGraph(JAVADOC_GRAPH).depthFirstPreOrder('a'); 369 370 assertEqualCharNodes(result, "abecfd"); 371 assertEqualCharNodes(result, "abecfd"); 372 } 373 374 @Test forGraph_depthFirstPreOrderIterable_javadocExample_canBeIteratedMultipleTimes()375 public void forGraph_depthFirstPreOrderIterable_javadocExample_canBeIteratedMultipleTimes() { 376 Iterable<Character> result = 377 Traverser.forGraph(JAVADOC_GRAPH).depthFirstPreOrder(charactersOf("bc")); 378 379 assertEqualCharNodes(result, "bacefd"); 380 assertEqualCharNodes(result, "bacefd"); 381 } 382 383 @Test forGraph_depthFirstPreOrder_infinite()384 public void forGraph_depthFirstPreOrder_infinite() { 385 Iterable<Integer> result = 386 Traverser.forGraph(fixedSuccessors(Iterables.cycle(1, 2, 3))).depthFirstPreOrder(0); 387 assertThat(Iterables.limit(result, 3)).containsExactly(0, 1, 2).inOrder(); 388 } 389 390 @Test forGraph_depthFirstPreOrder_diamond()391 public void forGraph_depthFirstPreOrder_diamond() { 392 Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); 393 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abdc"); 394 assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bd"); 395 assertEqualCharNodes(traverser.depthFirstPreOrder('c'), "cd"); 396 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "d"); 397 } 398 399 @Test forGraph_depthFirstPreOrderIterable_diamond()400 public void forGraph_depthFirstPreOrderIterable_diamond() { 401 Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); 402 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("")), ""); 403 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bc")), "bdc"); 404 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abdc"); 405 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("acdb")), "abdc"); 406 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("db")), "db"); 407 } 408 409 @Test forGraph_depthFirstPreOrder_multigraph()410 public void forGraph_depthFirstPreOrder_multigraph() { 411 Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); 412 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abdc"); 413 assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bd"); 414 assertEqualCharNodes(traverser.depthFirstPreOrder('c'), "cabd"); 415 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "d"); 416 } 417 418 @Test forGraph_depthFirstPreOrderIterable_multigraph()419 public void forGraph_depthFirstPreOrderIterable_multigraph() { 420 Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); 421 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("ac")), "abdc"); 422 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("cb")), "cabd"); 423 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("db")), "db"); 424 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("d")), "d"); 425 } 426 427 @Test forGraph_depthFirstPreOrder_cycle()428 public void forGraph_depthFirstPreOrder_cycle() { 429 Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); 430 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abcd"); 431 assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bcda"); 432 assertEqualCharNodes(traverser.depthFirstPreOrder('c'), "cdab"); 433 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "dabc"); 434 } 435 436 @Test forGraph_depthFirstPreOrderIterable_cycle()437 public void forGraph_depthFirstPreOrderIterable_cycle() { 438 Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); 439 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abcd"); 440 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bd")), "bcda"); 441 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("dc")), "dabc"); 442 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bc")), "bcda"); 443 } 444 445 @Test forGraph_depthFirstPreOrder_twoCycles()446 public void forGraph_depthFirstPreOrder_twoCycles() { 447 Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); 448 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abcd"); 449 assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bcda"); 450 assertEqualCharNodes(traverser.depthFirstPreOrder('c'), "cdab"); 451 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "dabc"); 452 } 453 454 @Test forGraph_depthFirstPreOrderIterable_twoCycles()455 public void forGraph_depthFirstPreOrderIterable_twoCycles() { 456 Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); 457 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abcd"); 458 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bd")), "bcda"); 459 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("dc")), "dabc"); 460 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bc")), "bcda"); 461 } 462 463 @Test forGraph_depthFirstPreOrder_tree()464 public void forGraph_depthFirstPreOrder_tree() throws Exception { 465 Traverser<Character> traverser = Traverser.forGraph(TREE); 466 467 assertEqualCharNodes(traverser.depthFirstPreOrder('h'), "hdabcegf"); 468 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "dabc"); 469 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "a"); 470 } 471 472 @Test forGraph_depthFirstPreOrderIterable_tree()473 public void forGraph_depthFirstPreOrderIterable_tree() throws Exception { 474 Traverser<Character> traverser = Traverser.forGraph(TREE); 475 476 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("hg")), "hdabcegf"); 477 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("gd")), "gfdabc"); 478 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bdgh")), "bdacgfhe"); 479 } 480 481 @Test forGraph_depthFirstPreOrder_twoTrees()482 public void forGraph_depthFirstPreOrder_twoTrees() { 483 Iterable<Character> result = Traverser.forGraph(TWO_TREES).depthFirstPreOrder('a'); 484 485 assertEqualCharNodes(result, "ab"); 486 } 487 488 @Test forGraph_depthFirstPreOrderIterable_twoTrees()489 public void forGraph_depthFirstPreOrderIterable_twoTrees() { 490 assertEqualCharNodes(Traverser.forGraph(TWO_TREES).depthFirstPreOrder(charactersOf("a")), "ab"); 491 assertEqualCharNodes( 492 Traverser.forGraph(TWO_TREES).depthFirstPreOrder(charactersOf("ac")), "abcd"); 493 } 494 495 @Test forGraph_depthFirstPreOrder_singleRoot()496 public void forGraph_depthFirstPreOrder_singleRoot() { 497 Iterable<Character> result = Traverser.forGraph(SINGLE_ROOT).depthFirstPreOrder('a'); 498 499 assertEqualCharNodes(result, "a"); 500 } 501 502 @Test forGraph_depthFirstPreOrderIterable_singleRoot()503 public void forGraph_depthFirstPreOrderIterable_singleRoot() { 504 Iterable<Character> result = 505 Traverser.forGraph(SINGLE_ROOT).depthFirstPreOrder(charactersOf("a")); 506 507 assertEqualCharNodes(result, "a"); 508 } 509 510 @Test forGraph_depthFirstPreOrder_emptyGraph()511 public void forGraph_depthFirstPreOrder_emptyGraph() { 512 try { 513 Traverser.forGraph(createDirectedGraph()).depthFirstPreOrder('a'); 514 fail("Expected IllegalArgumentException"); 515 } catch (IllegalArgumentException expected) { 516 } 517 } 518 519 @Test forGraph_depthFirstPreOrderIterable_emptyGraph()520 public void forGraph_depthFirstPreOrderIterable_emptyGraph() { 521 assertEqualCharNodes( 522 Traverser.forGraph(createDirectedGraph()).depthFirstPreOrder(charactersOf("")), ""); 523 try { 524 Traverser.forGraph(createDirectedGraph()).depthFirstPreOrder(charactersOf("a")); 525 fail("Expected IllegalArgumentException"); 526 } catch (IllegalArgumentException expected) { 527 } 528 } 529 530 @Test forGraph_depthFirstPreOrder_iterableIsLazy()531 public void forGraph_depthFirstPreOrder_iterableIsLazy() { 532 RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); 533 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPreOrder('a'); 534 535 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 536 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b'); 537 538 // Iterate again to see if calculation is done again 539 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 540 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b'); 541 } 542 543 @Test forGraph_depthFirstPreOrderIterable_iterableIsLazy()544 public void forGraph_depthFirstPreOrderIterable_iterableIsLazy() { 545 RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); 546 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPreOrder(charactersOf("ac")); 547 548 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 549 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'c'); 550 551 // Iterate again to see if calculation is done again 552 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 553 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b', 'c'); 554 } 555 556 @Test forGraph_depthFirstPostOrder_javadocExample_canBeIteratedMultipleTimes()557 public void forGraph_depthFirstPostOrder_javadocExample_canBeIteratedMultipleTimes() { 558 Iterable<Character> result = Traverser.forGraph(JAVADOC_GRAPH).depthFirstPostOrder('a'); 559 assertEqualCharNodes(result, "fcebda"); 560 assertEqualCharNodes(result, "fcebda"); 561 } 562 563 @Test forGraph_depthFirstPostOrderIterable_javadocExample_canBeIteratedMultipleTimes()564 public void forGraph_depthFirstPostOrderIterable_javadocExample_canBeIteratedMultipleTimes() { 565 Iterable<Character> result = 566 Traverser.forGraph(JAVADOC_GRAPH).depthFirstPostOrder(charactersOf("bf")); 567 assertEqualCharNodes(result, "efcdab"); 568 assertEqualCharNodes(result, "efcdab"); 569 } 570 571 @Test forGraph_depthFirstPostOrder_diamond()572 public void forGraph_depthFirstPostOrder_diamond() { 573 Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); 574 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "dbca"); 575 assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "db"); 576 assertEqualCharNodes(traverser.depthFirstPostOrder('c'), "dc"); 577 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "d"); 578 } 579 580 @Test forGraph_depthFirstPostOrderIterable_diamond()581 public void forGraph_depthFirstPostOrderIterable_diamond() { 582 Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); 583 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("")), ""); 584 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bc")), "dbc"); 585 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "dbca"); 586 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("acdb")), "dbca"); 587 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("db")), "db"); 588 } 589 590 @Test forGraph_depthFirstPostOrder_multigraph()591 public void forGraph_depthFirstPostOrder_multigraph() { 592 Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); 593 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "dbca"); 594 assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "db"); 595 assertEqualCharNodes(traverser.depthFirstPostOrder('c'), "dbac"); 596 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "d"); 597 } 598 599 @Test forGraph_depthFirstPostOrderIterable_multigraph()600 public void forGraph_depthFirstPostOrderIterable_multigraph() { 601 Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); 602 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("ac")), "dbca"); 603 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("cb")), "dbac"); 604 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("db")), "db"); 605 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("d")), "d"); 606 } 607 608 @Test forGraph_depthFirstPostOrder_cycle()609 public void forGraph_depthFirstPostOrder_cycle() { 610 Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); 611 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "dcba"); 612 assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "adcb"); 613 assertEqualCharNodes(traverser.depthFirstPostOrder('c'), "badc"); 614 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "cbad"); 615 } 616 617 @Test forGraph_depthFirstPostOrderIterable_cycle()618 public void forGraph_depthFirstPostOrderIterable_cycle() { 619 Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); 620 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "dcba"); 621 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bd")), "adcb"); 622 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("dc")), "cbad"); 623 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bc")), "adcb"); 624 } 625 626 @Test forGraph_depthFirstPostOrder_twoCycles()627 public void forGraph_depthFirstPostOrder_twoCycles() { 628 Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); 629 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "dcba"); 630 assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "adcb"); 631 assertEqualCharNodes(traverser.depthFirstPostOrder('c'), "badc"); 632 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "cbad"); 633 } 634 635 @Test forGraph_depthFirstPostOrderIterable_twoCycles()636 public void forGraph_depthFirstPostOrderIterable_twoCycles() { 637 Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); 638 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "dcba"); 639 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bd")), "adcb"); 640 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("dc")), "cbad"); 641 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bc")), "adcb"); 642 } 643 644 @Test forGraph_depthFirstPostOrder_tree()645 public void forGraph_depthFirstPostOrder_tree() throws Exception { 646 Traverser<Character> traverser = Traverser.forGraph(TREE); 647 648 assertEqualCharNodes(traverser.depthFirstPostOrder('h'), "abcdefgh"); 649 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "abcd"); 650 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "a"); 651 } 652 653 @Test forGraph_depthFirstPostOrderIterable_tree()654 public void forGraph_depthFirstPostOrderIterable_tree() throws Exception { 655 Traverser<Character> traverser = Traverser.forGraph(TREE); 656 657 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("hg")), "abcdefgh"); 658 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("gd")), "fgabcd"); 659 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bdgh")), "bacdfgeh"); 660 } 661 662 @Test forGraph_depthFirstPostOrder_twoTrees()663 public void forGraph_depthFirstPostOrder_twoTrees() { 664 Iterable<Character> result = Traverser.forGraph(TWO_TREES).depthFirstPostOrder('a'); 665 666 assertEqualCharNodes(result, "ba"); 667 } 668 669 @Test forGraph_depthFirstPostOrderIterable_twoTrees()670 public void forGraph_depthFirstPostOrderIterable_twoTrees() { 671 assertEqualCharNodes( 672 Traverser.forGraph(TWO_TREES).depthFirstPostOrder(charactersOf("a")), "ba"); 673 assertEqualCharNodes( 674 Traverser.forGraph(TWO_TREES).depthFirstPostOrder(charactersOf("ac")), "badc"); 675 } 676 677 @Test forGraph_depthFirstPostOrder_singleRoot()678 public void forGraph_depthFirstPostOrder_singleRoot() { 679 Iterable<Character> result = Traverser.forGraph(SINGLE_ROOT).depthFirstPostOrder('a'); 680 681 assertEqualCharNodes(result, "a"); 682 } 683 684 @Test forGraph_depthFirstPostOrderIterable_singleRoot()685 public void forGraph_depthFirstPostOrderIterable_singleRoot() { 686 Iterable<Character> result = 687 Traverser.forGraph(SINGLE_ROOT).depthFirstPostOrder(charactersOf("a")); 688 689 assertEqualCharNodes(result, "a"); 690 } 691 692 @Test forGraph_depthFirstPostOrder_emptyGraph()693 public void forGraph_depthFirstPostOrder_emptyGraph() { 694 try { 695 Traverser.forGraph(createDirectedGraph()).depthFirstPostOrder('a'); 696 fail("Expected IllegalArgumentException"); 697 } catch (IllegalArgumentException expected) { 698 } 699 } 700 701 @Test forGraph_depthFirstPostOrderIterable_emptyGraph()702 public void forGraph_depthFirstPostOrderIterable_emptyGraph() { 703 assertEqualCharNodes( 704 Traverser.forGraph(createDirectedGraph()).depthFirstPostOrder(charactersOf("")), ""); 705 try { 706 Traverser.forGraph(createDirectedGraph()).depthFirstPostOrder(charactersOf("a")); 707 fail("Expected IllegalArgumentException"); 708 } catch (IllegalArgumentException expected) { 709 } 710 } 711 712 @Test forGraph_depthFirstPostOrder_iterableIsLazy()713 public void forGraph_depthFirstPostOrder_iterableIsLazy() { 714 RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); 715 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPostOrder('a'); 716 717 assertEqualCharNodes(Iterables.limit(result, 2), "db"); 718 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'd'); 719 720 // Iterate again to see if calculation is done again 721 assertEqualCharNodes(Iterables.limit(result, 2), "db"); 722 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b', 'd', 'd'); 723 } 724 725 @Test forGraph_depthFirstPostOrderIterable_iterableIsLazy()726 public void forGraph_depthFirstPostOrderIterable_iterableIsLazy() { 727 RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); 728 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPostOrder(charactersOf("ac")); 729 730 assertEqualCharNodes(Iterables.limit(result, 2), "db"); 731 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'c', 'd'); 732 733 // Iterate again to see if calculation is done again 734 assertEqualCharNodes(Iterables.limit(result, 2), "db"); 735 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b', 'c', 'd', 'd'); 736 } 737 738 @Test 739 @SuppressWarnings("CheckReturnValue") forTree_acceptsDirectedGraph()740 public void forTree_acceptsDirectedGraph() throws Exception { 741 MutableGraph<String> graph = GraphBuilder.directed().build(); 742 graph.putEdge("a", "b"); 743 744 Traverser.forTree(graph); // Does not throw 745 } 746 747 @Test forTree_withUndirectedGraph_throws()748 public void forTree_withUndirectedGraph_throws() throws Exception { 749 MutableGraph<String> graph = GraphBuilder.undirected().build(); 750 graph.putEdge("a", "b"); 751 752 try { 753 Traverser.forTree(graph); 754 fail("Expected exception"); 755 } catch (IllegalArgumentException expected) { 756 } 757 } 758 759 @Test 760 @SuppressWarnings("CheckReturnValue") forTree_acceptsDirectedValueGraph()761 public void forTree_acceptsDirectedValueGraph() throws Exception { 762 MutableValueGraph<String, Integer> valueGraph = ValueGraphBuilder.directed().build(); 763 valueGraph.putEdgeValue("a", "b", 11); 764 765 Traverser.forTree(valueGraph); // Does not throw 766 } 767 768 @Test forTree_withUndirectedValueGraph_throws()769 public void forTree_withUndirectedValueGraph_throws() throws Exception { 770 MutableValueGraph<String, Integer> valueGraph = ValueGraphBuilder.undirected().build(); 771 valueGraph.putEdgeValue("a", "b", 11); 772 773 try { 774 Traverser.forTree(valueGraph); 775 fail("Expected exception"); 776 } catch (IllegalArgumentException expected) { 777 } 778 } 779 780 @Test 781 @SuppressWarnings("CheckReturnValue") forTree_acceptsDirectedNetwork()782 public void forTree_acceptsDirectedNetwork() throws Exception { 783 MutableNetwork<String, Integer> network = NetworkBuilder.directed().build(); 784 network.addEdge("a", "b", 11); 785 786 Traverser.forTree(network); // Does not throw 787 } 788 789 @Test forTree_withUndirectedNetwork_throws()790 public void forTree_withUndirectedNetwork_throws() throws Exception { 791 MutableNetwork<String, Integer> network = NetworkBuilder.undirected().build(); 792 network.addEdge("a", "b", 11); 793 794 try { 795 Traverser.forTree(network); 796 fail("Expected exception"); 797 } catch (IllegalArgumentException expected) { 798 } 799 } 800 801 @Test forTree_breadthFirst_infinite()802 public void forTree_breadthFirst_infinite() { 803 Iterable<Integer> result = 804 Traverser.forTree(fixedSuccessors(Iterables.cycle(1, 2, 3))).breadthFirst(0); 805 assertThat(Iterables.limit(result, 8)).containsExactly(0, 1, 2, 3, 1, 2, 3, 1).inOrder(); 806 } 807 808 @Test forTree_breadthFirst_tree()809 public void forTree_breadthFirst_tree() throws Exception { 810 Traverser<Character> traverser = Traverser.forTree(TREE); 811 812 assertEqualCharNodes(traverser.breadthFirst('h'), "hdegabcf"); 813 assertEqualCharNodes(traverser.breadthFirst('d'), "dabc"); 814 assertEqualCharNodes(traverser.breadthFirst('a'), "a"); 815 } 816 817 @Test forTree_breadthFirstIterable_tree()818 public void forTree_breadthFirstIterable_tree() throws Exception { 819 Traverser<Character> traverser = Traverser.forTree(TREE); 820 821 assertEqualCharNodes(traverser.breadthFirst(charactersOf("")), ""); 822 assertEqualCharNodes(traverser.breadthFirst(charactersOf("h")), "hdegabcf"); 823 assertEqualCharNodes(traverser.breadthFirst(charactersOf("gd")), "gdfabc"); 824 assertEqualCharNodes(traverser.breadthFirst(charactersOf("age")), "agef"); 825 } 826 827 @Test forTree_breadthFirst_cyclicGraphContainingTree()828 public void forTree_breadthFirst_cyclicGraphContainingTree() throws Exception { 829 Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); 830 831 assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); 832 assertEqualCharNodes(traverser.breadthFirst('b'), "bcd"); 833 assertEqualCharNodes(traverser.breadthFirst('d'), "d"); 834 } 835 836 @Test forTree_breadthFirstIterable_cyclicGraphContainingTree()837 public void forTree_breadthFirstIterable_cyclicGraphContainingTree() throws Exception { 838 Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); 839 840 assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd"); 841 assertEqualCharNodes(traverser.breadthFirst(charactersOf("b")), "bcd"); 842 assertEqualCharNodes(traverser.breadthFirst(charactersOf("cd")), "cd"); 843 } 844 845 @Test forTree_breadthFirst_graphContainingTreeAndDiamond()846 public void forTree_breadthFirst_graphContainingTreeAndDiamond() throws Exception { 847 Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); 848 849 assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); 850 assertEqualCharNodes(traverser.breadthFirst('b'), "bcd"); 851 assertEqualCharNodes(traverser.breadthFirst('d'), "d"); 852 } 853 854 @Test forTree_breadthFirstIterable_graphContainingTreeAndDiamond()855 public void forTree_breadthFirstIterable_graphContainingTreeAndDiamond() throws Exception { 856 Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); 857 858 assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd"); 859 assertEqualCharNodes(traverser.breadthFirst(charactersOf("bg")), "bgcdh"); 860 assertEqualCharNodes(traverser.breadthFirst(charactersOf("ga")), "gahbcd"); 861 } 862 863 @Test forTree_breadthFirst_twoTrees()864 public void forTree_breadthFirst_twoTrees() { 865 Iterable<Character> result = Traverser.forTree(TWO_TREES).breadthFirst('a'); 866 867 assertEqualCharNodes(result, "ab"); 868 } 869 870 @Test forTree_breadthFirstIterable_twoTrees()871 public void forTree_breadthFirstIterable_twoTrees() { 872 assertEqualCharNodes(Traverser.forTree(TWO_TREES).breadthFirst(charactersOf("a")), "ab"); 873 assertEqualCharNodes(Traverser.forTree(TWO_TREES).breadthFirst(charactersOf("ca")), "cadb"); 874 } 875 876 @Test forTree_breadthFirst_singleRoot()877 public void forTree_breadthFirst_singleRoot() { 878 Iterable<Character> result = Traverser.forTree(SINGLE_ROOT).breadthFirst('a'); 879 880 assertEqualCharNodes(result, "a"); 881 } 882 883 @Test forTree_breadthFirstIterable_singleRoot()884 public void forTree_breadthFirstIterable_singleRoot() { 885 Iterable<Character> result = Traverser.forTree(SINGLE_ROOT).breadthFirst(charactersOf("a")); 886 887 assertEqualCharNodes(result, "a"); 888 } 889 890 @Test forTree_breadthFirst_emptyGraph()891 public void forTree_breadthFirst_emptyGraph() { 892 try { 893 Traverser.forTree(createDirectedGraph()).breadthFirst('a'); 894 fail("Expected IllegalArgumentException"); 895 } catch (IllegalArgumentException expected) { 896 } 897 } 898 899 @Test forTree_breadthFirstIterable_emptyGraph()900 public void forTree_breadthFirstIterable_emptyGraph() { 901 assertEqualCharNodes( 902 Traverser.forTree(createDirectedGraph()).breadthFirst(charactersOf("")), ""); 903 try { 904 Traverser.forTree(createDirectedGraph()).breadthFirst(charactersOf("a")); 905 fail("Expected IllegalArgumentException"); 906 } catch (IllegalArgumentException expected) { 907 } 908 } 909 910 @Test forTree_breadthFirst_iterableIsLazy()911 public void forTree_breadthFirst_iterableIsLazy() { 912 RequestSavingGraph graph = new RequestSavingGraph(TREE); 913 Iterable<Character> result = Traverser.forGraph(graph).breadthFirst('h'); 914 915 assertEqualCharNodes(Iterables.limit(result, 2), "hd"); 916 assertThat(graph.requestedNodes).containsExactly('h', 'h', 'd'); 917 918 // Iterate again to see if calculation is done again 919 assertEqualCharNodes(Iterables.limit(result, 2), "hd"); 920 assertThat(graph.requestedNodes).containsExactly('h', 'h', 'h', 'd', 'd'); 921 } 922 923 @Test forTree_breadthFirstIterable_iterableIsLazy()924 public void forTree_breadthFirstIterable_iterableIsLazy() { 925 RequestSavingGraph graph = new RequestSavingGraph(TREE); 926 Iterable<Character> result = Traverser.forGraph(graph).breadthFirst(charactersOf("dg")); 927 928 assertEqualCharNodes(Iterables.limit(result, 3), "dga"); 929 assertThat(graph.requestedNodes).containsExactly('a', 'd', 'd', 'g', 'g'); 930 931 // Iterate again to see if calculation is done again 932 assertEqualCharNodes(Iterables.limit(result, 3), "dga"); 933 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'd', 'd', 'd', 'g', 'g', 'g'); 934 } 935 936 @Test forTree_depthFirstPreOrder_infinite()937 public void forTree_depthFirstPreOrder_infinite() { 938 Iterable<Integer> result = 939 Traverser.forTree(fixedSuccessors(Iterables.cycle(1, 2, 3))).depthFirstPreOrder(0); 940 assertThat(Iterables.limit(result, 3)).containsExactly(0, 1, 1).inOrder(); 941 } 942 943 @Test forTree_depthFirstPreOrderIterable_tree()944 public void forTree_depthFirstPreOrderIterable_tree() throws Exception { 945 Traverser<Character> traverser = Traverser.forTree(TREE); 946 947 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("h")), "hdabcegf"); 948 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("d")), "dabc"); 949 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "a"); 950 } 951 952 @Test forTree_depthFirstPreOrderIterableIterable_tree()953 public void forTree_depthFirstPreOrderIterableIterable_tree() throws Exception { 954 Traverser<Character> traverser = Traverser.forTree(TREE); 955 956 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("")), ""); 957 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("h")), "hdabcegf"); 958 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("gd")), "gfdabc"); 959 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("age")), "agfe"); 960 } 961 962 @Test forTree_depthFirstPreOrder_cyclicGraphContainingTree()963 public void forTree_depthFirstPreOrder_cyclicGraphContainingTree() throws Exception { 964 Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); 965 966 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abcd"); 967 assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bcd"); 968 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "d"); 969 } 970 971 @Test forTree_depthFirstPreOrderIterable_cyclicGraphContainingTree()972 public void forTree_depthFirstPreOrderIterable_cyclicGraphContainingTree() throws Exception { 973 Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); 974 975 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abcd"); 976 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("b")), "bcd"); 977 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("cd")), "cd"); 978 } 979 980 @Test forTree_depthFirstPreOrder_graphContainingTreeAndDiamond()981 public void forTree_depthFirstPreOrder_graphContainingTreeAndDiamond() throws Exception { 982 Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); 983 984 assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abcd"); 985 assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bcd"); 986 assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "d"); 987 } 988 989 @Test forTree_depthFirstPreOrderIterable_graphContainingTreeAndDiamond()990 public void forTree_depthFirstPreOrderIterable_graphContainingTreeAndDiamond() throws Exception { 991 Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); 992 993 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abcd"); 994 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bg")), "bcdgh"); 995 assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("ga")), "ghabcd"); 996 } 997 998 @Test forTree_depthFirstPreOrder_twoTrees()999 public void forTree_depthFirstPreOrder_twoTrees() { 1000 Iterable<Character> result = Traverser.forTree(TWO_TREES).depthFirstPreOrder('a'); 1001 1002 assertEqualCharNodes(result, "ab"); 1003 } 1004 1005 @Test forTree_depthFirstPreOrderIterable_twoTrees()1006 public void forTree_depthFirstPreOrderIterable_twoTrees() { 1007 assertEqualCharNodes(Traverser.forTree(TWO_TREES).depthFirstPreOrder(charactersOf("a")), "ab"); 1008 assertEqualCharNodes( 1009 Traverser.forTree(TWO_TREES).depthFirstPreOrder(charactersOf("ca")), "cdab"); 1010 } 1011 1012 @Test forTree_depthFirstPreOrder_singleRoot()1013 public void forTree_depthFirstPreOrder_singleRoot() { 1014 Iterable<Character> result = Traverser.forTree(SINGLE_ROOT).depthFirstPreOrder('a'); 1015 1016 assertEqualCharNodes(result, "a"); 1017 } 1018 1019 @Test forTree_depthFirstPreOrderIterable_singleRoot()1020 public void forTree_depthFirstPreOrderIterable_singleRoot() { 1021 Iterable<Character> result = 1022 Traverser.forTree(SINGLE_ROOT).depthFirstPreOrder(charactersOf("a")); 1023 1024 assertEqualCharNodes(result, "a"); 1025 } 1026 1027 @Test forTree_depthFirstPreOrder_emptyGraph()1028 public void forTree_depthFirstPreOrder_emptyGraph() { 1029 try { 1030 Traverser.forTree(createDirectedGraph()).depthFirstPreOrder('a'); 1031 fail("Expected IllegalArgumentException"); 1032 } catch (IllegalArgumentException expected) { 1033 } 1034 } 1035 1036 @Test forTree_depthFirstPreOrderIterable_emptyGraph()1037 public void forTree_depthFirstPreOrderIterable_emptyGraph() { 1038 assertEqualCharNodes( 1039 Traverser.forTree(createDirectedGraph()).depthFirstPreOrder(charactersOf("")), ""); 1040 try { 1041 Traverser.forTree(createDirectedGraph()).depthFirstPreOrder(charactersOf("a")); 1042 fail("Expected IllegalArgumentException"); 1043 } catch (IllegalArgumentException expected) { 1044 } 1045 } 1046 1047 @Test forTree_depthFirstPreOrder_iterableIsLazy()1048 public void forTree_depthFirstPreOrder_iterableIsLazy() { 1049 RequestSavingGraph graph = new RequestSavingGraph(TREE); 1050 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPreOrder('h'); 1051 1052 assertEqualCharNodes(Iterables.limit(result, 2), "hd"); 1053 assertThat(graph.requestedNodes).containsExactly('h', 'h', 'd'); 1054 1055 // Iterate again to see if calculation is done again 1056 assertEqualCharNodes(Iterables.limit(result, 2), "hd"); 1057 assertThat(graph.requestedNodes).containsExactly('h', 'h', 'h', 'd', 'd'); 1058 } 1059 1060 @Test forTree_depthFirstPreOrderIterable_iterableIsLazy()1061 public void forTree_depthFirstPreOrderIterable_iterableIsLazy() { 1062 RequestSavingGraph graph = new RequestSavingGraph(TREE); 1063 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPreOrder(charactersOf("dg")); 1064 1065 assertEqualCharNodes(Iterables.limit(result, 2), "da"); 1066 assertThat(graph.requestedNodes).containsExactly('a', 'd', 'd', 'g'); 1067 1068 // Iterate again to see if calculation is done again 1069 assertEqualCharNodes(Iterables.limit(result, 2), "da"); 1070 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'd', 'd', 'd', 'g'); 1071 } 1072 1073 @Test forTree_depthFirstPostOrder_tree()1074 public void forTree_depthFirstPostOrder_tree() throws Exception { 1075 Traverser<Character> traverser = Traverser.forTree(TREE); 1076 1077 assertEqualCharNodes(traverser.depthFirstPostOrder('h'), "abcdefgh"); 1078 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "abcd"); 1079 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "a"); 1080 } 1081 1082 @Test forTree_depthFirstPostOrderIterable_tree()1083 public void forTree_depthFirstPostOrderIterable_tree() throws Exception { 1084 Traverser<Character> traverser = Traverser.forTree(TREE); 1085 1086 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("")), ""); 1087 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("h")), "abcdefgh"); 1088 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("gd")), "fgabcd"); 1089 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("age")), "afge"); 1090 } 1091 1092 @Test forTree_depthFirstPostOrder_cyclicGraphContainingTree()1093 public void forTree_depthFirstPostOrder_cyclicGraphContainingTree() throws Exception { 1094 Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); 1095 1096 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "cdba"); 1097 assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "cdb"); 1098 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "d"); 1099 } 1100 1101 @Test forTree_depthFirstPostOrderIterable_cyclicGraphContainingTree()1102 public void forTree_depthFirstPostOrderIterable_cyclicGraphContainingTree() throws Exception { 1103 Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); 1104 1105 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "cdba"); 1106 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("b")), "cdb"); 1107 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("cd")), "cd"); 1108 } 1109 1110 @Test forTree_depthFirstPostOrder_graphContainingTreeAndDiamond()1111 public void forTree_depthFirstPostOrder_graphContainingTreeAndDiamond() throws Exception { 1112 Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); 1113 1114 assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "cdba"); 1115 assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "cdb"); 1116 assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "d"); 1117 } 1118 1119 @Test forTree_depthFirstPostOrderIterable_graphContainingTreeAndDiamond()1120 public void forTree_depthFirstPostOrderIterable_graphContainingTreeAndDiamond() throws Exception { 1121 Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); 1122 1123 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "cdba"); 1124 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bg")), "cdbhg"); 1125 assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("ga")), "hgcdba"); 1126 } 1127 1128 @Test forTree_depthFirstPostOrder_twoTrees()1129 public void forTree_depthFirstPostOrder_twoTrees() { 1130 Iterable<Character> result = Traverser.forTree(TWO_TREES).depthFirstPostOrder('a'); 1131 1132 assertEqualCharNodes(result, "ba"); 1133 } 1134 1135 @Test forTree_depthFirstPostOrderIterable_twoTrees()1136 public void forTree_depthFirstPostOrderIterable_twoTrees() { 1137 assertEqualCharNodes(Traverser.forTree(TWO_TREES).depthFirstPostOrder(charactersOf("a")), "ba"); 1138 assertEqualCharNodes( 1139 Traverser.forTree(TWO_TREES).depthFirstPostOrder(charactersOf("ca")), "dcba"); 1140 } 1141 1142 @Test forTree_depthFirstPostOrder_singleRoot()1143 public void forTree_depthFirstPostOrder_singleRoot() { 1144 Iterable<Character> result = Traverser.forTree(SINGLE_ROOT).depthFirstPostOrder('a'); 1145 1146 assertEqualCharNodes(result, "a"); 1147 } 1148 1149 @Test forTree_depthFirstPostOrderIterable_singleRoot()1150 public void forTree_depthFirstPostOrderIterable_singleRoot() { 1151 Iterable<Character> result = 1152 Traverser.forTree(SINGLE_ROOT).depthFirstPostOrder(charactersOf("a")); 1153 1154 assertEqualCharNodes(result, "a"); 1155 } 1156 1157 @Test forTree_depthFirstPostOrder_emptyGraph()1158 public void forTree_depthFirstPostOrder_emptyGraph() { 1159 try { 1160 Traverser.forTree(createDirectedGraph()).depthFirstPostOrder('a'); 1161 fail("Expected IllegalArgumentException"); 1162 } catch (IllegalArgumentException expected) { 1163 } 1164 } 1165 1166 @Test forTree_depthFirstPostOrderIterable_emptyGraph()1167 public void forTree_depthFirstPostOrderIterable_emptyGraph() { 1168 assertEqualCharNodes( 1169 Traverser.forTree(createDirectedGraph()).depthFirstPostOrder(charactersOf("")), ""); 1170 try { 1171 Traverser.forTree(createDirectedGraph()).depthFirstPostOrder(charactersOf("a")); 1172 fail("Expected IllegalArgumentException"); 1173 } catch (IllegalArgumentException expected) { 1174 } 1175 } 1176 1177 @Test forTree_depthFirstPostOrder_iterableIsLazy()1178 public void forTree_depthFirstPostOrder_iterableIsLazy() { 1179 RequestSavingGraph graph = new RequestSavingGraph(TREE); 1180 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPostOrder('h'); 1181 1182 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 1183 assertThat(graph.requestedNodes).containsExactly('h', 'h', 'd', 'a', 'b'); 1184 1185 // Iterate again to see if calculation is done again 1186 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 1187 assertThat(graph.requestedNodes).containsExactly('h', 'h', 'h', 'd', 'd', 'a', 'a', 'b', 'b'); 1188 } 1189 1190 @Test forTree_depthFirstPostOrderIterable_iterableIsLazy()1191 public void forTree_depthFirstPostOrderIterable_iterableIsLazy() { 1192 RequestSavingGraph graph = new RequestSavingGraph(TREE); 1193 Iterable<Character> result = Traverser.forGraph(graph).depthFirstPostOrder(charactersOf("dg")); 1194 1195 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 1196 assertThat(graph.requestedNodes).containsExactly('a', 'b', 'd', 'd', 'g'); 1197 1198 // Iterate again to see if calculation is done again 1199 assertEqualCharNodes(Iterables.limit(result, 2), "ab"); 1200 assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'b', 'd', 'd', 'd', 'g'); 1201 } 1202 createDirectedGraph(String... edges)1203 private static SuccessorsFunction<Character> createDirectedGraph(String... edges) { 1204 return createGraph(/* directed = */ true, edges); 1205 } 1206 createUndirectedGraph(String... edges)1207 private static SuccessorsFunction<Character> createUndirectedGraph(String... edges) { 1208 return createGraph(/* directed = */ false, edges); 1209 } 1210 1211 /** 1212 * Creates a graph from a list of node pairs (encoded as strings, e.g. "ab" means that this graph 1213 * has an edge between 'a' and 'b'). 1214 * 1215 * <p>The {@code successors} are always returned in alphabetical order. 1216 */ createGraph(boolean directed, String... edges)1217 private static SuccessorsFunction<Character> createGraph(boolean directed, String... edges) { 1218 ImmutableMultimap.Builder<Character, Character> graphMapBuilder = ImmutableMultimap.builder(); 1219 for (String edge : edges) { 1220 checkArgument( 1221 edge.length() == 2, "Expecting each edge to consist of 2 characters but got %s", edge); 1222 char node1 = edge.charAt(0); 1223 char node2 = edge.charAt(1); 1224 graphMapBuilder.put(node1, node2); 1225 if (!directed) { 1226 graphMapBuilder.put(node2, node1); 1227 } 1228 } 1229 final ImmutableMultimap<Character, Character> graphMap = graphMapBuilder.build(); 1230 1231 return new SuccessorsFunction<Character>() { 1232 @Override 1233 public Iterable<? extends Character> successors(Character node) { 1234 checkArgument( 1235 graphMap.containsKey(node) || graphMap.containsValue(node), 1236 "Node %s is not an element of this graph", 1237 node); 1238 return Ordering.natural().immutableSortedCopy(graphMap.get(node)); 1239 } 1240 }; 1241 } 1242 1243 private static ImmutableGraph<Character> createSingleRootGraph() { 1244 MutableGraph<Character> graph = GraphBuilder.directed().build(); 1245 graph.addNode('a'); 1246 return ImmutableGraph.copyOf(graph); 1247 } 1248 1249 private static void assertEqualCharNodes(Iterable<Character> result, String expectedCharacters) { 1250 assertThat(ImmutableList.copyOf(result)) 1251 .containsExactlyElementsIn(Chars.asList(expectedCharacters.toCharArray())) 1252 .inOrder(); 1253 } 1254 1255 private static class RequestSavingGraph implements SuccessorsFunction<Character> { 1256 private final SuccessorsFunction<Character> delegate; 1257 final Multiset<Character> requestedNodes = HashMultiset.create(); 1258 1259 RequestSavingGraph(SuccessorsFunction<Character> delegate) { 1260 this.delegate = checkNotNull(delegate); 1261 } 1262 1263 @Override 1264 public Iterable<? extends Character> successors(Character node) { 1265 requestedNodes.add(node); 1266 return delegate.successors(node); 1267 } 1268 } 1269 1270 private static <N> SuccessorsFunction<N> fixedSuccessors(final Iterable<N> successors) { 1271 return new SuccessorsFunction<N>() { 1272 @Override 1273 public Iterable<N> successors(N n) { 1274 return successors; 1275 } 1276 }; 1277 } 1278 } 1279