1 /*
2 * Copyright (C) 2016 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 static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static com.google.common.graph.GraphConstants.ENDPOINTS_MISMATCH;
22 import static com.google.common.graph.GraphConstants.MULTIPLE_EDGES_CONNECTING;
23 import static java.util.Collections.unmodifiableSet;
24
25 import com.google.common.annotations.Beta;
26 import com.google.common.base.Function;
27 import com.google.common.base.Predicate;
28 import com.google.common.collect.ImmutableSet;
29 import com.google.common.collect.Iterators;
30 import com.google.common.collect.Maps;
31 import com.google.common.collect.Sets;
32 import com.google.common.math.IntMath;
33 import java.util.AbstractSet;
34 import java.util.Iterator;
35 import java.util.Map;
36 import java.util.Optional;
37 import java.util.Set;
38 import javax.annotation.CheckForNull;
39
40 /**
41 * This class provides a skeletal implementation of {@link Network}. It is recommended to extend
42 * this class rather than implement {@link Network} directly.
43 *
44 * <p>The methods implemented in this class should not be overridden unless the subclass admits a
45 * more efficient implementation.
46 *
47 * @author James Sexton
48 * @param <N> Node parameter type
49 * @param <E> Edge parameter type
50 * @since 20.0
51 */
52 @Beta
53 @ElementTypesAreNonnullByDefault
54 public abstract class AbstractNetwork<N, E> implements Network<N, E> {
55
56 @Override
57 public Graph<N> asGraph() {
58 return new AbstractGraph<N>() {
59 @Override
60 public Set<N> nodes() {
61 return AbstractNetwork.this.nodes();
62 }
63
64 @Override
65 public Set<EndpointPair<N>> edges() {
66 if (allowsParallelEdges()) {
67 return super.edges(); // Defer to AbstractGraph implementation.
68 }
69
70 // Optimized implementation assumes no parallel edges (1:1 edge to EndpointPair mapping).
71 return new AbstractSet<EndpointPair<N>>() {
72 @Override
73 public Iterator<EndpointPair<N>> iterator() {
74 return Iterators.transform(
75 AbstractNetwork.this.edges().iterator(),
76 new Function<E, EndpointPair<N>>() {
77 @Override
78 public EndpointPair<N> apply(E edge) {
79 return incidentNodes(edge);
80 }
81 });
82 }
83
84 @Override
85 public int size() {
86 return AbstractNetwork.this.edges().size();
87 }
88
89 // Mostly safe: We check contains(u) before calling successors(u), so we perform unsafe
90 // operations only in weird cases like checking for an EndpointPair<ArrayList> in a
91 // Network<LinkedList>.
92 @SuppressWarnings("unchecked")
93 @Override
94 public boolean contains(@CheckForNull Object obj) {
95 if (!(obj instanceof EndpointPair)) {
96 return false;
97 }
98 EndpointPair<?> endpointPair = (EndpointPair<?>) obj;
99 return isOrderingCompatible(endpointPair)
100 && nodes().contains(endpointPair.nodeU())
101 && successors((N) endpointPair.nodeU()).contains(endpointPair.nodeV());
102 }
103 };
104 }
105
106 @Override
107 public ElementOrder<N> nodeOrder() {
108 return AbstractNetwork.this.nodeOrder();
109 }
110
111 @Override
112 public ElementOrder<N> incidentEdgeOrder() {
113 // TODO(b/142723300): Return AbstractNetwork.this.incidentEdgeOrder() once Network has that
114 // method.
115 return ElementOrder.unordered();
116 }
117
118 @Override
119 public boolean isDirected() {
120 return AbstractNetwork.this.isDirected();
121 }
122
123 @Override
124 public boolean allowsSelfLoops() {
125 return AbstractNetwork.this.allowsSelfLoops();
126 }
127
128 @Override
129 public Set<N> adjacentNodes(N node) {
130 return AbstractNetwork.this.adjacentNodes(node);
131 }
132
133 @Override
134 public Set<N> predecessors(N node) {
135 return AbstractNetwork.this.predecessors(node);
136 }
137
138 @Override
139 public Set<N> successors(N node) {
140 return AbstractNetwork.this.successors(node);
141 }
142
143 // DO NOT override the AbstractGraph *degree() implementations.
144 };
145 }
146
147 @Override
148 public int degree(N node) {
149 if (isDirected()) {
150 return IntMath.saturatedAdd(inEdges(node).size(), outEdges(node).size());
151 } else {
152 return IntMath.saturatedAdd(incidentEdges(node).size(), edgesConnecting(node, node).size());
153 }
154 }
155
156 @Override
157 public int inDegree(N node) {
158 return isDirected() ? inEdges(node).size() : degree(node);
159 }
160
161 @Override
162 public int outDegree(N node) {
163 return isDirected() ? outEdges(node).size() : degree(node);
164 }
165
166 @Override
167 public Set<E> adjacentEdges(E edge) {
168 EndpointPair<N> endpointPair = incidentNodes(edge); // Verifies that edge is in this network.
169 Set<E> endpointPairIncidentEdges =
170 Sets.union(incidentEdges(endpointPair.nodeU()), incidentEdges(endpointPair.nodeV()));
171 return Sets.difference(endpointPairIncidentEdges, ImmutableSet.of(edge));
172 }
173
174 @Override
175 public Set<E> edgesConnecting(N nodeU, N nodeV) {
176 Set<E> outEdgesU = outEdges(nodeU);
177 Set<E> inEdgesV = inEdges(nodeV);
178 return outEdgesU.size() <= inEdgesV.size()
179 ? unmodifiableSet(Sets.filter(outEdgesU, connectedPredicate(nodeU, nodeV)))
180 : unmodifiableSet(Sets.filter(inEdgesV, connectedPredicate(nodeV, nodeU)));
181 }
182
183 @Override
184 public Set<E> edgesConnecting(EndpointPair<N> endpoints) {
185 validateEndpoints(endpoints);
186 return edgesConnecting(endpoints.nodeU(), endpoints.nodeV());
187 }
188
189 private Predicate<E> connectedPredicate(final N nodePresent, final N nodeToCheck) {
190 return new Predicate<E>() {
191 @Override
192 public boolean apply(E edge) {
193 return incidentNodes(edge).adjacentNode(nodePresent).equals(nodeToCheck);
194 }
195 };
196 }
197
198 @Override
199 public Optional<E> edgeConnecting(N nodeU, N nodeV) {
200 return Optional.ofNullable(edgeConnectingOrNull(nodeU, nodeV));
201 }
202
203 @Override
204 public Optional<E> edgeConnecting(EndpointPair<N> endpoints) {
205 validateEndpoints(endpoints);
206 return edgeConnecting(endpoints.nodeU(), endpoints.nodeV());
207 }
208
209 @Override
210 @CheckForNull
211 public E edgeConnectingOrNull(N nodeU, N nodeV) {
212 Set<E> edgesConnecting = edgesConnecting(nodeU, nodeV);
213 switch (edgesConnecting.size()) {
214 case 0:
215 return null;
216 case 1:
217 return edgesConnecting.iterator().next();
218 default:
219 throw new IllegalArgumentException(String.format(MULTIPLE_EDGES_CONNECTING, nodeU, nodeV));
220 }
221 }
222
223 @Override
224 @CheckForNull
225 public E edgeConnectingOrNull(EndpointPair<N> endpoints) {
226 validateEndpoints(endpoints);
227 return edgeConnectingOrNull(endpoints.nodeU(), endpoints.nodeV());
228 }
229
230 @Override
231 public boolean hasEdgeConnecting(N nodeU, N nodeV) {
232 checkNotNull(nodeU);
233 checkNotNull(nodeV);
234 return nodes().contains(nodeU) && successors(nodeU).contains(nodeV);
235 }
236
237 @Override
238 public boolean hasEdgeConnecting(EndpointPair<N> endpoints) {
239 checkNotNull(endpoints);
240 if (!isOrderingCompatible(endpoints)) {
241 return false;
242 }
243 return hasEdgeConnecting(endpoints.nodeU(), endpoints.nodeV());
244 }
245
246 /**
247 * Throws an IllegalArgumentException if the ordering of {@code endpoints} is not compatible with
248 * the directionality of this graph.
249 */
250 protected final void validateEndpoints(EndpointPair<?> endpoints) {
251 checkNotNull(endpoints);
252 checkArgument(isOrderingCompatible(endpoints), ENDPOINTS_MISMATCH);
253 }
254
255 protected final boolean isOrderingCompatible(EndpointPair<?> endpoints) {
256 return endpoints.isOrdered() || !this.isDirected();
257 }
258
259 @Override
260 public final boolean equals(@CheckForNull Object obj) {
261 if (obj == this) {
262 return true;
263 }
264 if (!(obj instanceof Network)) {
265 return false;
266 }
267 Network<?, ?> other = (Network<?, ?>) obj;
268
269 return isDirected() == other.isDirected()
270 && nodes().equals(other.nodes())
271 && edgeIncidentNodesMap(this).equals(edgeIncidentNodesMap(other));
272 }
273
274 @Override
275 public final int hashCode() {
276 return edgeIncidentNodesMap(this).hashCode();
277 }
278
279 /** Returns a string representation of this network. */
280 @Override
281 public String toString() {
282 return "isDirected: "
283 + isDirected()
284 + ", allowsParallelEdges: "
285 + allowsParallelEdges()
286 + ", allowsSelfLoops: "
287 + allowsSelfLoops()
288 + ", nodes: "
289 + nodes()
290 + ", edges: "
291 + edgeIncidentNodesMap(this);
292 }
293
294 private static <N, E> Map<E, EndpointPair<N>> edgeIncidentNodesMap(final Network<N, E> network) {
295 Function<E, EndpointPair<N>> edgeToIncidentNodesFn =
296 new Function<E, EndpointPair<N>>() {
297 @Override
298 public EndpointPair<N> apply(E edge) {
299 return network.incidentNodes(edge);
300 }
301 };
302 return Maps.asMap(network.edges(), edgeToIncidentNodesFn);
303 }
304 }