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.checkState;
20 import static java.util.Objects.requireNonNull;
21
22 import com.google.common.collect.AbstractIterator;
23 import com.google.common.collect.ImmutableSet;
24 import com.google.common.collect.Sets;
25 import java.util.Iterator;
26 import java.util.Set;
27 import javax.annotation.CheckForNull;
28 import org.checkerframework.checker.nullness.qual.Nullable;
29
30 /**
31 * A class to facilitate the set returned by {@link Graph#edges()}.
32 *
33 * @author James Sexton
34 */
35 @ElementTypesAreNonnullByDefault
36 abstract class EndpointPairIterator<N> extends AbstractIterator<EndpointPair<N>> {
37 private final BaseGraph<N> graph;
38 private final Iterator<N> nodeIterator;
39
40 @CheckForNull
41 N node = null; // null is safe as an initial value because graphs don't allow null nodes
42
43 Iterator<N> successorIterator = ImmutableSet.<N>of().iterator();
44
45 static <N> EndpointPairIterator<N> of(BaseGraph<N> graph) {
46 return graph.isDirected() ? new Directed<N>(graph) : new Undirected<N>(graph);
47 }
48
49 private EndpointPairIterator(BaseGraph<N> graph) {
50 this.graph = graph;
51 this.nodeIterator = graph.nodes().iterator();
52 }
53
54 /**
55 * Called after {@link #successorIterator} is exhausted. Advances {@link #node} to the next node
56 * and updates {@link #successorIterator} to iterate through the successors of {@link #node}.
57 */
58 final boolean advance() {
59 checkState(!successorIterator.hasNext());
60 if (!nodeIterator.hasNext()) {
61 return false;
62 }
63 node = nodeIterator.next();
64 successorIterator = graph.successors(node).iterator();
65 return true;
66 }
67
68 /**
69 * If the graph is directed, each ordered [source, target] pair will be visited once if there is
70 * an edge connecting them.
71 */
72 private static final class Directed<N> extends EndpointPairIterator<N> {
73 private Directed(BaseGraph<N> graph) {
74 super(graph);
75 }
76
77 @Override
78 protected EndpointPair<N> computeNext() {
79 while (true) {
80 if (successorIterator.hasNext()) {
81 // requireNonNull is safe because successorIterator is empty until we set this.node.
82 return EndpointPair.ordered(requireNonNull(node), successorIterator.next());
83 }
84 if (!advance()) {
85 return endOfData();
86 }
87 }
88 }
89 }
90
91 /**
92 * If the graph is undirected, each unordered [node, otherNode] pair (except self-loops) will be
93 * visited twice if there is an edge connecting them. To avoid returning duplicate {@link
94 * EndpointPair}s, we keep track of the nodes that we have visited. When processing endpoint
95 * pairs, we skip if the "other node" is in the visited set, as shown below:
96 *
97 * <pre>
98 * Nodes = {N1, N2, N3, N4}
99 * N2 __
100 * / \ | |
101 * N1----N3 N4__|
102 *
103 * Visited Nodes = {}
104 * EndpointPair [N1, N2] - return
105 * EndpointPair [N1, N3] - return
106 * Visited Nodes = {N1}
107 * EndpointPair [N2, N1] - skip
108 * EndpointPair [N2, N3] - return
109 * Visited Nodes = {N1, N2}
110 * EndpointPair [N3, N1] - skip
111 * EndpointPair [N3, N2] - skip
112 * Visited Nodes = {N1, N2, N3}
113 * EndpointPair [N4, N4] - return
114 * Visited Nodes = {N1, N2, N3, N4}
115 * </pre>
116 */
117 private static final class Undirected<N> extends EndpointPairIterator<N> {
118 // It's a little weird that we add `null` to this set, but it makes for slightly simpler code.
119 @CheckForNull private Set<@Nullable N> visitedNodes;
120
121 private Undirected(BaseGraph<N> graph) {
122 super(graph);
123 this.visitedNodes = Sets.newHashSetWithExpectedSize(graph.nodes().size() + 1);
124 }
125
126 @Override
127 protected EndpointPair<N> computeNext() {
128 while (true) {
129 /*
130 * requireNonNull is safe because visitedNodes isn't cleared until this method calls
131 * endOfData() (after which this method is never called again).
132 */
133 requireNonNull(visitedNodes);
134 while (successorIterator.hasNext()) {
135 N otherNode = successorIterator.next();
136 if (!visitedNodes.contains(otherNode)) {
137 // requireNonNull is safe because successorIterator is empty until we set node.
138 return EndpointPair.unordered(requireNonNull(node), otherNode);
139 }
140 }
141 // Add to visited set *after* processing neighbors so we still include self-loops.
142 visitedNodes.add(node);
143 if (!advance()) {
144 visitedNodes = null;
145 return endOfData();
146 }
147 }
148 }
149 }
150 }