001/*
002 * Copyright (C) 2014 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 com.google.common.annotations.Beta;
020import com.google.errorprone.annotations.DoNotMock;
021
022/**
023 * A functional interface for <a
024 * href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)">graph</a>-structured data.
025 *
026 * <p>This interface is meant to be used as the type of a parameter to graph algorithms (such as
027 * topological sort) that only need a way of accessing the predecessors of a node in a graph.
028 *
029 * <h3>Usage</h3>
030 *
031 * Given an algorithm, for example:
032 *
033 * <pre>{@code
034 * public <N> someGraphAlgorithm(N startNode, PredecessorsFunction<N> predecessorsFunction);
035 * }</pre>
036 *
037 * you will invoke it depending on the graph representation you're using.
038 *
039 * <p>If you have an instance of one of the primary {@code common.graph} types ({@link Graph},
040 * {@link ValueGraph}, and {@link Network}):
041 *
042 * <pre>{@code
043 * someGraphAlgorithm(startNode, graph);
044 * }</pre>
045 *
046 * This works because those types each implement {@code PredecessorsFunction}. It will also work
047 * with any other implementation of this interface.
048 *
049 * <p>If you have your own graph implementation based around a custom node type {@code MyNode},
050 * which has a method {@code getParents()} that retrieves its predecessors in a graph:
051 *
052 * <pre>{@code
053 * someGraphAlgorithm(startNode, MyNode::getParents);
054 * }</pre>
055 *
056 * <p>If you have some other mechanism for returning the predecessors of a node, or one that doesn't
057 * return a {@code Iterable<? extends N>}, then you can use a lambda to perform a more general
058 * transformation:
059 *
060 * <pre>{@code
061 * someGraphAlgorithm(startNode, node -> ImmutableList.of(node.mother(), node.father()));
062 * }</pre>
063 *
064 * <p>Graph algorithms that need additional capabilities (accessing both predecessors and
065 * successors, iterating over the edges, etc.) should declare their input to be of a type that
066 * provides those capabilities, such as {@link Graph}, {@link ValueGraph}, or {@link Network}.
067 *
068 * <h3>Additional documentation</h3>
069 *
070 * <p>See the Guava User Guide for the {@code common.graph} package (<a
071 * href="https://github.com/google/guava/wiki/GraphsExplained">"Graphs Explained"</a>) for
072 * additional documentation, including <a
073 * href="https://github.com/google/guava/wiki/GraphsExplained#notes-for-implementors">notes for
074 * implementors</a>
075 *
076 * @author Joshua O'Madadhain
077 * @author Jens Nyman
078 * @param <N> Node parameter type
079 * @since 23.0
080 */
081@Beta
082@DoNotMock("Implement with a lambda, or use GraphBuilder to build a Graph with the desired edges")
083public interface PredecessorsFunction<N> {
084
085  /**
086   * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing
087   * {@code node}'s incoming edges <i>against</i> the direction (if any) of the edge.
088   *
089   * <p>Some algorithms that operate on a {@code PredecessorsFunction} may produce undesired results
090   * if the returned {@link Iterable} contains duplicate elements. Implementations of such
091   * algorithms should document their behavior in the presence of duplicates.
092   *
093   * <p>The elements of the returned {@code Iterable} must each be:
094   *
095   * <ul>
096   *   <li>Non-null
097   *   <li>Usable as {@code Map} keys (see the Guava User Guide's section on <a
098   *       href="https://github.com/google/guava/wiki/GraphsExplained#graph-elements-nodes-and-edges">
099   *       graph elements</a> for details)
100   * </ul>
101   *
102   * @throws IllegalArgumentException if {@code node} is not an element of this graph
103   */
104  Iterable<? extends N> predecessors(N node);
105}