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}