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") 083@ElementTypesAreNonnullByDefault 084public interface PredecessorsFunction<N> { 085 086 /** 087 * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing 088 * {@code node}'s incoming edges <i>against</i> the direction (if any) of the edge. 089 * 090 * <p>Some algorithms that operate on a {@code PredecessorsFunction} may produce undesired results 091 * if the returned {@link Iterable} contains duplicate elements. Implementations of such 092 * algorithms should document their behavior in the presence of duplicates. 093 * 094 * <p>The elements of the returned {@code Iterable} must each be: 095 * 096 * <ul> 097 * <li>Non-null 098 * <li>Usable as {@code Map} keys (see the Guava User Guide's section on <a 099 * href="https://github.com/google/guava/wiki/GraphsExplained#graph-elements-nodes-and-edges"> 100 * graph elements</a> for details) 101 * </ul> 102 * 103 * @throws IllegalArgumentException if {@code node} is not an element of this graph 104 */ 105 Iterable<? extends N> predecessors(N node); 106}