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