View Javadoc
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.Optional;
21  import java.util.Set;
22  import javax.annotation.Nullable;
23  
24  /**
25   * An interface for <a
26   * href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)">graph</a>-structured data,
27   * whose edges are unique objects.
28   *
29   * <p>A graph is composed of a set of nodes and a set of edges connecting pairs of nodes.
30   *
31   * <p>There are three primary interfaces provided to represent graphs. In order of increasing
32   * complexity they are: {@link Graph}, {@link ValueGraph}, and {@link Network}. You should generally
33   * prefer the simplest interface that satisfies your use case. See the <a
34   * href="https://github.com/google/guava/wiki/GraphsExplained#choosing-the-right-graph-type">
35   * "Choosing the right graph type"</a> section of the Guava User Guide for more details.
36   *
37   * <h3>Capabilities</h3>
38   *
39   * <p>{@code Network} supports the following use cases (<a
40   * href="https://github.com/google/guava/wiki/GraphsExplained#definitions">definitions of
41   * terms</a>):
42   *
43   * <ul>
44   *   <li>directed graphs
45   *   <li>undirected graphs
46   *   <li>graphs that do/don't allow parallel edges
47   *   <li>graphs that do/don't allow self-loops
48   *   <li>graphs whose nodes/edges are insertion-ordered, sorted, or unordered
49   *   <li>graphs whose edges are unique objects
50   * </ul>
51   *
52   * <h3>Building a {@code Network}</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 Network}, use the
56   * {@link NetworkBuilder} class:
57   *
58   * <pre>{@code
59   * MutableNetwork<Integer, MyEdge> graph = NetworkBuilder.directed().build();
60   * }</pre>
61   *
62   * <p>{@link NetworkBuilder#build()} returns an instance of {@link MutableNetwork}, which is a
63   * subtype of {@code Network} that provides methods for adding and removing nodes and edges. If you
64   * do not need to mutate a graph (e.g. if you write a method than runs a read-only algorithm on the
65   * graph), you should use the non-mutating {@link Network} interface, or an {@link
66   * ImmutableNetwork}.
67   *
68   * <p>You can create an immutable copy of an existing {@code Network} using {@link
69   * ImmutableNetwork#copyOf(Network)}:
70   *
71   * <pre>{@code
72   * ImmutableNetwork<Integer, MyEdge> immutableGraph = ImmutableNetwork.copyOf(graph);
73   * }</pre>
74   *
75   * <p>Instances of {@link ImmutableNetwork} do not implement {@link MutableNetwork} (obviously!) and
76   * are contractually guaranteed to be unmodifiable and thread-safe.
77   *
78   * <p>The Guava User Guide has <a
79   * href="https://github.com/google/guava/wiki/GraphsExplained#building-graph-instances">more
80   * information on (and examples of) building graphs</a>.
81   *
82   * <h3>Additional documentation</h3>
83   *
84   * <p>See the Guava User Guide for the {@code common.graph} package (<a
85   * href="https://github.com/google/guava/wiki/GraphsExplained">"Graphs Explained"</a>) for
86   * additional documentation, including:
87   *
88   * <ul>
89   *   <li><a
90   *       href="https://github.com/google/guava/wiki/GraphsExplained#equals-hashcode-and-graph-equivalence">
91   *       {@code equals()}, {@code hashCode()}, and graph equivalence</a>
92   *   <li><a href="https://github.com/google/guava/wiki/GraphsExplained#synchronization">
93   *       Synchronization policy</a>
94   *   <li><a href="https://github.com/google/guava/wiki/GraphsExplained#notes-for-implementors">Notes
95   *       for implementors</a>
96   * </ul>
97   *
98   * @author James Sexton
99   * @author Joshua O'Madadhain
100  * @param <N> Node parameter type
101  * @param <E> Edge parameter type
102  * @since 20.0
103  */
104 @Beta
105 public interface Network<N, E> extends SuccessorsFunction<N>, PredecessorsFunction<N> {
106   //
107   // Network-level accessors
108   //
109 
110   /** Returns all nodes in this network, in the order specified by {@link #nodeOrder()}. */
111   Set<N> nodes();
112 
113   /** Returns all edges in this network, in the order specified by {@link #edgeOrder()}. */
114   Set<E> edges();
115 
116   /**
117    * Returns a live view of this network as a {@link Graph}. The resulting {@link Graph} will have
118    * an edge connecting node A to node B if this {@link Network} has an edge connecting A to B.
119    *
120    * <p>If this network {@link #allowsParallelEdges() allows parallel edges}, parallel edges will be
121    * treated as if collapsed into a single edge. For example, the {@link #degree(Object)} of a node
122    * in the {@link Graph} view may be less than the degree of the same node in this {@link Network}.
123    */
124   Graph<N> asGraph();
125 
126   //
127   // Network properties
128   //
129 
130   /**
131    * Returns true if the edges in this network are directed. Directed edges connect a {@link
132    * EndpointPair#source() source node} to a {@link EndpointPair#target() target node}, while
133    * undirected edges connect a pair of nodes to each other.
134    */
135   boolean isDirected();
136 
137   /**
138    * Returns true if this network allows parallel edges. Attempting to add a parallel edge to a
139    * network that does not allow them will throw an {@link IllegalArgumentException}.
140    */
141   boolean allowsParallelEdges();
142 
143   /**
144    * Returns true if this network allows self-loops (edges that connect a node to itself).
145    * Attempting to add a self-loop to a network that does not allow them will throw an {@link
146    * IllegalArgumentException}.
147    */
148   boolean allowsSelfLoops();
149 
150   /** Returns the order of iteration for the elements of {@link #nodes()}. */
151   ElementOrder<N> nodeOrder();
152 
153   /** Returns the order of iteration for the elements of {@link #edges()}. */
154   ElementOrder<E> edgeOrder();
155 
156   //
157   // Element-level accessors
158   //
159 
160   /**
161    * Returns the nodes which have an incident edge in common with {@code node} in this network.
162    *
163    * @throws IllegalArgumentException if {@code node} is not an element of this network
164    */
165   Set<N> adjacentNodes(N node);
166 
167   /**
168    * Returns all nodes in this network adjacent to {@code node} which can be reached by traversing
169    * {@code node}'s incoming edges <i>against</i> the direction (if any) of the edge.
170    *
171    * <p>In an undirected network, this is equivalent to {@link #adjacentNodes(Object)}.
172    *
173    * @throws IllegalArgumentException if {@code node} is not an element of this network
174    */
175   @Override
176   Set<N> predecessors(N node);
177 
178   /**
179    * Returns all nodes in this network adjacent to {@code node} which can be reached by traversing
180    * {@code node}'s outgoing edges in the direction (if any) of the edge.
181    *
182    * <p>In an undirected network, this is equivalent to {@link #adjacentNodes(Object)}.
183    *
184    * <p>This is <i>not</i> the same as "all nodes reachable from {@code node} by following outgoing
185    * edges". For that functionality, see {@link Graphs#reachableNodes(Graph, Object)}.
186    *
187    * @throws IllegalArgumentException if {@code node} is not an element of this network
188    */
189   @Override
190   Set<N> successors(N node);
191 
192   /**
193    * Returns the edges whose {@link #incidentNodes(Object) incident nodes} in this network include
194    * {@code node}.
195    *
196    * @throws IllegalArgumentException if {@code node} is not an element of this network
197    */
198   Set<E> incidentEdges(N node);
199 
200   /**
201    * Returns all edges in this network which can be traversed in the direction (if any) of the edge
202    * to end at {@code node}.
203    *
204    * <p>In a directed network, an incoming edge's {@link EndpointPair#target()} equals {@code node}.
205    *
206    * <p>In an undirected network, this is equivalent to {@link #incidentEdges(Object)}.
207    *
208    * @throws IllegalArgumentException if {@code node} is not an element of this network
209    */
210   Set<E> inEdges(N node);
211 
212   /**
213    * Returns all edges in this network which can be traversed in the direction (if any) of the edge
214    * starting from {@code node}.
215    *
216    * <p>In a directed network, an outgoing edge's {@link EndpointPair#source()} equals {@code node}.
217    *
218    * <p>In an undirected network, this is equivalent to {@link #incidentEdges(Object)}.
219    *
220    * @throws IllegalArgumentException if {@code node} is not an element of this network
221    */
222   Set<E> outEdges(N node);
223 
224   /**
225    * Returns the count of {@code node}'s {@link #incidentEdges(Object) incident edges}, counting
226    * self-loops twice (equivalently, the number of times an edge touches {@code node}).
227    *
228    * <p>For directed networks, this is equal to {@code inDegree(node) + outDegree(node)}.
229    *
230    * <p>For undirected networks, this is equal to {@code incidentEdges(node).size()} + (number of
231    * self-loops incident to {@code node}).
232    *
233    * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
234    *
235    * @throws IllegalArgumentException if {@code node} is not an element of this network
236    */
237   int degree(N node);
238 
239   /**
240    * Returns the count of {@code node}'s {@link #inEdges(Object) incoming edges} in a directed
241    * network. In an undirected network, returns the {@link #degree(Object)}.
242    *
243    * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
244    *
245    * @throws IllegalArgumentException if {@code node} is not an element of this network
246    */
247   int inDegree(N node);
248 
249   /**
250    * Returns the count of {@code node}'s {@link #outEdges(Object) outgoing edges} in a directed
251    * network. In an undirected network, returns the {@link #degree(Object)}.
252    *
253    * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
254    *
255    * @throws IllegalArgumentException if {@code node} is not an element of this network
256    */
257   int outDegree(N node);
258 
259   /**
260    * Returns the nodes which are the endpoints of {@code edge} in this network.
261    *
262    * @throws IllegalArgumentException if {@code edge} is not an element of this network
263    */
264   EndpointPair<N> incidentNodes(E edge);
265 
266   /**
267    * Returns the edges which have an {@link #incidentNodes(Object) incident node} in common with
268    * {@code edge}. An edge is not considered adjacent to itself.
269    *
270    * @throws IllegalArgumentException if {@code edge} is not an element of this network
271    */
272   Set<E> adjacentEdges(E edge);
273 
274   /**
275    * Returns the set of edges directly connecting {@code nodeU} to {@code nodeV}.
276    *
277    * <p>In an undirected network, this is equal to {@code edgesConnecting(nodeV, nodeU)}.
278    *
279    * <p>The resulting set of edges will be parallel (i.e. have equal {@link #incidentNodes(Object)}.
280    * If this network does not {@link #allowsParallelEdges() allow parallel edges}, the resulting set
281    * will contain at most one edge (equivalent to {@code edgeConnecting(nodeU, nodeV).asSet()}).
282    *
283    * @throws IllegalArgumentException if {@code nodeU} or {@code nodeV} is not an element of this
284    *     network
285    */
286   Set<E> edgesConnecting(N nodeU, N nodeV);
287 
288   /**
289    * Returns the single edge directly connecting {@code nodeU} to {@code nodeV}, if one is present,
290    * or {@code Optional.empty()} if no such edge exists.
291    *
292    * <p>In an undirected network, this is equal to {@code edgeConnecting(nodeV, nodeU)}.
293    *
294    * @throws IllegalArgumentException if there are multiple parallel edges connecting {@code nodeU}
295    *     to {@code nodeV}
296    * @throws IllegalArgumentException if {@code nodeU} or {@code nodeV} is not an element of this
297    *     network
298    * @since 23.0
299    */
300   Optional<E> edgeConnecting(N nodeU, N nodeV);
301 
302   /**
303    * Returns the single edge directly connecting {@code nodeU} to {@code nodeV}, if one is present,
304    * or {@code null} if no such edge exists.
305    *
306    * <p>In an undirected network, this is equal to {@code edgeConnectingOrNull(nodeV, nodeU)}.
307    *
308    * @throws IllegalArgumentException if there are multiple parallel edges connecting {@code nodeU}
309    *     to {@code nodeV}
310    * @throws IllegalArgumentException if {@code nodeU} or {@code nodeV} is not an element of this
311    *     network
312    * @since 23.0
313    */
314   @Nullable
315   E edgeConnectingOrNull(N nodeU, N nodeV);
316 
317   /**
318    * Returns true if there is an edge directly connecting {@code nodeU} to {@code nodeV}. This is
319    * equivalent to {@code nodes().contains(nodeU) && successors(nodeU).contains(nodeV)},
320    * and to {@code edgeConnectingOrNull(nodeU, nodeV) != null}.
321    *
322    * <p>In an undirected graph, this is equal to {@code hasEdgeConnecting(nodeV, nodeU)}.
323    *
324    * @since 23.0
325    */
326   boolean hasEdgeConnecting(N nodeU, N nodeV);
327 
328   //
329   // Network identity
330   //
331 
332   /**
333    * Returns {@code true} iff {@code object} is a {@link Network} that has the same elements and the
334    * same structural relationships as those in this network.
335    *
336    * <p>Thus, two networks A and B are equal if <b>all</b> of the following are true:
337    *
338    * <ul>
339    * <li>A and B have equal {@link #isDirected() directedness}.
340    * <li>A and B have equal {@link #nodes() node sets}.
341    * <li>A and B have equal {@link #edges() edge sets}.
342    * <li>Every edge in A and B connects the same nodes in the same direction (if any).
343    * </ul>
344    *
345    * <p>Network properties besides {@link #isDirected() directedness} do <b>not</b> affect equality.
346    * For example, two networks may be considered equal even if one allows parallel edges and the
347    * other doesn't. Additionally, the order in which nodes or edges are added to the network, and
348    * the order in which they are iterated over, are irrelevant.
349    *
350    * <p>A reference implementation of this is provided by {@link AbstractNetwork#equals(Object)}.
351    */
352   @Override
353   boolean equals(@Nullable Object object);
354 
355   /**
356    * Returns the hash code for this network. The hash code of a network is defined as the hash code
357    * of a map from each of its {@link #edges() edges} to their {@link #incidentNodes(Object)
358    * incident nodes}.
359    *
360    * <p>A reference implementation of this is provided by {@link AbstractNetwork#hashCode()}.
361    */
362   @Override
363   int hashCode();
364 }