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