View Javadoc
1   /*
2    * Copyright (C) 2017 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.graph;
18  
19  import static com.google.common.base.Preconditions.checkNotNull;
20  
21  import com.google.common.annotations.Beta;
22  import com.google.common.collect.AbstractIterator;
23  import com.google.common.collect.UnmodifiableIterator;
24  import java.util.ArrayDeque;
25  import java.util.Deque;
26  import java.util.HashSet;
27  import java.util.Iterator;
28  import java.util.Queue;
29  import java.util.Set;
30  
31  /**
32   * Provides methods for traversing a graph.
33   *
34   * @author Jens Nyman
35   * @param <N> Node parameter type
36   * @since 23.1
37   */
38  @Beta
39  public abstract class Traverser<N> {
40  
41    /**
42     * Creates a new traverser for the given general {@code graph}.
43     *
44     * <p>If {@code graph} is known to be tree-shaped, consider using {@link
45     * #forTree(SuccessorsFunction)} instead.
46     *
47     * <p><b>Performance notes</b>
48     *
49     * <ul>
50     *   <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from
51     *       the start node), assuming that the node objects have <i>O(1)</i> {@code equals()} and
52     *       {@code hashCode()} implementations.
53     *   <li>While traversing, the traverser will use <i>O(n)</i> space (where <i>n</i> is the number
54     *       of nodes that have thus far been visited), plus <i>O(H)</i> space (where <i>H</i> is the
55     *       number of nodes that have been seen but not yet visited, that is, the "horizon").
56     * </ul>
57     *
58     * @param graph {@link SuccessorsFunction} representing a general graph that may have cycles.
59     */
60    public static <N> Traverser<N> forGraph(SuccessorsFunction<N> graph) {
61      return new GraphTraverser<>(graph);
62    }
63  
64    /**
65     * Creates a new traverser for a directed acyclic graph that has at most one path from the start
66     * node to any node reachable from the start node, such as a tree.
67     *
68     * <p>Providing graphs that don't conform to the above description may lead to:
69     *
70     * <ul>
71     *   <li>Traversal not terminating (if the graph has cycles)
72     *   <li>Nodes being visited multiple times (if multiple paths exist from the start node to any
73     *       node reachable from it)
74     * </ul>
75     *
76     * In these cases, use {@link #forGraph(SuccessorsFunction)} instead.
77     *
78     * <p><b>Performance notes</b>
79     *
80     * <ul>
81     *   <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from
82     *       the start node).
83     *   <li>While traversing, the traverser will use <i>O(H)</i> space (where <i>H</i> is the number
84     *       of nodes that have been seen but not yet visited, that is, the "horizon").
85     * </ul>
86     *
87     * <p><b>Examples</b>
88     *
89     * <p>This is a valid input graph (all edges are directed facing downwards):
90     *
91     * <pre>{@code
92     *    a     b      c
93     *   / \   / \     |
94     *  /   \ /   \    |
95     * d     e     f   g
96     *       |
97     *       |
98     *       h
99     * }</pre>
100    *
101    * <p>This is <b>not</b> a valid input graph (all edges are directed facing downwards):
102    *
103    * <pre>{@code
104    *    a     b
105    *   / \   / \
106    *  /   \ /   \
107    * c     d     e
108    *        \   /
109    *         \ /
110    *          f
111    * }</pre>
112    *
113    * <p>because there are two paths from {@code b} to {@code f} ({@code b->d->f} and {@code
114    * b->e->f}).
115    *
116    * <p><b>Note on binary trees</b>
117    *
118    * <p>This method can be used to traverse over a binary tree. Given methods {@code
119    * leftChild(node)} and {@code rightChild(node)}, this method can be called as
120    *
121    * <pre>{@code
122    * Traverser.forTree(node -> ImmutableList.of(leftChild(node), rightChild(node)));
123    * }</pre>
124    *
125    * @param tree {@link SuccessorsFunction} representing a directed acyclic graph that has at most
126    *     one path between any two nodes
127    */
128   public static <N> Traverser<N> forTree(SuccessorsFunction<N> tree) {
129     // TODO(b/27898002): Implement
130     throw new UnsupportedOperationException("Not yet implemented");
131   }
132 
133   /**
134    * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
135    * the order of a breadth-first traversal. That is, all the nodes of depth 0 are returned, then
136    * depth 1, then 2, and so on.
137    *
138    * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
139    * the order {@code abcdef} (assuming successors are returned in alphabetical order).
140    *
141    * <pre>{@code
142    * b ---- a ---- d
143    * |      |
144    * |      |
145    * e ---- c ---- f
146    * }</pre>
147    *
148    * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
149    * while iteration is in progress.
150    *
151    * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
152    * compute its next element on the fly. It is thus possible to limit the traversal to a certain
153    * number of nodes as follows:
154    *
155    * <pre>{@code
156    * Iterables.limit(Traverser.forGraph(graph).breadthFirst(node), maxNumberOfNodes);
157    * }</pre>
158    *
159    * <p>See <a href="https://en.wikipedia.org/wiki/Breadth-first_search">Wikipedia</a> for more
160    * info.
161    */
162   public abstract Iterable<N> breadthFirst(N startNode);
163 
164   /**
165    * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
166    * the order of a depth-first pre-order traversal. "Pre-order" implies that nodes appear in the
167    * {@code Iterable} in the order in which they are first visited.
168    *
169    * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
170    * the order {@code abecfd} (assuming successors are returned in alphabetical order).
171    *
172    * <pre>{@code
173    * b ---- a ---- d
174    * |      |
175    * |      |
176    * e ---- c ---- f
177    * }</pre>
178    *
179    * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
180    * while iteration is in progress.
181    *
182    * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
183    * compute its next element on the fly. It is thus possible to limit the traversal to a certain
184    * number of nodes as follows:
185    *
186    * <pre>{@code
187    * Iterables.limit(
188    *     Traverser.forGraph(graph).depthFirstPreOrder(node), maxNumberOfNodes);
189    * }</pre>
190    *
191    * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info.
192    */
193   public abstract Iterable<N> depthFirstPreOrder(N startNode);
194 
195   /**
196    * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
197    * the order of a depth-first post-order traversal. "Post-order" implies that nodes appear in the
198    * {@code Iterable} in the order in which they are visited for the last time.
199    *
200    * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
201    * the order {@code fcebda} (assuming successors are returned in alphabetical order).
202    *
203    * <pre>{@code
204    * b ---- a ---- d
205    * |      |
206    * |      |
207    * e ---- c ---- f
208    * }</pre>
209    *
210    * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
211    * while iteration is in progress.
212    *
213    * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
214    * compute its next element on the fly. It is thus possible to limit the traversal to a certain
215    * number of nodes as follows:
216    *
217    * <pre>{@code
218    * Iterables.limit(
219    *     Traverser.forGraph(graph).depthFirstPostOrder(node), maxNumberOfNodes);
220    * }</pre>
221    *
222    * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info.
223    */
224   public abstract Iterable<N> depthFirstPostOrder(N startNode);
225 
226   private static final class GraphTraverser<N> extends Traverser<N> {
227     private final SuccessorsFunction<N> graph;
228 
229     GraphTraverser(SuccessorsFunction<N> graph) {
230       this.graph = checkNotNull(graph);
231     }
232 
233     @Override
234     public Iterable<N> breadthFirst(final N startNode) {
235       return new Iterable<N>() {
236         @Override
237         public Iterator<N> iterator() {
238           return new BreadthFirstIterator(startNode);
239         }
240       };
241     }
242 
243     @Override
244     public Iterable<N> depthFirstPreOrder(final N startNode) {
245       return new Iterable<N>() {
246         @Override
247         public Iterator<N> iterator() {
248           return new DepthFirstIterator(startNode, Order.PREORDER);
249         }
250       };
251     }
252 
253     @Override
254     public Iterable<N> depthFirstPostOrder(final N startNode) {
255       return new Iterable<N>() {
256         @Override
257         public Iterator<N> iterator() {
258           return new DepthFirstIterator(startNode, Order.POSTORDER);
259         }
260       };
261     }
262 
263     private final class BreadthFirstIterator extends UnmodifiableIterator<N> {
264       private final Queue<N> queue = new ArrayDeque<>();
265       private final Set<N> visited = new HashSet<>();
266 
267       BreadthFirstIterator(N root) {
268         queue.add(root);
269         visited.add(root);
270       }
271 
272       @Override
273       public boolean hasNext() {
274         return !queue.isEmpty();
275       }
276 
277       @Override
278       public N next() {
279         N current = queue.remove();
280         for (N neighbor : graph.successors(current)) {
281           if (visited.add(neighbor)) {
282             queue.add(neighbor);
283           }
284         }
285         return current;
286       }
287     }
288 
289     private final class DepthFirstIterator extends AbstractIterator<N> {
290       private final Deque<NodeAndSuccessors> stack = new ArrayDeque<>();
291       private final Set<N> visited = new HashSet<>();
292       private final Order order;
293 
294       DepthFirstIterator(N root, Order order) {
295         // our invariant is that in computeNext we call next on the iterator at the top first, so we
296         // need to start with one additional item on that iterator
297         stack.push(withSuccessors(root));
298         this.order = order;
299       }
300 
301       @Override
302       protected N computeNext() {
303         while (true) {
304           if (stack.isEmpty()) {
305             return endOfData();
306           }
307           NodeAndSuccessors node = stack.getFirst();
308           boolean firstVisit = visited.add(node.node);
309           boolean lastVisit = !node.successors.hasNext();
310           boolean produceNode =
311               (firstVisit && order == Order.PREORDER) || (lastVisit && order == Order.POSTORDER);
312           if (lastVisit) {
313             stack.pop();
314           } else {
315             // we need to push a neighbor, but only if we haven't already seen it
316             N child = node.successors.next();
317             if (!visited.contains(child)) {
318               stack.push(withSuccessors(child));
319             }
320           }
321           if (produceNode) {
322             return node.node;
323           }
324         }
325       }
326 
327       NodeAndSuccessors withSuccessors(N node) {
328         return new NodeAndSuccessors(node, graph.successors(node));
329       }
330 
331       /** A simple tuple of a node and a partially iterated {@link Iterator} of its successors. */
332       private final class NodeAndSuccessors {
333         final N node;
334         final Iterator<? extends N> successors;
335 
336         NodeAndSuccessors(N node, Iterable<? extends N> successors) {
337           this.node = node;
338           this.successors = successors.iterator();
339         }
340       }
341     }
342   }
343 
344   private enum Order {
345     PREORDER,
346     POSTORDER
347   }
348 }