001/*
002 * Copyright (C) 2017 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.graph;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020
021import com.google.common.annotations.Beta;
022import com.google.common.collect.UnmodifiableIterator;
023import java.util.ArrayDeque;
024import java.util.HashSet;
025import java.util.Iterator;
026import java.util.Queue;
027import java.util.Set;
028
029/**
030 * Provides methods for traversing a graph.
031 *
032 * @author Jens Nyman
033 * @param <N> Node parameter type
034 * @since 23.1
035 */
036@Beta
037public abstract class Traverser<N> {
038
039  /**
040   * Creates a new traverser for the given general {@code graph}.
041   *
042   * <p>If {@code graph} is known to be tree-shaped, consider using {@link
043   * #forTree(SuccessorsFunction)} instead.
044   *
045   * <p><b>Performance notes</b>
046   *
047   * <ul>
048   *   <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from
049   *       the start node), assuming that the node objects have <i>O(1)</i> {@code equals()} and
050   *       {@code hashCode()} implementations.
051   *   <li>While traversing, the traverser will use <i>O(n)</i> space (where <i>n</i> is the number
052   *       of nodes that have thus far been visited), plus <i>O(H)</i> space (where <i>H</i> is the
053   *       number of nodes that have been seen but not yet visited, that is, the "horizon").
054   * </ul>
055   *
056   * @param graph {@link SuccessorsFunction} representing a general graph that may have cycles.
057   */
058  public static <N> Traverser<N> forGraph(SuccessorsFunction<N> graph) {
059    return new GraphTraverser<>(graph);
060  }
061
062  /**
063   * Creates a new traverser for a directed acyclic graph that has at most one path from the start
064   * node to any node reachable from the start node, such as a tree.
065   *
066   * <p>Providing graphs that don't conform to the above description may lead to:
067   *
068   * <ul>
069   *   <li>Traversal not terminating (if the graph has cycles)
070   *   <li>Nodes being visited multiple times (if multiple paths exist from the start node to any
071   *       node reachable from it)
072   * </ul>
073   *
074   * In these cases, use {@link #forGraph(SuccessorsFunction)} instead.
075   *
076   * <p><b>Performance notes</b>
077   *
078   * <ul>
079   *   <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from
080   *       the start node).
081   *   <li>While traversing, the traverser will use <i>O(H)</i> space (where <i>H</i> is the number
082   *       of nodes that have been seen but not yet visited, that is, the "horizon").
083   * </ul>
084   *
085   * <p><b>Examples</b>
086   *
087   * <p>This is a valid input graph (all edges are directed facing downwards):
088   *
089   * <pre>{@code
090   *    a     b      c
091   *   / \   / \     |
092   *  /   \ /   \    |
093   * d     e     f   g
094   *       |
095   *       |
096   *       h
097   * }</pre>
098   *
099   * <p>This is <b>not</b> a valid input graph (all edges are directed facing downwards):
100   *
101   * <pre>{@code
102   *    a     b
103   *   / \   / \
104   *  /   \ /   \
105   * c     d     e
106   *        \   /
107   *         \ /
108   *          f
109   * }</pre>
110   *
111   * <p>because there are two paths from {@code b} to {@code f} ({@code b->d->f} and {@code
112   * b->e->f}).
113   *
114   * <p><b>Note on binary trees</b>
115   *
116   * <p>This method can be used to traverse over a binary tree. Given methods {@code
117   * leftChild(node)} and {@code rightChild(node)}, this method can be called as
118   *
119   * <pre>{@code
120   * Traverser.forTree(node -> ImmutableList.of(leftChild(node), rightChild(node)));
121   * }</pre>
122   *
123   * @param tree {@link SuccessorsFunction} representing a directed acyclic graph that has at most
124   *     one path between any two nodes
125   */
126  public static <N> Traverser<N> forTree(SuccessorsFunction<N> tree) {
127    // TODO(b/27898002): Implement
128    throw new UnsupportedOperationException("Not yet implemented");
129  }
130
131  /**
132   * Returns an unmodifiable iterable over the nodes in the graph, using breadth-first traversal.
133   * That is, all the nodes of depth 0 are returned, then depth 1, then 2, and so on.
134   *
135   * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
136   * the order {@code abcdef} (assuming successors are returned in alphabetical order).
137   *
138   * <pre>{@code
139   * b ---- a ---- d
140   * |      |
141   * |      |
142   * e ---- c ---- f
143   * }</pre>
144   *
145   * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
146   * while iteration is in progress.
147   *
148   * <p>The returned iterable can be iterated over multiple times. Every iterator will compute its
149   * next element on the fly. It is thus possible to limit the traversal to a certain number of
150   * nodes as follows:
151   *
152   * <pre>{@code
153   * Iterables.limit(Traverser.forGraph(graph).breadthFirst(node), maxNumberOfNodes);
154   * }</pre>
155   *
156   * <p>See <a href="https://en.wikipedia.org/wiki/Breadth-first_search">Wikipedia</a> for more
157   * info.
158   */
159  public abstract Iterable<N> breadthFirst(N startNode);
160
161  /**
162   * Returns an unmodifiable iterable over the nodes in the graph, using depth-first pre-order
163   * traversal. That is, the nodes are returned in the order they are visited for the first time.
164   *
165   * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
166   * the order {@code abcdef} (assuming successors are returned in alphabetical order).
167   *
168   * <pre>{@code
169   * b ---- a ---- f
170   * |      |
171   * |      |
172   * c ---- d ---- e
173   * }</pre>
174   *
175   * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
176   * while iteration is in progress.
177   *
178   * <p>The returned iterable can be iterated over multiple times. Every iterator will compute its
179   * next element on the fly. It is thus possible to limit the traversal to a certain number of
180   * nodes as follows:
181   *
182   * <pre>{@code
183   * Iterables.limit(
184   *     Traverser.forGraph(graph).depthFirstPreOrder(node), maxNumberOfNodes);
185   * }</pre>
186   *
187   * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info.
188   */
189  public abstract Iterable<N> depthFirstPreOrder(N startNode);
190
191  /**
192   * Returns an unmodifiable iterable over the nodes in the graph, using depth-first post-order
193   * traversal. That is, the nodes are returned in the order they are visited for the last time.
194   *
195   * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
196   * the order {@code edcbfa} (assuming successors are returned in alphabetical order).
197   *
198   * <pre>{@code
199   * b ---- a ---- f
200   * |      |
201   * |      |
202   * c ---- d ---- e
203   * }</pre>
204   *
205   * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
206   * while iteration is in progress.
207   *
208   * <p>The returned iterable can be iterated over multiple times. Every iterator will compute its
209   * next element on the fly. It is thus possible to limit the traversal to a certain number of
210   * nodes as follows:
211   *
212   * <pre>{@code
213   * Iterables.limit(
214   *     Traverser.forGraph(graph).depthFirstPostOrder(node), maxNumberOfNodes);
215   * }</pre>
216   *
217   * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info.
218   */
219  public abstract Iterable<N> depthFirstPostOrder(N startNode);
220
221  private static class GraphTraverser<N> extends Traverser<N> {
222    private final SuccessorsFunction<N> graph;
223
224    GraphTraverser(SuccessorsFunction<N> graph) {
225      this.graph = checkNotNull(graph);
226    }
227
228    @Override
229    public Iterable<N> breadthFirst(final N startNode) {
230      return new Iterable<N>() {
231        @Override
232        public Iterator<N> iterator() {
233          return new BreadthFirstIterator(startNode);
234        }
235      };
236    }
237
238    @Override
239    public Iterable<N> depthFirstPreOrder(N startNode) {
240      // TODO(b/27898002): Implement
241      throw new UnsupportedOperationException("Not yet implemented");
242    }
243
244    @Override
245    public Iterable<N> depthFirstPostOrder(N startNode) {
246      // TODO(b/27898002): Implement
247      throw new UnsupportedOperationException("Not yet implemented");
248    }
249
250    final class BreadthFirstIterator extends UnmodifiableIterator<N> {
251      final Queue<N> queue = new ArrayDeque<>();
252      final Set<N> visited = new HashSet<>();
253
254      BreadthFirstIterator(N root) {
255        queue.add(root);
256        visited.add(root);
257      }
258
259      @Override
260      public boolean hasNext() {
261        return !queue.isEmpty();
262      }
263
264      @Override
265      public N next() {
266        N current = queue.remove();
267        for (N neighbor : graph.successors(current)) {
268          if (visited.add(neighbor)) {
269            queue.add(neighbor);
270          }
271        }
272        return current;
273      }
274    }
275  }
276}