| /* |
| |
| * Copyright (C) 2017 The Guava Authors |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.google.common.graph; |
| |
| import static com.google.common.base.Preconditions.checkArgument; |
| import static com.google.common.base.Preconditions.checkNotNull; |
| import static com.google.common.collect.Lists.charactersOf; |
| import static com.google.common.truth.Truth.assertThat; |
| import static org.junit.Assert.fail; |
| |
| import com.google.common.collect.HashMultiset; |
| import com.google.common.collect.ImmutableList; |
| import com.google.common.collect.ImmutableMultimap; |
| import com.google.common.collect.Iterables; |
| import com.google.common.collect.Multiset; |
| import com.google.common.collect.Ordering; |
| import com.google.common.primitives.Chars; |
| import org.junit.Test; |
| import org.junit.runner.RunWith; |
| import org.junit.runners.JUnit4; |
| |
| @RunWith(JUnit4.class) |
| public class TraverserTest { |
| |
| /** |
| * The undirected graph in the {@link Traverser#breadthFirst(Object)} javadoc: |
| * |
| * <pre>{@code |
| * b ---- a ---- d |
| * | | |
| * | | |
| * e ---- c ---- f |
| * }</pre> |
| */ |
| private static final SuccessorsFunction<Character> JAVADOC_GRAPH = |
| createUndirectedGraph("ba", "ad", "be", "ac", "ec", "cf"); |
| |
| /** |
| * A diamond shaped directed graph (arrows going down): |
| * |
| * <pre>{@code |
| * a |
| * / \ |
| * b c |
| * \ / |
| * d |
| * }</pre> |
| */ |
| private static final SuccessorsFunction<Character> DIAMOND_GRAPH = |
| createDirectedGraph("ab", "ac", "bd", "cd"); |
| |
| /** |
| * Same as {@link #DIAMOND_GRAPH}, but with an extra c->a edge and some self edges: |
| * |
| * <pre>{@code |
| * a<> |
| * / \\ |
| * b c |
| * \ / |
| * d<> |
| * }</pre> |
| * |
| * {@code <>} indicates a self-loop |
| */ |
| private static final SuccessorsFunction<Character> MULTI_GRAPH = |
| createDirectedGraph("aa", "dd", "ab", "ac", "ca", "cd", "bd"); |
| |
| /** A directed graph with a single cycle: a -> b -> c -> d -> a. */ |
| private static final SuccessorsFunction<Character> CYCLE_GRAPH = |
| createDirectedGraph("ab", "bc", "cd", "da"); |
| |
| /** |
| * Same as {@link #CYCLE_GRAPH}, but with an extra a->c edge. |
| * |
| * <pre>{@code |
| * |--------------| |
| * v | |
| * a -> b -> c -> d |
| * | ^ |
| * |---------| |
| * }</pre> |
| */ |
| private static final SuccessorsFunction<Character> TWO_CYCLES_GRAPH = |
| createDirectedGraph("ab", "ac", "bc", "cd", "da"); |
| |
| /** |
| * A tree-shaped graph that looks as follows (all edges are directed facing downwards): |
| * |
| * <pre>{@code |
| * h |
| * /|\ |
| * / | \ |
| * / | \ |
| * d e g |
| * /|\ | |
| * / | \ | |
| * a b c f |
| * }</pre> |
| */ |
| private static final SuccessorsFunction<Character> TREE = |
| createDirectedGraph("hd", "he", "hg", "da", "db", "dc", "gf"); |
| |
| /** |
| * Two disjoint tree-shaped graphs that look as follows (all edges are directed facing downwards): |
| * |
| * <pre>{@code |
| * a c |
| * | | |
| * | | |
| * b d |
| * }</pre> |
| */ |
| private static final SuccessorsFunction<Character> TWO_TREES = createDirectedGraph("ab", "cd"); |
| |
| /** |
| * A graph consisting of a single root {@code a}: |
| * |
| * <pre>{@code |
| * a |
| * }</pre> |
| */ |
| private static final SuccessorsFunction<Character> SINGLE_ROOT = createSingleRootGraph(); |
| |
| /** |
| * A graph that is not a tree (for example, it has two antiparallel edge between {@code e} and |
| * {@code f} and thus has a cycle) but is a valid input to {@link Traverser#forTree} when starting |
| * e.g. at node {@code a} (all edges without an arrow are directed facing downwards): |
| * |
| * <pre>{@code |
| * a |
| * / |
| * b e <----> f |
| * / \ / |
| * c d |
| * }</pre> |
| */ |
| private static final SuccessorsFunction<Character> CYCLIC_GRAPH_CONTAINING_TREE = |
| createDirectedGraph("ab", "bc", "bd", "ed", "ef", "fe"); |
| |
| /** |
| * A graph that is not a tree (for example, {@code h} is reachable from {@code f} via both {@code |
| * e} and {@code g}) but is a valid input to {@link Traverser#forTree} when starting e.g. at node |
| * {@code a} (all edges are directed facing downwards): |
| * |
| * <pre>{@code |
| * a f |
| * / / \ |
| * b e g |
| * / \ / \ / |
| * c d h |
| * }</pre> |
| */ |
| private static final SuccessorsFunction<Character> GRAPH_CONTAINING_TREE_AND_DIAMOND = |
| createDirectedGraph("ab", "fe", "fg", "bc", "bd", "ed", "eh", "gh"); |
| |
| @Test |
| public void forGraph_breadthFirst_javadocExample_canBeIteratedMultipleTimes() { |
| Iterable<Character> result = Traverser.forGraph(JAVADOC_GRAPH).breadthFirst('a'); |
| |
| assertEqualCharNodes(result, "abcdef"); |
| assertEqualCharNodes(result, "abcdef"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirstIterable_javadocExample_canBeIteratedMultipleTimes() { |
| Iterable<Character> result = Traverser.forGraph(JAVADOC_GRAPH).breadthFirst(charactersOf("bf")); |
| |
| assertEqualCharNodes(result, "bfaecd"); |
| assertEqualCharNodes(result, "bfaecd"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirst_diamond() { |
| Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); |
| assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); |
| assertEqualCharNodes(traverser.breadthFirst('b'), "bd"); |
| assertEqualCharNodes(traverser.breadthFirst('c'), "cd"); |
| assertEqualCharNodes(traverser.breadthFirst('d'), "d"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirstIterable_diamond() { |
| Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("")), ""); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("bc")), "bcd"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("acdb")), "acdb"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("db")), "db"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirst_multiGraph() { |
| Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); |
| assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); |
| assertEqualCharNodes(traverser.breadthFirst('b'), "bd"); |
| assertEqualCharNodes(traverser.breadthFirst('c'), "cadb"); |
| assertEqualCharNodes(traverser.breadthFirst('d'), "d"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirstIterable_multiGraph() { |
| Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("ac")), "acbd"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("cb")), "cbad"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("db")), "db"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("d")), "d"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirst_cycle() { |
| Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); |
| assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); |
| assertEqualCharNodes(traverser.breadthFirst('b'), "bcda"); |
| assertEqualCharNodes(traverser.breadthFirst('c'), "cdab"); |
| assertEqualCharNodes(traverser.breadthFirst('d'), "dabc"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirstIterable_cycle() { |
| Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("bd")), "bdca"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("dc")), "dcab"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("bc")), "bcda"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirst_twoCycles() { |
| Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); |
| assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); |
| assertEqualCharNodes(traverser.breadthFirst('b'), "bcda"); |
| assertEqualCharNodes(traverser.breadthFirst('c'), "cdab"); |
| assertEqualCharNodes(traverser.breadthFirst('d'), "dabc"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirstIterable_twoCycles() { |
| Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("bd")), "bdca"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("dc")), "dcab"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("bc")), "bcda"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirst_tree() throws Exception { |
| Traverser<Character> traverser = Traverser.forGraph(TREE); |
| |
| assertEqualCharNodes(traverser.breadthFirst('h'), "hdegabcf"); |
| assertEqualCharNodes(traverser.breadthFirst('d'), "dabc"); |
| assertEqualCharNodes(traverser.breadthFirst('a'), "a"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirstIterable_tree() throws Exception { |
| Traverser<Character> traverser = Traverser.forGraph(TREE); |
| |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("hg")), "hgdefabc"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("gd")), "gdfabc"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("bdgh")), "bdghacfe"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirst_twoTrees() { |
| Iterable<Character> result = Traverser.forGraph(TWO_TREES).breadthFirst('a'); |
| |
| assertEqualCharNodes(result, "ab"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirstIterable_twoTrees() { |
| assertEqualCharNodes(Traverser.forGraph(TWO_TREES).breadthFirst(charactersOf("a")), "ab"); |
| assertEqualCharNodes(Traverser.forGraph(TWO_TREES).breadthFirst(charactersOf("ac")), "acbd"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirst_singleRoot() { |
| Iterable<Character> result = Traverser.forGraph(SINGLE_ROOT).breadthFirst('a'); |
| |
| assertEqualCharNodes(result, "a"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirstIterable_singleRoot() { |
| Iterable<Character> result = Traverser.forGraph(SINGLE_ROOT).breadthFirst(charactersOf("a")); |
| |
| assertEqualCharNodes(result, "a"); |
| } |
| |
| @Test |
| public void forGraph_breadthFirst_emptyGraph() { |
| try { |
| Traverser.forGraph(createDirectedGraph()).breadthFirst('a'); |
| fail("Expected IllegalArgumentException"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| /** |
| * Checks that the elements of the iterable are calculated on the fly. Concretely, that means that |
| * {@link SuccessorsFunction#successors(Object)} can only be called for a subset of all nodes. |
| */ |
| @Test |
| public void forGraph_breadthFirstIterable_emptyGraph() { |
| assertEqualCharNodes( |
| Traverser.forGraph(createDirectedGraph()).breadthFirst(charactersOf("")), ""); |
| try { |
| Traverser.forGraph(createDirectedGraph()).breadthFirst(charactersOf("a")); |
| fail("Expected IllegalArgumentException"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| /** |
| * Checks that the elements of the iterable are calculated on the fly. Concretely, that means that |
| * {@link SuccessorsFunction#successors(Object)} can only be called for a subset of all nodes. |
| */ |
| @Test |
| public void forGraph_breadthFirst_iterableIsLazy() { |
| RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); |
| Iterable<Character> result = Traverser.forGraph(graph).breadthFirst('a'); |
| |
| assertEqualCharNodes(Iterables.limit(result, 2), "ab"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b'); |
| |
| // Iterate again to see if calculation is done again |
| assertEqualCharNodes(Iterables.limit(result, 2), "ab"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b'); |
| } |
| |
| @Test |
| public void forGraph_breadthFirstIterable_iterableIsLazy() { |
| RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); |
| Iterable<Character> result = Traverser.forGraph(graph).breadthFirst(charactersOf("ab")); |
| |
| assertEqualCharNodes(Iterables.limit(result, 2), "ab"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'b'); |
| |
| // Iterate again to see if calculation is done again |
| assertEqualCharNodes(Iterables.limit(result, 2), "ab"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b', 'b'); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrder_javadocExample_canBeIteratedMultipleTimes() { |
| Iterable<Character> result = Traverser.forGraph(JAVADOC_GRAPH).depthFirstPreOrder('a'); |
| |
| assertEqualCharNodes(result, "abecfd"); |
| assertEqualCharNodes(result, "abecfd"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrderIterable_javadocExample_canBeIteratedMultipleTimes() { |
| Iterable<Character> result = |
| Traverser.forGraph(JAVADOC_GRAPH).depthFirstPreOrder(charactersOf("bc")); |
| |
| assertEqualCharNodes(result, "bacefd"); |
| assertEqualCharNodes(result, "bacefd"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrder_diamond() { |
| Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abdc"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('c'), "cd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "d"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrderIterable_diamond() { |
| Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("")), ""); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bc")), "bdc"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abdc"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("acdb")), "abdc"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("db")), "db"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrder_multigraph() { |
| Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abdc"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('c'), "cabd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "d"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrderIterable_multigraph() { |
| Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("ac")), "abdc"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("cb")), "cabd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("db")), "db"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("d")), "d"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrder_cycle() { |
| Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abcd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bcda"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('c'), "cdab"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "dabc"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrderIterable_cycle() { |
| Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abcd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bd")), "bcda"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("dc")), "dabc"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bc")), "bcda"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrder_twoCycles() { |
| Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abcd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bcda"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('c'), "cdab"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "dabc"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrderIterable_twoCycles() { |
| Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abcd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bd")), "bcda"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("dc")), "dabc"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bc")), "bcda"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrder_tree() throws Exception { |
| Traverser<Character> traverser = Traverser.forGraph(TREE); |
| |
| assertEqualCharNodes(traverser.depthFirstPreOrder('h'), "hdabcegf"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "dabc"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "a"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrderIterable_tree() throws Exception { |
| Traverser<Character> traverser = Traverser.forGraph(TREE); |
| |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("hg")), "hdabcegf"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("gd")), "gfdabc"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bdgh")), "bdacgfhe"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrder_twoTrees() { |
| Iterable<Character> result = Traverser.forGraph(TWO_TREES).depthFirstPreOrder('a'); |
| |
| assertEqualCharNodes(result, "ab"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrderIterable_twoTrees() { |
| assertEqualCharNodes(Traverser.forGraph(TWO_TREES).depthFirstPreOrder(charactersOf("a")), "ab"); |
| assertEqualCharNodes( |
| Traverser.forGraph(TWO_TREES).depthFirstPreOrder(charactersOf("ac")), "abcd"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrder_singleRoot() { |
| Iterable<Character> result = Traverser.forGraph(SINGLE_ROOT).depthFirstPreOrder('a'); |
| |
| assertEqualCharNodes(result, "a"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrderIterable_singleRoot() { |
| Iterable<Character> result = |
| Traverser.forGraph(SINGLE_ROOT).depthFirstPreOrder(charactersOf("a")); |
| |
| assertEqualCharNodes(result, "a"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrder_emptyGraph() { |
| try { |
| Traverser.forGraph(createDirectedGraph()).depthFirstPreOrder('a'); |
| fail("Expected IllegalArgumentException"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrderIterable_emptyGraph() { |
| assertEqualCharNodes( |
| Traverser.forGraph(createDirectedGraph()).depthFirstPreOrder(charactersOf("")), ""); |
| try { |
| Traverser.forGraph(createDirectedGraph()).depthFirstPreOrder(charactersOf("a")); |
| fail("Expected IllegalArgumentException"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrder_iterableIsLazy() { |
| RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); |
| Iterable<Character> result = Traverser.forGraph(graph).depthFirstPreOrder('a'); |
| |
| assertEqualCharNodes(Iterables.limit(result, 2), "ab"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'd'); |
| |
| // Iterate again to see if calculation is done again |
| assertEqualCharNodes(Iterables.limit(result, 2), "ab"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b', 'd', 'd'); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPreOrderIterable_iterableIsLazy() { |
| RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); |
| Iterable<Character> result = Traverser.forGraph(graph).depthFirstPreOrder(charactersOf("ac")); |
| |
| assertEqualCharNodes(Iterables.limit(result, 2), "ab"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'c', 'd'); |
| |
| // Iterate again to see if calculation is done again |
| assertEqualCharNodes(Iterables.limit(result, 2), "ab"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b', 'c', 'd', 'd'); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrder_javadocExample_canBeIteratedMultipleTimes() { |
| Iterable<Character> result = Traverser.forGraph(JAVADOC_GRAPH).depthFirstPostOrder('a'); |
| assertEqualCharNodes(result, "fcebda"); |
| assertEqualCharNodes(result, "fcebda"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrderIterable_javadocExample_canBeIteratedMultipleTimes() { |
| Iterable<Character> result = |
| Traverser.forGraph(JAVADOC_GRAPH).depthFirstPostOrder(charactersOf("bf")); |
| assertEqualCharNodes(result, "efcdab"); |
| assertEqualCharNodes(result, "efcdab"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrder_diamond() { |
| Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "dbca"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "db"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('c'), "dc"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "d"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrderIterable_diamond() { |
| Traverser<Character> traverser = Traverser.forGraph(DIAMOND_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("")), ""); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bc")), "dbc"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "dbca"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("acdb")), "dbca"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("db")), "db"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrder_multigraph() { |
| Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "dbca"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "db"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('c'), "dbac"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "d"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrderIterable_multigraph() { |
| Traverser<Character> traverser = Traverser.forGraph(MULTI_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("ac")), "dbca"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("cb")), "dbac"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("db")), "db"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("d")), "d"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrder_cycle() { |
| Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "dcba"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "adcb"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('c'), "badc"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "cbad"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrderIterable_cycle() { |
| Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "dcba"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bd")), "adcb"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("dc")), "cbad"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bc")), "adcb"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrder_twoCycles() { |
| Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "dcba"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "adcb"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('c'), "badc"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "cbad"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrderIterable_twoCycles() { |
| Traverser<Character> traverser = Traverser.forGraph(TWO_CYCLES_GRAPH); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "dcba"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bd")), "adcb"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("dc")), "cbad"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bc")), "adcb"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrder_tree() throws Exception { |
| Traverser<Character> traverser = Traverser.forGraph(TREE); |
| |
| assertEqualCharNodes(traverser.depthFirstPostOrder('h'), "abcdefgh"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "abcd"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "a"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrderIterable_tree() throws Exception { |
| Traverser<Character> traverser = Traverser.forGraph(TREE); |
| |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("hg")), "abcdefgh"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("gd")), "fgabcd"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bdgh")), "bacdfgeh"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrder_twoTrees() { |
| Iterable<Character> result = Traverser.forGraph(TWO_TREES).depthFirstPostOrder('a'); |
| |
| assertEqualCharNodes(result, "ba"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrderIterable_twoTrees() { |
| assertEqualCharNodes( |
| Traverser.forGraph(TWO_TREES).depthFirstPostOrder(charactersOf("a")), "ba"); |
| assertEqualCharNodes( |
| Traverser.forGraph(TWO_TREES).depthFirstPostOrder(charactersOf("ac")), "badc"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrder_singleRoot() { |
| Iterable<Character> result = Traverser.forGraph(SINGLE_ROOT).depthFirstPostOrder('a'); |
| |
| assertEqualCharNodes(result, "a"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrderIterable_singleRoot() { |
| Iterable<Character> result = |
| Traverser.forGraph(SINGLE_ROOT).depthFirstPostOrder(charactersOf("a")); |
| |
| assertEqualCharNodes(result, "a"); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrder_emptyGraph() { |
| try { |
| Traverser.forGraph(createDirectedGraph()).depthFirstPostOrder('a'); |
| fail("Expected IllegalArgumentException"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrderIterable_emptyGraph() { |
| assertEqualCharNodes( |
| Traverser.forGraph(createDirectedGraph()).depthFirstPostOrder(charactersOf("")), ""); |
| try { |
| Traverser.forGraph(createDirectedGraph()).depthFirstPostOrder(charactersOf("a")); |
| fail("Expected IllegalArgumentException"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrder_iterableIsLazy() { |
| RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); |
| Iterable<Character> result = Traverser.forGraph(graph).depthFirstPostOrder('a'); |
| |
| assertEqualCharNodes(Iterables.limit(result, 2), "db"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'd'); |
| |
| // Iterate again to see if calculation is done again |
| assertEqualCharNodes(Iterables.limit(result, 2), "db"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b', 'd', 'd'); |
| } |
| |
| @Test |
| public void forGraph_depthFirstPostOrderIterable_iterableIsLazy() { |
| RequestSavingGraph graph = new RequestSavingGraph(DIAMOND_GRAPH); |
| Iterable<Character> result = Traverser.forGraph(graph).depthFirstPostOrder(charactersOf("ac")); |
| |
| assertEqualCharNodes(Iterables.limit(result, 2), "db"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'c', 'd'); |
| |
| // Iterate again to see if calculation is done again |
| assertEqualCharNodes(Iterables.limit(result, 2), "db"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'a', 'b', 'b', 'c', 'd', 'd'); |
| } |
| |
| @Test |
| @SuppressWarnings("CheckReturnValue") |
| public void forTree_acceptsDirectedGraph() throws Exception { |
| MutableGraph<String> graph = GraphBuilder.directed().build(); |
| graph.putEdge("a", "b"); |
| |
| Traverser.forTree(graph); // Does not throw |
| } |
| |
| @Test |
| public void forTree_withUndirectedGraph_throws() throws Exception { |
| MutableGraph<String> graph = GraphBuilder.undirected().build(); |
| graph.putEdge("a", "b"); |
| |
| try { |
| Traverser.forTree(graph); |
| fail("Expected exception"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| @Test |
| @SuppressWarnings("CheckReturnValue") |
| public void forTree_acceptsDirectedValueGraph() throws Exception { |
| MutableValueGraph<String, Integer> valueGraph = ValueGraphBuilder.directed().build(); |
| valueGraph.putEdgeValue("a", "b", 11); |
| |
| Traverser.forTree(valueGraph); // Does not throw |
| } |
| |
| @Test |
| public void forTree_withUndirectedValueGraph_throws() throws Exception { |
| MutableValueGraph<String, Integer> valueGraph = ValueGraphBuilder.undirected().build(); |
| valueGraph.putEdgeValue("a", "b", 11); |
| |
| try { |
| Traverser.forTree(valueGraph); |
| fail("Expected exception"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| @Test |
| @SuppressWarnings("CheckReturnValue") |
| public void forTree_acceptsDirectedNetwork() throws Exception { |
| MutableNetwork<String, Integer> network = NetworkBuilder.directed().build(); |
| network.addEdge("a", "b", 11); |
| |
| Traverser.forTree(network); // Does not throw |
| } |
| |
| @Test |
| public void forTree_withUndirectedNetwork_throws() throws Exception { |
| MutableNetwork<String, Integer> network = NetworkBuilder.undirected().build(); |
| network.addEdge("a", "b", 11); |
| |
| try { |
| Traverser.forTree(network); |
| fail("Expected exception"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| @Test |
| public void forTree_breadthFirst_tree() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(TREE); |
| |
| assertEqualCharNodes(traverser.breadthFirst('h'), "hdegabcf"); |
| assertEqualCharNodes(traverser.breadthFirst('d'), "dabc"); |
| assertEqualCharNodes(traverser.breadthFirst('a'), "a"); |
| } |
| |
| @Test |
| public void forTree_breadthFirstIterable_tree() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(TREE); |
| |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("")), ""); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("h")), "hdegabcf"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("gd")), "gdfabc"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("age")), "agef"); |
| } |
| |
| @Test |
| public void forTree_breadthFirst_cyclicGraphContainingTree() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); |
| |
| assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); |
| assertEqualCharNodes(traverser.breadthFirst('b'), "bcd"); |
| assertEqualCharNodes(traverser.breadthFirst('d'), "d"); |
| } |
| |
| @Test |
| public void forTree_breadthFirstIterable_cyclicGraphContainingTree() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); |
| |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("b")), "bcd"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("cd")), "cd"); |
| } |
| |
| @Test |
| public void forTree_breadthFirst_graphContainingTreeAndDiamond() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); |
| |
| assertEqualCharNodes(traverser.breadthFirst('a'), "abcd"); |
| assertEqualCharNodes(traverser.breadthFirst('b'), "bcd"); |
| assertEqualCharNodes(traverser.breadthFirst('d'), "d"); |
| } |
| |
| @Test |
| public void forTree_breadthFirstIterable_graphContainingTreeAndDiamond() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); |
| |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("bg")), "bgcdh"); |
| assertEqualCharNodes(traverser.breadthFirst(charactersOf("ga")), "gahbcd"); |
| } |
| |
| @Test |
| public void forTree_breadthFirst_twoTrees() { |
| Iterable<Character> result = Traverser.forTree(TWO_TREES).breadthFirst('a'); |
| |
| assertEqualCharNodes(result, "ab"); |
| } |
| |
| @Test |
| public void forTree_breadthFirstIterable_twoTrees() { |
| assertEqualCharNodes(Traverser.forTree(TWO_TREES).breadthFirst(charactersOf("a")), "ab"); |
| assertEqualCharNodes(Traverser.forTree(TWO_TREES).breadthFirst(charactersOf("ca")), "cadb"); |
| } |
| |
| @Test |
| public void forTree_breadthFirst_singleRoot() { |
| Iterable<Character> result = Traverser.forTree(SINGLE_ROOT).breadthFirst('a'); |
| |
| assertEqualCharNodes(result, "a"); |
| } |
| |
| @Test |
| public void forTree_breadthFirstIterable_singleRoot() { |
| Iterable<Character> result = Traverser.forTree(SINGLE_ROOT).breadthFirst(charactersOf("a")); |
| |
| assertEqualCharNodes(result, "a"); |
| } |
| |
| @Test |
| public void forTree_breadthFirst_emptyGraph() { |
| try { |
| Traverser.forTree(createDirectedGraph()).breadthFirst('a'); |
| fail("Expected IllegalArgumentException"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| @Test |
| public void forTree_breadthFirstIterable_emptyGraph() { |
| assertEqualCharNodes( |
| Traverser.forTree(createDirectedGraph()).breadthFirst(charactersOf("")), ""); |
| try { |
| Traverser.forTree(createDirectedGraph()).breadthFirst(charactersOf("a")); |
| fail("Expected IllegalArgumentException"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| @Test |
| public void forTree_breadthFirst_iterableIsLazy() { |
| RequestSavingGraph graph = new RequestSavingGraph(TREE); |
| Iterable<Character> result = Traverser.forGraph(graph).breadthFirst('h'); |
| |
| assertEqualCharNodes(Iterables.limit(result, 2), "hd"); |
| assertThat(graph.requestedNodes).containsExactly('h', 'h', 'd'); |
| |
| // Iterate again to see if calculation is done again |
| assertEqualCharNodes(Iterables.limit(result, 2), "hd"); |
| assertThat(graph.requestedNodes).containsExactly('h', 'h', 'h', 'd', 'd'); |
| } |
| |
| @Test |
| public void forTree_breadthFirstIterable_iterableIsLazy() { |
| RequestSavingGraph graph = new RequestSavingGraph(TREE); |
| Iterable<Character> result = Traverser.forGraph(graph).breadthFirst(charactersOf("dg")); |
| |
| assertEqualCharNodes(Iterables.limit(result, 3), "dga"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'd', 'd', 'g', 'g'); |
| |
| // Iterate again to see if calculation is done again |
| assertEqualCharNodes(Iterables.limit(result, 3), "dga"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'd', 'd', 'd', 'g', 'g', 'g'); |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrderIterable_tree() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(TREE); |
| |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("h")), "hdabcegf"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("d")), "dabc"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "a"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrderIterableIterable_tree() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(TREE); |
| |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("")), ""); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("h")), "hdabcegf"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("gd")), "gfdabc"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("age")), "agfe"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrder_cyclicGraphContainingTree() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); |
| |
| assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abcd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bcd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "d"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrderIterable_cyclicGraphContainingTree() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); |
| |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abcd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("b")), "bcd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("cd")), "cd"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrder_graphContainingTreeAndDiamond() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); |
| |
| assertEqualCharNodes(traverser.depthFirstPreOrder('a'), "abcd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('b'), "bcd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder('d'), "d"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrderIterable_graphContainingTreeAndDiamond() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); |
| |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("a")), "abcd"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("bg")), "bcdgh"); |
| assertEqualCharNodes(traverser.depthFirstPreOrder(charactersOf("ga")), "ghabcd"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrder_twoTrees() { |
| Iterable<Character> result = Traverser.forTree(TWO_TREES).depthFirstPreOrder('a'); |
| |
| assertEqualCharNodes(result, "ab"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrderIterable_twoTrees() { |
| assertEqualCharNodes(Traverser.forTree(TWO_TREES).depthFirstPreOrder(charactersOf("a")), "ab"); |
| assertEqualCharNodes( |
| Traverser.forTree(TWO_TREES).depthFirstPreOrder(charactersOf("ca")), "cdab"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrder_singleRoot() { |
| Iterable<Character> result = Traverser.forTree(SINGLE_ROOT).depthFirstPreOrder('a'); |
| |
| assertEqualCharNodes(result, "a"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrderIterable_singleRoot() { |
| Iterable<Character> result = |
| Traverser.forTree(SINGLE_ROOT).depthFirstPreOrder(charactersOf("a")); |
| |
| assertEqualCharNodes(result, "a"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrder_emptyGraph() { |
| try { |
| Traverser.forTree(createDirectedGraph()).depthFirstPreOrder('a'); |
| fail("Expected IllegalArgumentException"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrderIterable_emptyGraph() { |
| assertEqualCharNodes( |
| Traverser.forTree(createDirectedGraph()).depthFirstPreOrder(charactersOf("")), ""); |
| try { |
| Traverser.forTree(createDirectedGraph()).depthFirstPreOrder(charactersOf("a")); |
| fail("Expected IllegalArgumentException"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrder_iterableIsLazy() { |
| RequestSavingGraph graph = new RequestSavingGraph(TREE); |
| Iterable<Character> result = Traverser.forGraph(graph).depthFirstPreOrder('h'); |
| |
| assertEqualCharNodes(Iterables.limit(result, 2), "hd"); |
| assertThat(graph.requestedNodes).containsExactly('h', 'h', 'd', 'a'); |
| |
| // Iterate again to see if calculation is done again |
| assertEqualCharNodes(Iterables.limit(result, 2), "hd"); |
| assertThat(graph.requestedNodes).containsExactly('h', 'h', 'h', 'd', 'd', 'a', 'a'); |
| } |
| |
| @Test |
| public void forTree_depthFirstPreOrderIterable_iterableIsLazy() { |
| RequestSavingGraph graph = new RequestSavingGraph(TREE); |
| Iterable<Character> result = Traverser.forGraph(graph).depthFirstPreOrder(charactersOf("dg")); |
| |
| assertEqualCharNodes(Iterables.limit(result, 2), "da"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'd', 'd', 'g'); |
| |
| // Iterate again to see if calculation is done again |
| assertEqualCharNodes(Iterables.limit(result, 2), "da"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'd', 'd', 'd', 'g'); |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrder_tree() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(TREE); |
| |
| assertEqualCharNodes(traverser.depthFirstPostOrder('h'), "abcdefgh"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "abcd"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "a"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrderIterable_tree() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(TREE); |
| |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("")), ""); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("h")), "abcdefgh"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("gd")), "fgabcd"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("age")), "afge"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrder_cyclicGraphContainingTree() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); |
| |
| assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "cdba"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "cdb"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "d"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrderIterable_cyclicGraphContainingTree() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(CYCLIC_GRAPH_CONTAINING_TREE); |
| |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "cdba"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("b")), "cdb"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("cd")), "cd"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrder_graphContainingTreeAndDiamond() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); |
| |
| assertEqualCharNodes(traverser.depthFirstPostOrder('a'), "cdba"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('b'), "cdb"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder('d'), "d"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrderIterable_graphContainingTreeAndDiamond() throws Exception { |
| Traverser<Character> traverser = Traverser.forTree(GRAPH_CONTAINING_TREE_AND_DIAMOND); |
| |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("a")), "cdba"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("bg")), "cdbhg"); |
| assertEqualCharNodes(traverser.depthFirstPostOrder(charactersOf("ga")), "hgcdba"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrder_twoTrees() { |
| Iterable<Character> result = Traverser.forTree(TWO_TREES).depthFirstPostOrder('a'); |
| |
| assertEqualCharNodes(result, "ba"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrderIterable_twoTrees() { |
| assertEqualCharNodes(Traverser.forTree(TWO_TREES).depthFirstPostOrder(charactersOf("a")), "ba"); |
| assertEqualCharNodes( |
| Traverser.forTree(TWO_TREES).depthFirstPostOrder(charactersOf("ca")), "dcba"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrder_singleRoot() { |
| Iterable<Character> result = Traverser.forTree(SINGLE_ROOT).depthFirstPostOrder('a'); |
| |
| assertEqualCharNodes(result, "a"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrderIterable_singleRoot() { |
| Iterable<Character> result = |
| Traverser.forTree(SINGLE_ROOT).depthFirstPostOrder(charactersOf("a")); |
| |
| assertEqualCharNodes(result, "a"); |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrder_emptyGraph() { |
| try { |
| Traverser.forTree(createDirectedGraph()).depthFirstPostOrder('a'); |
| fail("Expected IllegalArgumentException"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrderIterable_emptyGraph() { |
| assertEqualCharNodes( |
| Traverser.forTree(createDirectedGraph()).depthFirstPostOrder(charactersOf("")), ""); |
| try { |
| Traverser.forTree(createDirectedGraph()).depthFirstPostOrder(charactersOf("a")); |
| fail("Expected IllegalArgumentException"); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrder_iterableIsLazy() { |
| RequestSavingGraph graph = new RequestSavingGraph(TREE); |
| Iterable<Character> result = Traverser.forGraph(graph).depthFirstPostOrder('h'); |
| |
| assertEqualCharNodes(Iterables.limit(result, 2), "ab"); |
| assertThat(graph.requestedNodes).containsExactly('h', 'h', 'd', 'a', 'b'); |
| |
| // Iterate again to see if calculation is done again |
| assertEqualCharNodes(Iterables.limit(result, 2), "ab"); |
| assertThat(graph.requestedNodes).containsExactly('h', 'h', 'h', 'd', 'd', 'a', 'a', 'b', 'b'); |
| } |
| |
| @Test |
| public void forTree_depthFirstPostOrderIterable_iterableIsLazy() { |
| RequestSavingGraph graph = new RequestSavingGraph(TREE); |
| Iterable<Character> result = Traverser.forGraph(graph).depthFirstPostOrder(charactersOf("dg")); |
| |
| assertEqualCharNodes(Iterables.limit(result, 2), "ab"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'b', 'd', 'd', 'g'); |
| |
| // Iterate again to see if calculation is done again |
| assertEqualCharNodes(Iterables.limit(result, 2), "ab"); |
| assertThat(graph.requestedNodes).containsExactly('a', 'a', 'b', 'b', 'd', 'd', 'd', 'g'); |
| } |
| |
| private static SuccessorsFunction<Character> createDirectedGraph(String... edges) { |
| return createGraph(/* directed = */ true, edges); |
| } |
| |
| private static SuccessorsFunction<Character> createUndirectedGraph(String... edges) { |
| return createGraph(/* directed = */ false, edges); |
| } |
| |
| /** |
| * Creates a graph from a list of node pairs (encoded as strings, e.g. "ab" means that this graph |
| * has an edge between 'a' and 'b'). |
| * |
| * <p>The {@code successors} are always returned in alphabetical order. |
| */ |
| private static SuccessorsFunction<Character> createGraph(boolean directed, String... edges) { |
| ImmutableMultimap.Builder<Character, Character> graphMapBuilder = ImmutableMultimap.builder(); |
| for (String edge : edges) { |
| checkArgument( |
| edge.length() == 2, "Expecting each edge to consist of 2 characters but got %s", edge); |
| char node1 = edge.charAt(0); |
| char node2 = edge.charAt(1); |
| graphMapBuilder.put(node1, node2); |
| if (!directed) { |
| graphMapBuilder.put(node2, node1); |
| } |
| } |
| final ImmutableMultimap<Character, Character> graphMap = graphMapBuilder.build(); |
| |
| return new SuccessorsFunction<Character>() { |
| @Override |
| public Iterable<? extends Character> successors(Character node) { |
| checkArgument( |
| graphMap.containsKey(node) || graphMap.containsValue(node), |
| "Node %s is not an element of this graph", |
| node); |
| return Ordering.natural().immutableSortedCopy(graphMap.get(node)); |
| } |
| }; |
| } |
| |
| private static ImmutableGraph<Character> createSingleRootGraph() { |
| MutableGraph<Character> graph = GraphBuilder.directed().build(); |
| graph.addNode('a'); |
| return ImmutableGraph.copyOf(graph); |
| } |
| |
| private static void assertEqualCharNodes(Iterable<Character> result, String expectedCharacters) { |
| assertThat(ImmutableList.copyOf(result)) |
| .containsExactlyElementsIn(Chars.asList(expectedCharacters.toCharArray())) |
| .inOrder(); |
| } |
| |
| private static class RequestSavingGraph implements SuccessorsFunction<Character> { |
| private final SuccessorsFunction<Character> delegate; |
| final Multiset<Character> requestedNodes = HashMultiset.create(); |
| |
| RequestSavingGraph(SuccessorsFunction<Character> delegate) { |
| this.delegate = checkNotNull(delegate); |
| } |
| |
| @Override |
| public Iterable<? extends Character> successors(Character node) { |
| requestedNodes.add(node); |
| return delegate.successors(node); |
| } |
| } |
| } |