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 import java.util.Set;
21 import org.checkerframework.checker.nullness.compatqual.NullableDecl;
22
23 /**
24 * An interface for <a
25 * href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)">graph</a>-structured data,
26 * whose edges are anonymous entities with no identity or information of their own.
27 *
28 * <p>A graph is composed of a set of nodes and a set of edges connecting pairs of nodes.
29 *
30 * <p>There are three primary interfaces provided to represent graphs. In order of increasing
31 * complexity they are: {@link Graph}, {@link ValueGraph}, and {@link Network}. You should generally
32 * prefer the simplest interface that satisfies your use case. See the <a
33 * href="https://github.com/google/guava/wiki/GraphsExplained#choosing-the-right-graph-type">
34 * "Choosing the right graph type"</a> section of the Guava User Guide for more details.
35 *
36 * <h3>Capabilities</h3>
37 *
38 * <p>{@code Graph} supports the following use cases (<a
39 * href="https://github.com/google/guava/wiki/GraphsExplained#definitions">definitions of
40 * terms</a>):
41 *
42 * <ul>
43 * <li>directed graphs
44 * <li>undirected graphs
45 * <li>graphs that do/don't allow self-loops
46 * <li>graphs whose nodes/edges are insertion-ordered, sorted, or unordered
47 * </ul>
48 *
49 * <p>{@code Graph} explicitly does not support parallel edges, and forbids implementations or
50 * extensions with parallel edges. If you need parallel edges, use {@link Network}.
51 *
52 * <h3>Building a {@code Graph}</h3>
53 *
54 * <p>The implementation classes that {@code common.graph} provides are not public, by design. To
55 * create an instance of one of the built-in implementations of {@code Graph}, use the {@link
56 * GraphBuilder} class:
57 *
58 * <pre>{@code
59 * MutableGraph<Integer> graph = GraphBuilder.undirected().build();
60 * }</pre>
61 *
62 * <p>{@link GraphBuilder#build()} returns an instance of {@link MutableGraph}, which is a subtype
63 * of {@code Graph} that provides methods for adding and removing nodes and edges. If you do not
64 * need to mutate a graph (e.g. if you write a method than runs a read-only algorithm on the graph),
65 * you should use the non-mutating {@link Graph} interface, or an {@link ImmutableGraph}.
66 *
67 * <p>You can create an immutable copy of an existing {@code Graph} using {@link
68 * ImmutableGraph#copyOf(Graph)}:
69 *
70 * <pre>{@code
71 * ImmutableGraph<Integer> immutableGraph = ImmutableGraph.copyOf(graph);
72 * }</pre>
73 *
74 * <p>Instances of {@link ImmutableGraph} do not implement {@link MutableGraph} (obviously!) and are
75 * contractually guaranteed to be unmodifiable and thread-safe.
76 *
77 * <p>The Guava User Guide has <a
78 * href="https://github.com/google/guava/wiki/GraphsExplained#building-graph-instances">more
79 * information on (and examples of) building graphs</a>.
80 *
81 * <h3>Additional documentation</h3>
82 *
83 * <p>See the Guava User Guide for the {@code common.graph} package (<a
84 * href="https://github.com/google/guava/wiki/GraphsExplained">"Graphs Explained"</a>) for
85 * additional documentation, including:
86 *
87 * <ul>
88 * <li><a
89 * href="https://github.com/google/guava/wiki/GraphsExplained#equals-hashcode-and-graph-equivalence">
90 * {@code equals()}, {@code hashCode()}, and graph equivalence</a>
91 * <li><a href="https://github.com/google/guava/wiki/GraphsExplained#synchronization">
92 * Synchronization policy</a>
93 * <li><a href="https://github.com/google/guava/wiki/GraphsExplained#notes-for-implementors">Notes
94 * for implementors</a>
95 * </ul>
96 *
97 * @author James Sexton
98 * @author Joshua O'Madadhain
99 * @param <N> Node parameter type
100 * @since 20.0
101 */
102 @Beta
103 public interface Graph<N> extends BaseGraph<N> {
104 //
105 // Graph-level accessors
106 //
107
108 /** Returns all nodes in this graph, in the order specified by {@link #nodeOrder()}. */
109 @Override
110 Set<N> nodes();
111
112 /** Returns all edges in this graph. */
113 @Override
114 Set<EndpointPair<N>> edges();
115
116 //
117 // Graph properties
118 //
119
120 /**
121 * Returns true if the edges in this graph are directed. Directed edges connect a {@link
122 * EndpointPair#source() source node} to a {@link EndpointPair#target() target node}, while
123 * undirected edges connect a pair of nodes to each other.
124 */
125 @Override
126 boolean isDirected();
127
128 /**
129 * Returns true if this graph allows self-loops (edges that connect a node to itself). Attempting
130 * to add a self-loop to a graph that does not allow them will throw an {@link
131 * IllegalArgumentException}.
132 */
133 @Override
134 boolean allowsSelfLoops();
135
136 /** Returns the order of iteration for the elements of {@link #nodes()}. */
137 @Override
138 ElementOrder<N> nodeOrder();
139
140 //
141 // Element-level accessors
142 //
143
144 /**
145 * Returns the nodes which have an incident edge in common with {@code node} in this graph.
146 *
147 * @throws IllegalArgumentException if {@code node} is not an element of this graph
148 */
149 @Override
150 Set<N> adjacentNodes(N node);
151
152 /**
153 * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing
154 * {@code node}'s incoming edges <i>against</i> the direction (if any) of the edge.
155 *
156 * <p>In an undirected graph, this is equivalent to {@link #adjacentNodes(Object)}.
157 *
158 * @throws IllegalArgumentException if {@code node} is not an element of this graph
159 */
160 @Override
161 Set<N> predecessors(N node);
162
163 /**
164 * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing
165 * {@code node}'s outgoing edges in the direction (if any) of the edge.
166 *
167 * <p>In an undirected graph, this is equivalent to {@link #adjacentNodes(Object)}.
168 *
169 * <p>This is <i>not</i> the same as "all nodes reachable from {@code node} by following outgoing
170 * edges". For that functionality, see {@link Graphs#reachableNodes(Graph, Object)}.
171 *
172 * @throws IllegalArgumentException if {@code node} is not an element of this graph
173 */
174 @Override
175 Set<N> successors(N node);
176
177 /**
178 * Returns the edges in this graph whose endpoints include {@code node}.
179 *
180 * @throws IllegalArgumentException if {@code node} is not an element of this graph
181 * @since 24.0
182 */
183 @Override
184 Set<EndpointPair<N>> incidentEdges(N node);
185
186 /**
187 * Returns the count of {@code node}'s incident edges, counting self-loops twice (equivalently,
188 * the number of times an edge touches {@code node}).
189 *
190 * <p>For directed graphs, this is equal to {@code inDegree(node) + outDegree(node)}.
191 *
192 * <p>For undirected graphs, this is equal to {@code incidentEdges(node).size()} + (number of
193 * self-loops incident to {@code node}).
194 *
195 * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
196 *
197 * @throws IllegalArgumentException if {@code node} is not an element of this graph
198 */
199 @Override
200 int degree(N node);
201
202 /**
203 * Returns the count of {@code node}'s incoming edges (equal to {@code predecessors(node).size()})
204 * in a directed graph. In an undirected graph, returns the {@link #degree(Object)}.
205 *
206 * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
207 *
208 * @throws IllegalArgumentException if {@code node} is not an element of this graph
209 */
210 @Override
211 int inDegree(N node);
212
213 /**
214 * Returns the count of {@code node}'s outgoing edges (equal to {@code successors(node).size()})
215 * in a directed graph. In an undirected graph, returns the {@link #degree(Object)}.
216 *
217 * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
218 *
219 * @throws IllegalArgumentException if {@code node} is not an element of this graph
220 */
221 @Override
222 int outDegree(N node);
223
224 /**
225 * Returns true if there is an edge directly connecting {@code nodeU} to {@code nodeV}. This is
226 * equivalent to {@code nodes().contains(nodeU) && successors(nodeU).contains(nodeV)}.
227 *
228 * <p>In an undirected graph, this is equal to {@code hasEdgeConnecting(nodeV, nodeU)}.
229 *
230 * @since 23.0
231 */
232 @Override
233 boolean hasEdgeConnecting(N nodeU, N nodeV);
234
235 //
236 // Graph identity
237 //
238
239 /**
240 * Returns {@code true} iff {@code object} is a {@link Graph} that has the same elements and the
241 * same structural relationships as those in this graph.
242 *
243 * <p>Thus, two graphs A and B are equal if <b>all</b> of the following are true:
244 *
245 * <ul>
246 * <li>A and B have equal {@link #isDirected() directedness}.
247 * <li>A and B have equal {@link #nodes() node sets}.
248 * <li>A and B have equal {@link #edges() edge sets}.
249 * </ul>
250 *
251 * <p>Graph properties besides {@link #isDirected() directedness} do <b>not</b> affect equality.
252 * For example, two graphs may be considered equal even if one allows self-loops and the other
253 * doesn't. Additionally, the order in which nodes or edges are added to the graph, and the order
254 * in which they are iterated over, are irrelevant.
255 *
256 * <p>A reference implementation of this is provided by {@link AbstractGraph#equals(Object)}.
257 */
258 @Override
259 boolean equals(@NullableDecl Object object);
260
261 /**
262 * Returns the hash code for this graph. The hash code of a graph is defined as the hash code of
263 * the set returned by {@link #edges()}.
264 *
265 * <p>A reference implementation of this is provided by {@link AbstractGraph#hashCode()}.
266 */
267 @Override
268 int hashCode();
269 }