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 static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static com.google.common.base.Preconditions.checkState;
22 import static com.google.common.graph.GraphConstants.ENDPOINTS_MISMATCH;
23
24 import com.google.common.base.Function;
25 import com.google.common.collect.ImmutableSet;
26 import com.google.common.collect.Iterators;
27 import com.google.common.collect.Sets;
28 import com.google.common.collect.UnmodifiableIterator;
29 import com.google.common.math.IntMath;
30 import com.google.common.primitives.Ints;
31 import java.util.AbstractSet;
32 import java.util.Set;
33 import javax.annotation.CheckForNull;
34
35 /**
36 * This class provides a skeletal implementation of {@link BaseGraph}.
37 *
38 * <p>The methods implemented in this class should not be overridden unless the subclass admits a
39 * more efficient implementation.
40 *
41 * @author James Sexton
42 * @param <N> Node parameter type
43 */
44 @ElementTypesAreNonnullByDefault
45 abstract class AbstractBaseGraph<N> implements BaseGraph<N> {
46
47 /**
48 * Returns the number of edges in this graph; used to calculate the size of {@link #edges()}. This
49 * implementation requires O(|N|) time. Classes extending this one may manually keep track of the
50 * number of edges as the graph is updated, and override this method for better performance.
51 */
52 protected long edgeCount() {
53 long degreeSum = 0L;
54 for (N node : nodes()) {
55 degreeSum += degree(node);
56 }
57 // According to the degree sum formula, this is equal to twice the number of edges.
58 checkState((degreeSum & 1) == 0);
59 return degreeSum >>> 1;
60 }
61
62 /**
63 * An implementation of {@link BaseGraph#edges()} defined in terms of {@link #nodes()} and {@link
64 * #successors(Object)}.
65 */
66 @Override
67 public Set<EndpointPair<N>> edges() {
68 return new AbstractSet<EndpointPair<N>>() {
69 @Override
70 public UnmodifiableIterator<EndpointPair<N>> iterator() {
71 return EndpointPairIterator.of(AbstractBaseGraph.this);
72 }
73
74 @Override
75 public int size() {
76 return Ints.saturatedCast(edgeCount());
77 }
78
79 @Override
80 public boolean remove(@CheckForNull Object o) {
81 throw new UnsupportedOperationException();
82 }
83
84 // Mostly safe: We check contains(u) before calling successors(u), so we perform unsafe
85 // operations only in weird cases like checking for an EndpointPair<ArrayList> in a
86 // Graph<LinkedList>.
87 @SuppressWarnings("unchecked")
88 @Override
89 public boolean contains(@CheckForNull Object obj) {
90 if (!(obj instanceof EndpointPair)) {
91 return false;
92 }
93 EndpointPair<?> endpointPair = (EndpointPair<?>) obj;
94 return isOrderingCompatible(endpointPair)
95 && nodes().contains(endpointPair.nodeU())
96 && successors((N) endpointPair.nodeU()).contains(endpointPair.nodeV());
97 }
98 };
99 }
100
101 @Override
102 public ElementOrder<N> incidentEdgeOrder() {
103 return ElementOrder.unordered();
104 }
105
106 @Override
107 public Set<EndpointPair<N>> incidentEdges(N node) {
108 checkNotNull(node);
109 checkArgument(nodes().contains(node), "Node %s is not an element of this graph.", node);
110 return new IncidentEdgeSet<N>(this, node) {
111 @Override
112 public UnmodifiableIterator<EndpointPair<N>> iterator() {
113 if (graph.isDirected()) {
114 return Iterators.unmodifiableIterator(
115 Iterators.concat(
116 Iterators.transform(
117 graph.predecessors(node).iterator(),
118 new Function<N, EndpointPair<N>>() {
119 @Override
120 public EndpointPair<N> apply(N predecessor) {
121 return EndpointPair.ordered(predecessor, node);
122 }
123 }),
124 Iterators.transform(
125 // filter out 'node' from successors (already covered by predecessors, above)
126 Sets.difference(graph.successors(node), ImmutableSet.of(node)).iterator(),
127 new Function<N, EndpointPair<N>>() {
128 @Override
129 public EndpointPair<N> apply(N successor) {
130 return EndpointPair.ordered(node, successor);
131 }
132 })));
133 } else {
134 return Iterators.unmodifiableIterator(
135 Iterators.transform(
136 graph.adjacentNodes(node).iterator(),
137 new Function<N, EndpointPair<N>>() {
138 @Override
139 public EndpointPair<N> apply(N adjacentNode) {
140 return EndpointPair.unordered(node, adjacentNode);
141 }
142 }));
143 }
144 }
145 };
146 }
147
148 @Override
149 public int degree(N node) {
150 if (isDirected()) {
151 return IntMath.saturatedAdd(predecessors(node).size(), successors(node).size());
152 } else {
153 Set<N> neighbors = adjacentNodes(node);
154 int selfLoopCount = (allowsSelfLoops() && neighbors.contains(node)) ? 1 : 0;
155 return IntMath.saturatedAdd(neighbors.size(), selfLoopCount);
156 }
157 }
158
159 @Override
160 public int inDegree(N node) {
161 return isDirected() ? predecessors(node).size() : degree(node);
162 }
163
164 @Override
165 public int outDegree(N node) {
166 return isDirected() ? successors(node).size() : degree(node);
167 }
168
169 @Override
170 public boolean hasEdgeConnecting(N nodeU, N nodeV) {
171 checkNotNull(nodeU);
172 checkNotNull(nodeV);
173 return nodes().contains(nodeU) && successors(nodeU).contains(nodeV);
174 }
175
176 @Override
177 public boolean hasEdgeConnecting(EndpointPair<N> endpoints) {
178 checkNotNull(endpoints);
179 if (!isOrderingCompatible(endpoints)) {
180 return false;
181 }
182 N nodeU = endpoints.nodeU();
183 N nodeV = endpoints.nodeV();
184 return nodes().contains(nodeU) && successors(nodeU).contains(nodeV);
185 }
186
187 /**
188 * Throws {@code IllegalArgumentException} if the ordering of {@code endpoints} is not compatible
189 * with the directionality of this graph.
190 */
191 protected final void validateEndpoints(EndpointPair<?> endpoints) {
192 checkNotNull(endpoints);
193 checkArgument(isOrderingCompatible(endpoints), ENDPOINTS_MISMATCH);
194 }
195
196 protected final boolean isOrderingCompatible(EndpointPair<?> endpoints) {
197 return endpoints.isOrdered() || !this.isDirected();
198 }
199 }