1 /* 2 * Copyright (C) 2017 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 java.util.Set; 20 21 /** 22 * A non-public interface for the methods shared between {@link Graph} and {@link ValueGraph}. 23 * 24 * @author James Sexton 25 * @param <N> Node parameter type 26 */ 27 @ElementTypesAreNonnullByDefault 28 interface BaseGraph<N> extends SuccessorsFunction<N>, PredecessorsFunction<N> { 29 // 30 // Graph-level accessors 31 // 32 33 /** Returns all nodes in this graph, in the order specified by {@link #nodeOrder()}. */ nodes()34 Set<N> nodes(); 35 36 /** Returns all edges in this graph. */ edges()37 Set<EndpointPair<N>> edges(); 38 39 // 40 // Graph properties 41 // 42 43 /** 44 * Returns true if the edges in this graph are directed. Directed edges connect a {@link 45 * EndpointPair#source() source node} to a {@link EndpointPair#target() target node}, while 46 * undirected edges connect a pair of nodes to each other. 47 */ isDirected()48 boolean isDirected(); 49 50 /** 51 * Returns true if this graph allows self-loops (edges that connect a node to itself). Attempting 52 * to add a self-loop to a graph that does not allow them will throw an {@link 53 * IllegalArgumentException}. 54 */ allowsSelfLoops()55 boolean allowsSelfLoops(); 56 57 /** Returns the order of iteration for the elements of {@link #nodes()}. */ nodeOrder()58 ElementOrder<N> nodeOrder(); 59 60 /** 61 * Returns an {@link ElementOrder} that specifies the order of iteration for the elements of 62 * {@link #edges()}, {@link #adjacentNodes(Object)}, {@link #predecessors(Object)}, {@link 63 * #successors(Object)} and {@link #incidentEdges(Object)}. 64 * 65 * @since 29.0 66 */ incidentEdgeOrder()67 ElementOrder<N> incidentEdgeOrder(); 68 69 // 70 // Element-level accessors 71 // 72 73 /** 74 * Returns the nodes which have an incident edge in common with {@code node} in this graph. 75 * 76 * <p>This is equal to the union of {@link #predecessors(Object)} and {@link #successors(Object)}. 77 * 78 * @throws IllegalArgumentException if {@code node} is not an element of this graph 79 */ adjacentNodes(N node)80 Set<N> adjacentNodes(N node); 81 82 /** 83 * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing 84 * {@code node}'s incoming edges <i>against</i> the direction (if any) of the edge. 85 * 86 * <p>In an undirected graph, this is equivalent to {@link #adjacentNodes(Object)}. 87 * 88 * @throws IllegalArgumentException if {@code node} is not an element of this graph 89 */ 90 @Override predecessors(N node)91 Set<N> predecessors(N node); 92 93 /** 94 * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing 95 * {@code node}'s outgoing edges in the direction (if any) of the edge. 96 * 97 * <p>In an undirected graph, this is equivalent to {@link #adjacentNodes(Object)}. 98 * 99 * <p>This is <i>not</i> the same as "all nodes reachable from {@code node} by following outgoing 100 * edges". For that functionality, see {@link Graphs#reachableNodes(Graph, Object)}. 101 * 102 * @throws IllegalArgumentException if {@code node} is not an element of this graph 103 */ 104 @Override successors(N node)105 Set<N> successors(N node); 106 107 /** 108 * Returns the edges in this graph whose endpoints include {@code node}. 109 * 110 * <p>This is equal to the union of incoming and outgoing edges. 111 * 112 * @throws IllegalArgumentException if {@code node} is not an element of this graph 113 * @since 24.0 114 */ incidentEdges(N node)115 Set<EndpointPair<N>> incidentEdges(N node); 116 117 /** 118 * Returns the count of {@code node}'s incident edges, counting self-loops twice (equivalently, 119 * the number of times an edge touches {@code node}). 120 * 121 * <p>For directed graphs, this is equal to {@code inDegree(node) + outDegree(node)}. 122 * 123 * <p>For undirected graphs, this is equal to {@code incidentEdges(node).size()} + (number of 124 * self-loops incident to {@code node}). 125 * 126 * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}. 127 * 128 * @throws IllegalArgumentException if {@code node} is not an element of this graph 129 */ degree(N node)130 int degree(N node); 131 132 /** 133 * Returns the count of {@code node}'s incoming edges (equal to {@code predecessors(node).size()}) 134 * in a directed graph. In an undirected graph, returns the {@link #degree(Object)}. 135 * 136 * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}. 137 * 138 * @throws IllegalArgumentException if {@code node} is not an element of this graph 139 */ inDegree(N node)140 int inDegree(N node); 141 142 /** 143 * Returns the count of {@code node}'s outgoing edges (equal to {@code successors(node).size()}) 144 * in a directed graph. In an undirected graph, returns the {@link #degree(Object)}. 145 * 146 * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}. 147 * 148 * @throws IllegalArgumentException if {@code node} is not an element of this graph 149 */ outDegree(N node)150 int outDegree(N node); 151 152 /** 153 * Returns true if there is an edge that directly connects {@code nodeU} to {@code nodeV}. This is 154 * equivalent to {@code nodes().contains(nodeU) && successors(nodeU).contains(nodeV)}. 155 * 156 * <p>In an undirected graph, this is equal to {@code hasEdgeConnecting(nodeV, nodeU)}. 157 * 158 * @since 23.0 159 */ hasEdgeConnecting(N nodeU, N nodeV)160 boolean hasEdgeConnecting(N nodeU, N nodeV); 161 162 /** 163 * Returns true if there is an edge that directly connects {@code endpoints} (in the order, if 164 * any, specified by {@code endpoints}). This is equivalent to {@code 165 * edges().contains(endpoints)}. 166 * 167 * <p>Unlike the other {@code EndpointPair}-accepting methods, this method does not throw if the 168 * endpoints are unordered; it simply returns false. This is for consistency with the behavior of 169 * {@link Collection#contains(Object)} (which does not generally throw if the object cannot be 170 * present in the collection), and the desire to have this method's behavior be compatible with 171 * {@code edges().contains(endpoints)}. 172 * 173 * @since 27.1 174 */ hasEdgeConnecting(EndpointPair<N> endpoints)175 boolean hasEdgeConnecting(EndpointPair<N> endpoints); 176 } 177