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