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.base.Preconditions.checkState;
22 import static com.google.common.graph.GraphConstants.INNER_CAPACITY;
23 import static com.google.common.graph.GraphConstants.INNER_LOAD_FACTOR;
24 import static com.google.common.graph.Graphs.checkNonNegative;
25 import static com.google.common.graph.Graphs.checkPositive;
26
27 import com.google.common.base.Function;
28 import com.google.common.collect.AbstractIterator;
29 import com.google.common.collect.ImmutableList;
30 import com.google.common.collect.Iterators;
31 import com.google.common.collect.UnmodifiableIterator;
32 import java.util.AbstractSet;
33 import java.util.ArrayList;
34 import java.util.Collections;
35 import java.util.HashMap;
36 import java.util.HashSet;
37 import java.util.Iterator;
38 import java.util.List;
39 import java.util.Map;
40 import java.util.Map.Entry;
41 import java.util.Set;
42 import java.util.concurrent.atomic.AtomicBoolean;
43 import javax.annotation.CheckForNull;
44
45 /**
46 * An implementation of {@link GraphConnections} for directed graphs.
47 *
48 * @author James Sexton
49 * @author Jens Nyman
50 * @param <N> Node parameter type
51 * @param <V> Value parameter type
52 */
53 @ElementTypesAreNonnullByDefault
54 final class DirectedGraphConnections<N, V> implements GraphConnections<N, V> {
55 /**
56 * A wrapper class to indicate a node is both a predecessor and successor while still providing
57 * the successor value.
58 */
59 private static final class PredAndSucc {
60 private final Object successorValue;
61
62 PredAndSucc(Object successorValue) {
63 this.successorValue = successorValue;
64 }
65 }
66
67 /**
68 * A value class representing single connection between the origin node and another node.
69 *
70 * <p>There can be two types of connections (predecessor and successor), which is represented by
71 * the two implementations.
72 */
73 private abstract static class NodeConnection<N> {
74 final N node;
75
76 NodeConnection(N node) {
77 this.node = checkNotNull(node);
78 }
79
80 static final class Pred<N> extends NodeConnection<N> {
81 Pred(N node) {
82 super(node);
83 }
84
85 @Override
86 public boolean equals(@CheckForNull Object that) {
87 if (that instanceof Pred) {
88 return this.node.equals(((Pred<?>) that).node);
89 } else {
90 return false;
91 }
92 }
93
94 @Override
95 public int hashCode() {
96 // Adding the class hashCode to avoid a clash with Succ instances.
97 return Pred.class.hashCode() + node.hashCode();
98 }
99 }
100
101 static final class Succ<N> extends NodeConnection<N> {
102 Succ(N node) {
103 super(node);
104 }
105
106 @Override
107 public boolean equals(@CheckForNull Object that) {
108 if (that instanceof Succ) {
109 return this.node.equals(((Succ<?>) that).node);
110 } else {
111 return false;
112 }
113 }
114
115 @Override
116 public int hashCode() {
117 // Adding the class hashCode to avoid a clash with Pred instances.
118 return Succ.class.hashCode() + node.hashCode();
119 }
120 }
121 }
122
123 private static final Object PRED = new Object();
124
125 // Every value in this map must either be an instance of PredAndSucc with a successorValue of
126 // type V, PRED (representing predecessor), or an instance of type V (representing successor).
127 private final Map<N, Object> adjacentNodeValues;
128
129 /**
130 * All node connections in this graph, in edge insertion order.
131 *
132 * <p>Note: This field and {@link #adjacentNodeValues} cannot be combined into a single
133 * LinkedHashMap because one target node may be mapped to both a predecessor and a successor. A
134 * LinkedHashMap combines two such edges into a single node-value pair, even though the edges may
135 * not have been inserted consecutively.
136 */
137 @CheckForNull private final List<NodeConnection<N>> orderedNodeConnections;
138
139 private int predecessorCount;
140 private int successorCount;
141
142 private DirectedGraphConnections(
143 Map<N, Object> adjacentNodeValues,
144 @CheckForNull List<NodeConnection<N>> orderedNodeConnections,
145 int predecessorCount,
146 int successorCount) {
147 this.adjacentNodeValues = checkNotNull(adjacentNodeValues);
148 this.orderedNodeConnections = orderedNodeConnections;
149 this.predecessorCount = checkNonNegative(predecessorCount);
150 this.successorCount = checkNonNegative(successorCount);
151 checkState(
152 predecessorCount <= adjacentNodeValues.size()
153 && successorCount <= adjacentNodeValues.size());
154 }
155
156 static <N, V> DirectedGraphConnections<N, V> of(ElementOrder<N> incidentEdgeOrder) {
157 // We store predecessors and successors in the same map, so double the initial capacity.
158 int initialCapacity = INNER_CAPACITY * 2;
159
160 List<NodeConnection<N>> orderedNodeConnections;
161 switch (incidentEdgeOrder.type()) {
162 case UNORDERED:
163 orderedNodeConnections = null;
164 break;
165 case STABLE:
166 orderedNodeConnections = new ArrayList<NodeConnection<N>>();
167 break;
168 default:
169 throw new AssertionError(incidentEdgeOrder.type());
170 }
171
172 return new DirectedGraphConnections<N, V>(
173 /* adjacentNodeValues = */ new HashMap<N, Object>(initialCapacity, INNER_LOAD_FACTOR),
174 orderedNodeConnections,
175 /* predecessorCount = */ 0,
176 /* successorCount = */ 0);
177 }
178
179 static <N, V> DirectedGraphConnections<N, V> ofImmutable(
180 N thisNode, Iterable<EndpointPair<N>> incidentEdges, Function<N, V> successorNodeToValueFn) {
181 checkNotNull(thisNode);
182 checkNotNull(successorNodeToValueFn);
183
184 Map<N, Object> adjacentNodeValues = new HashMap<>();
185 ImmutableList.Builder<NodeConnection<N>> orderedNodeConnectionsBuilder =
186 ImmutableList.builder();
187 int predecessorCount = 0;
188 int successorCount = 0;
189
190 for (EndpointPair<N> incidentEdge : incidentEdges) {
191 if (incidentEdge.nodeU().equals(thisNode) && incidentEdge.nodeV().equals(thisNode)) {
192 // incidentEdge is a self-loop
193
194 adjacentNodeValues.put(thisNode, new PredAndSucc(successorNodeToValueFn.apply(thisNode)));
195
196 orderedNodeConnectionsBuilder.add(new NodeConnection.Pred<>(thisNode));
197 orderedNodeConnectionsBuilder.add(new NodeConnection.Succ<>(thisNode));
198 predecessorCount++;
199 successorCount++;
200 } else if (incidentEdge.nodeV().equals(thisNode)) { // incidentEdge is an inEdge
201 N predecessor = incidentEdge.nodeU();
202
203 Object existingValue = adjacentNodeValues.put(predecessor, PRED);
204 if (existingValue != null) {
205 adjacentNodeValues.put(predecessor, new PredAndSucc(existingValue));
206 }
207
208 orderedNodeConnectionsBuilder.add(new NodeConnection.Pred<>(predecessor));
209 predecessorCount++;
210 } else { // incidentEdge is an outEdge
211 checkArgument(incidentEdge.nodeU().equals(thisNode));
212
213 N successor = incidentEdge.nodeV();
214 V value = successorNodeToValueFn.apply(successor);
215
216 Object existingValue = adjacentNodeValues.put(successor, value);
217 if (existingValue != null) {
218 checkArgument(existingValue == PRED);
219 adjacentNodeValues.put(successor, new PredAndSucc(value));
220 }
221
222 orderedNodeConnectionsBuilder.add(new NodeConnection.Succ<>(successor));
223 successorCount++;
224 }
225 }
226
227 return new DirectedGraphConnections<>(
228 adjacentNodeValues,
229 orderedNodeConnectionsBuilder.build(),
230 predecessorCount,
231 successorCount);
232 }
233
234 @Override
235 public Set<N> adjacentNodes() {
236 if (orderedNodeConnections == null) {
237 return Collections.unmodifiableSet(adjacentNodeValues.keySet());
238 } else {
239 return new AbstractSet<N>() {
240 @Override
241 public UnmodifiableIterator<N> iterator() {
242 final Iterator<NodeConnection<N>> nodeConnections = orderedNodeConnections.iterator();
243 final Set<N> seenNodes = new HashSet<>();
244 return new AbstractIterator<N>() {
245 @Override
246 protected N computeNext() {
247 while (nodeConnections.hasNext()) {
248 NodeConnection<N> nodeConnection = nodeConnections.next();
249 boolean added = seenNodes.add(nodeConnection.node);
250 if (added) {
251 return nodeConnection.node;
252 }
253 }
254 return endOfData();
255 }
256 };
257 }
258
259 @Override
260 public int size() {
261 return adjacentNodeValues.size();
262 }
263
264 @Override
265 public boolean contains(@CheckForNull Object obj) {
266 return adjacentNodeValues.containsKey(obj);
267 }
268 };
269 }
270 }
271
272 @Override
273 public Set<N> predecessors() {
274 return new AbstractSet<N>() {
275 @Override
276 public UnmodifiableIterator<N> iterator() {
277 if (orderedNodeConnections == null) {
278 final Iterator<Entry<N, Object>> entries = adjacentNodeValues.entrySet().iterator();
279 return new AbstractIterator<N>() {
280 @Override
281 protected N computeNext() {
282 while (entries.hasNext()) {
283 Entry<N, Object> entry = entries.next();
284 if (isPredecessor(entry.getValue())) {
285 return entry.getKey();
286 }
287 }
288 return endOfData();
289 }
290 };
291 } else {
292 final Iterator<NodeConnection<N>> nodeConnections = orderedNodeConnections.iterator();
293 return new AbstractIterator<N>() {
294 @Override
295 protected N computeNext() {
296 while (nodeConnections.hasNext()) {
297 NodeConnection<N> nodeConnection = nodeConnections.next();
298 if (nodeConnection instanceof NodeConnection.Pred) {
299 return nodeConnection.node;
300 }
301 }
302 return endOfData();
303 }
304 };
305 }
306 }
307
308 @Override
309 public int size() {
310 return predecessorCount;
311 }
312
313 @Override
314 public boolean contains(@CheckForNull Object obj) {
315 return isPredecessor(adjacentNodeValues.get(obj));
316 }
317 };
318 }
319
320 @Override
321 public Set<N> successors() {
322 return new AbstractSet<N>() {
323 @Override
324 public UnmodifiableIterator<N> iterator() {
325 if (orderedNodeConnections == null) {
326 final Iterator<Entry<N, Object>> entries = adjacentNodeValues.entrySet().iterator();
327 return new AbstractIterator<N>() {
328 @Override
329 protected N computeNext() {
330 while (entries.hasNext()) {
331 Entry<N, Object> entry = entries.next();
332 if (isSuccessor(entry.getValue())) {
333 return entry.getKey();
334 }
335 }
336 return endOfData();
337 }
338 };
339 } else {
340 final Iterator<NodeConnection<N>> nodeConnections = orderedNodeConnections.iterator();
341 return new AbstractIterator<N>() {
342 @Override
343 protected N computeNext() {
344 while (nodeConnections.hasNext()) {
345 NodeConnection<N> nodeConnection = nodeConnections.next();
346 if (nodeConnection instanceof NodeConnection.Succ) {
347 return nodeConnection.node;
348 }
349 }
350 return endOfData();
351 }
352 };
353 }
354 }
355
356 @Override
357 public int size() {
358 return successorCount;
359 }
360
361 @Override
362 public boolean contains(@CheckForNull Object obj) {
363 return isSuccessor(adjacentNodeValues.get(obj));
364 }
365 };
366 }
367
368 @Override
369 public Iterator<EndpointPair<N>> incidentEdgeIterator(final N thisNode) {
370 checkNotNull(thisNode);
371
372 final Iterator<EndpointPair<N>> resultWithDoubleSelfLoop;
373 if (orderedNodeConnections == null) {
374 resultWithDoubleSelfLoop =
375 Iterators.concat(
376 Iterators.transform(
377 predecessors().iterator(),
378 new Function<N, EndpointPair<N>>() {
379 @Override
380 public EndpointPair<N> apply(N predecessor) {
381 return EndpointPair.ordered(predecessor, thisNode);
382 }
383 }),
384 Iterators.transform(
385 successors().iterator(),
386 new Function<N, EndpointPair<N>>() {
387 @Override
388 public EndpointPair<N> apply(N successor) {
389 return EndpointPair.ordered(thisNode, successor);
390 }
391 }));
392 } else {
393 resultWithDoubleSelfLoop =
394 Iterators.transform(
395 orderedNodeConnections.iterator(),
396 new Function<NodeConnection<N>, EndpointPair<N>>() {
397 @Override
398 public EndpointPair<N> apply(NodeConnection<N> connection) {
399 if (connection instanceof NodeConnection.Succ) {
400 return EndpointPair.ordered(thisNode, connection.node);
401 } else {
402 return EndpointPair.ordered(connection.node, thisNode);
403 }
404 }
405 });
406 }
407
408 final AtomicBoolean alreadySeenSelfLoop = new AtomicBoolean(false);
409 return new AbstractIterator<EndpointPair<N>>() {
410 @Override
411 protected EndpointPair<N> computeNext() {
412 while (resultWithDoubleSelfLoop.hasNext()) {
413 EndpointPair<N> edge = resultWithDoubleSelfLoop.next();
414 if (edge.nodeU().equals(edge.nodeV())) {
415 if (!alreadySeenSelfLoop.getAndSet(true)) {
416 return edge;
417 }
418 } else {
419 return edge;
420 }
421 }
422 return endOfData();
423 }
424 };
425 }
426
427 @SuppressWarnings("unchecked")
428 @Override
429 @CheckForNull
430 public V value(N node) {
431 checkNotNull(node);
432 Object value = adjacentNodeValues.get(node);
433 if (value == PRED) {
434 return null;
435 }
436 if (value instanceof PredAndSucc) {
437 return (V) ((PredAndSucc) value).successorValue;
438 }
439 return (V) value;
440 }
441
442 @SuppressWarnings("unchecked")
443 @Override
444 public void removePredecessor(N node) {
445 checkNotNull(node);
446
447 Object previousValue = adjacentNodeValues.get(node);
448 boolean removedPredecessor;
449
450 if (previousValue == PRED) {
451 adjacentNodeValues.remove(node);
452 removedPredecessor = true;
453 } else if (previousValue instanceof PredAndSucc) {
454 adjacentNodeValues.put((N) node, ((PredAndSucc) previousValue).successorValue);
455 removedPredecessor = true;
456 } else {
457 removedPredecessor = false;
458 }
459
460 if (removedPredecessor) {
461 checkNonNegative(--predecessorCount);
462
463 if (orderedNodeConnections != null) {
464 orderedNodeConnections.remove(new NodeConnection.Pred<>(node));
465 }
466 }
467 }
468
469 @SuppressWarnings("unchecked")
470 @Override
471 @CheckForNull
472 public V removeSuccessor(Object node) {
473 checkNotNull(node);
474 Object previousValue = adjacentNodeValues.get(node);
475 Object removedValue;
476
477 if (previousValue == null || previousValue == PRED) {
478 removedValue = null;
479 } else if (previousValue instanceof PredAndSucc) {
480 adjacentNodeValues.put((N) node, PRED);
481 removedValue = ((PredAndSucc) previousValue).successorValue;
482 } else { // successor
483 adjacentNodeValues.remove(node);
484 removedValue = previousValue;
485 }
486
487 if (removedValue != null) {
488 checkNonNegative(--successorCount);
489
490 if (orderedNodeConnections != null) {
491 orderedNodeConnections.remove(new NodeConnection.Succ<>((N) node));
492 }
493 }
494
495 /*
496 * TODO(cpovirk): `return (V) removedValue` once our checker permits that.
497 *
498 * (We promoted a class of warnings into errors because sometimes they indicate real problems.
499 * But now we need to "undo" some instance of spurious errors, as discussed in
500 * https://github.com/jspecify/checker-framework/issues/8.)
501 */
502 return removedValue == null ? null : (V) removedValue;
503 }
504
505 @Override
506 public void addPredecessor(N node, V unused) {
507 Object previousValue = adjacentNodeValues.put(node, PRED);
508 boolean addedPredecessor;
509
510 if (previousValue == null) {
511 addedPredecessor = true;
512 } else if (previousValue instanceof PredAndSucc) {
513 // Restore previous PredAndSucc object.
514 adjacentNodeValues.put(node, previousValue);
515 addedPredecessor = false;
516 } else if (previousValue != PRED) { // successor
517 // Do NOT use method parameter value 'unused'. In directed graphs, successors store the value.
518 adjacentNodeValues.put(node, new PredAndSucc(previousValue));
519 addedPredecessor = true;
520 } else {
521 addedPredecessor = false;
522 }
523
524 if (addedPredecessor) {
525 checkPositive(++predecessorCount);
526
527 if (orderedNodeConnections != null) {
528 orderedNodeConnections.add(new NodeConnection.Pred<>(node));
529 }
530 }
531 }
532
533 @SuppressWarnings("unchecked")
534 @Override
535 @CheckForNull
536 public V addSuccessor(N node, V value) {
537 Object previousValue = adjacentNodeValues.put(node, value);
538 Object previousSuccessor;
539
540 if (previousValue == null) {
541 previousSuccessor = null;
542 } else if (previousValue instanceof PredAndSucc) {
543 adjacentNodeValues.put(node, new PredAndSucc(value));
544 previousSuccessor = ((PredAndSucc) previousValue).successorValue;
545 } else if (previousValue == PRED) {
546 adjacentNodeValues.put(node, new PredAndSucc(value));
547 previousSuccessor = null;
548 } else { // successor
549 previousSuccessor = previousValue;
550 }
551
552 if (previousSuccessor == null) {
553 checkPositive(++successorCount);
554
555 if (orderedNodeConnections != null) {
556 orderedNodeConnections.add(new NodeConnection.Succ<>(node));
557 }
558 }
559
560 // See the comment on the similar cast in removeSuccessor.
561 return previousSuccessor == null ? null : (V) previousSuccessor;
562 }
563
564 private static boolean isPredecessor(@CheckForNull Object value) {
565 return (value == PRED) || (value instanceof PredAndSucc);
566 }
567
568 private static boolean isSuccessor(@CheckForNull Object value) {
569 return (value != PRED) && (value != null);
570 }
571 }