1 /* 2 * Copyright (C) 2014 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 com.google.common.annotations.Beta; 20 import com.google.errorprone.annotations.DoNotMock; 21 22 /** 23 * A functional interface for <a 24 * href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)">graph</a>-structured data. 25 * 26 * <p>This interface is meant to be used as the type of a parameter to graph algorithms (such as 27 * breadth first traversal) that only need a way of accessing the successors of a node in a graph. 28 * 29 * <h3>Usage</h3> 30 * 31 * Given an algorithm, for example: 32 * 33 * <pre>{@code 34 * public <N> someGraphAlgorithm(N startNode, SuccessorsFunction<N> successorsFunction); 35 * }</pre> 36 * 37 * you will invoke it depending on the graph representation you're using. 38 * 39 * <p>If you have an instance of one of the primary {@code common.graph} types ({@link Graph}, 40 * {@link ValueGraph}, and {@link Network}): 41 * 42 * <pre>{@code 43 * someGraphAlgorithm(startNode, graph); 44 * }</pre> 45 * 46 * This works because those types each implement {@code SuccessorsFunction}. It will also work with 47 * any other implementation of this interface. 48 * 49 * <p>If you have your own graph implementation based around a custom node type {@code MyNode}, 50 * which has a method {@code getChildren()} that retrieves its successors in a graph: 51 * 52 * <pre>{@code 53 * someGraphAlgorithm(startNode, MyNode::getChildren); 54 * }</pre> 55 * 56 * <p>If you have some other mechanism for returning the successors of a node, or one that doesn't 57 * return an {@code Iterable<? extends N>}, then you can use a lambda to perform a more general 58 * transformation: 59 * 60 * <pre>{@code 61 * someGraphAlgorithm(startNode, node -> ImmutableList.of(node.leftChild(), node.rightChild())); 62 * }</pre> 63 * 64 * <p>Graph algorithms that need additional capabilities (accessing both predecessors and 65 * successors, iterating over the edges, etc.) should declare their input to be of a type that 66 * provides those capabilities, such as {@link Graph}, {@link ValueGraph}, or {@link Network}. 67 * 68 * <h3>Additional documentation</h3> 69 * 70 * <p>See the Guava User Guide for the {@code common.graph} package (<a 71 * href="https://github.com/google/guava/wiki/GraphsExplained">"Graphs Explained"</a>) for 72 * additional documentation, including <a 73 * href="https://github.com/google/guava/wiki/GraphsExplained#notes-for-implementors">notes for 74 * implementors</a> 75 * 76 * @author Joshua O'Madadhain 77 * @author Jens Nyman 78 * @param <N> Node parameter type 79 * @since 23.0 80 */ 81 @Beta 82 @DoNotMock("Implement with a lambda, or use GraphBuilder to build a Graph with the desired edges") 83 @ElementTypesAreNonnullByDefault 84 public interface SuccessorsFunction<N> { 85 86 /** 87 * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing 88 * {@code node}'s outgoing edges in the direction (if any) of the edge. 89 * 90 * <p>This is <i>not</i> the same as "all nodes reachable from {@code node} by following outgoing 91 * edges". For that functionality, see {@link Graphs#reachableNodes(Graph, Object)}. 92 * 93 * <p>Some algorithms that operate on a {@code SuccessorsFunction} may produce undesired results 94 * if the returned {@link Iterable} contains duplicate elements. Implementations of such 95 * algorithms should document their behavior in the presence of duplicates. 96 * 97 * <p>The elements of the returned {@code Iterable} must each be: 98 * 99 * <ul> 100 * <li>Non-null 101 * <li>Usable as {@code Map} keys (see the Guava User Guide's section on <a 102 * href="https://github.com/google/guava/wiki/GraphsExplained#graph-elements-nodes-and-edges"> 103 * graph elements</a> for details) 104 * </ul> 105 * 106 * @throws IllegalArgumentException if {@code node} is not an element of this graph 107 */ successors(N node)108 Iterable<? extends N> successors(N node); 109 } 110