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