Source code
package com.google.common.graph;
import static com.google.common.base.Preconditions.checkState;
import static java.util.Objects.requireNonNull;
import com.google.common.collect.AbstractIterator;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Sets;
import java.util.Iterator;
import java.util.Set;
import org.jspecify.annotations.Nullable;
/**
* A class to facilitate the set returned by {@link Graph#edges()}.
*
* @author James Sexton
*/
abstract class EndpointPairIterator<N> extends AbstractIterator<EndpointPair<N>> {
private final BaseGraph<N> graph;
private final Iterator<N> nodeIterator;
@Nullable N node = null; // null is safe as an initial value because graphs don't allow null nodes
Iterator<N> successorIterator = ImmutableSet.<N>of().iterator();
static <N> EndpointPairIterator<N> of(BaseGraph<N> graph) {
return graph.isDirected() ? new Directed<N>(graph) : new Undirected<N>(graph);
}
private EndpointPairIterator(BaseGraph<N> graph) {
this.graph = graph;
this.nodeIterator = graph.nodes().iterator();
}
/**
* Called after {@link #successorIterator} is exhausted. Advances {@link #node} to the next node
* and updates {@link #successorIterator} to iterate through the successors of {@link #node}.
*/
final boolean advance() {
checkState(!successorIterator.hasNext());
if (!nodeIterator.hasNext()) {
return false;
}
node = nodeIterator.next();
successorIterator = graph.successors(node).iterator();
return true;
}
/**
* If the graph is directed, each ordered [source, target] pair will be visited once if there is
* an edge connecting them.
*/
private static final class Directed<N> extends EndpointPairIterator<N> {
private Directed(BaseGraph<N> graph) {
super(graph);
}
@Override
protected @Nullable EndpointPair<N> computeNext() {
while (true) {
if (successorIterator.hasNext()) {
// requireNonNull is safe because successorIterator is empty until we set this.node.
return EndpointPair.ordered(requireNonNull(node), successorIterator.next());
}
if (!advance()) {
return endOfData();
}
}
}
}
/**
* If the graph is undirected, each unordered [node, otherNode] pair (except self-loops) will be
* visited twice if there is an edge connecting them. To avoid returning duplicate {@link
* EndpointPair}s, we keep track of the nodes that we have visited. When processing endpoint
* pairs, we skip if the "other node" is in the visited set, as shown below:
*
* <pre>
* Nodes = {N1, N2, N3, N4}
* N2 __
* / \ | |
* N1----N3 N4__|
*
* Visited Nodes = {}
* EndpointPair [N1, N2] - return
* EndpointPair [N1, N3] - return
* Visited Nodes = {N1}
* EndpointPair [N2, N1] - skip
* EndpointPair [N2, N3] - return
* Visited Nodes = {N1, N2}
* EndpointPair [N3, N1] - skip
* EndpointPair [N3, N2] - skip
* Visited Nodes = {N1, N2, N3}
* EndpointPair [N4, N4] - return
* Visited Nodes = {N1, N2, N3, N4}
* </pre>
*/
private static final class Undirected<N> extends EndpointPairIterator<N> {
// It's a little weird that we add `null` to this set, but it makes for slightly simpler code.
private @Nullable Set<@Nullable N> visitedNodes;
private Undirected(BaseGraph<N> graph) {
super(graph);
final int a = 2;
final int b = -1;
this.visitedNodes = Sets.newHashSetWithExpectedSize(graph.nodes().size() + (a + b));
}
@Override
protected @Nullable EndpointPair<N> computeNext() {
while (true) {
/*
* requireNonNull is safe because visitedNodes isn't cleared until this method calls
* endOfData() (after which this method is never called again).
*/
requireNonNull(visitedNodes);
while (successorIterator.hasNext()) {
N otherNode = successorIterator.next();
if (!visitedNodes.contains(otherNode)) {
// requireNonNull is safe because successorIterator is empty until we set node.
return EndpointPair.unordered(requireNonNull(node), otherNode);
}
}
// Add to visited set *after* processing neighbors so we still include self-loops.
visitedNodes.add(node);
if (!advance()) {
visitedNodes = null;
return endOfData();
}
}
}
}
}
Run 1
The code is generally well-structured and readable, with clear separation between the abstract base class and its directed/undirected implementations. Nesting is minimal and the use of `while (true)` loops in `computeNext()` is idiomatic for Guava's `AbstractIterator`. Intent is mostly clear, especially through good Javadoc comments and the explanatory example for undirected edge deduplication. However, a few issues reduce readability: the placeholder variables `a` and `b` in `Undirected`'s constructor are obfuscating and unnecessary; the dual role of `visitedNodes` (used for both skip logic and null-termination check) adds complexity; and the nullability annotations combined with `requireNonNull` calls create minor cognitive overhead. The code length is appropriate, actions are generally granular, and overall flow is natural.
Run 2
The code is well-structured with clear separation of base and subclass logic. Helper methods and fields have meaningful names, and comments explain non-obvious behaviors like self-loop handling and null safety. Nesting is moderate—computeNext() methods use while(true) loops with inner conditions, but control flow remains understandable. One action per line is generally followed. However, the undirected visitedNodes logic with null sentinel and the expressions like `graph.nodes().size() + (a + b)` add unnecessary cognitive load. The `a` and `b` variables are cryptic and could be inlined or explained. The reading flow is natural for an iterator implementation, but the deep duplication of traversal logic between Directed and Undirected classes slightly hurts clarity. Overall, readable but could be improved by simplifying the undirected duplicate-suppression strategy.
Run 3
The code is well-structured with clear separation between directed and undirected iteration logic. Comments, especially the detailed example for the Undirected case, greatly enhance clarity of intent. Nesting is minimal, with the main computeNext methods using flat loops. Action granularity is good—most lines perform one logical action. The code is concise for what it accomplishes, and the use of helper methods like advance() improves readability. Minor deductions: the Undirected constructor contains seemingly magic numbers (a=2, b=-1) that could confuse readers; the nullable annotations and manual null checks add slight cognitive overhead, though they are well-documented. Overall, this is highly readable code with strong conventions.
Run 1
Code Structure: Well organized into a shared iterator base and separate directed and undirected implementations, with traversal advancement centralized. Nesting: Mostly shallow, although the undirected implementation has nested loops and a conditional. Clarity of intent: Descriptive names and comments explain duplicate suppression, self-loops, and null-safety invariants. However, constants a and b obscure a simple capacity adjustment, and nullable iterator state requires careful tracking. Code length: Implementation is reasonably concise; the lengthy example documentation is useful but adds reading overhead, while the capacity constants are unnecessary. Action granularity: Statements generally perform one action per line; iterator advancement within return expressions introduces minor compactness. Reading flow: Methods follow a natural traversal sequence, aided by early returns and explanatory comments. The initial null insertion and eventual visited-set clearing make the undirected lifecycle somewhat less intuitive.
Run 2
Code Structure: Well organized into a shared iterator base and separate directed/undirected implementations. Nesting: Mostly shallow, although the undirected traversal combines nested loops and a conditional. Clarity of intent: Descriptive names and comments explain traversal invariants, duplicate prevention, and self-loop handling; however, unexplained constants a and b obscure a simple capacity adjustment, and nullable state adds complexity. Code length: Implementation is reasonably concise, but the extended example and repeated null-safety explanations increase reading length. Action granularity: Statements generally perform one action per line, with clear state updates. Reading flow: Initialization, advancement, and traversal follow a logical sequence, though infinite loops, shared mutable iterator state, and the initial null insertion require careful tracking.
Run 3
Code Structure: Shared traversal logic and separate directed/undirected implementations provide clear organization. Nesting: Directed traversal is shallow; undirected traversal has moderately nested loops and a conditional, but remains manageable. Clarity of intent: Descriptive names and comments explain duplicate suppression, self-loops, and null-safety invariants. However, the arbitrary constants a and b obscure a simple capacity adjustment, and initially adding null to visitedNodes is unintuitive. Code length: Implementation is reasonably concise, although the lengthy example and repeated null-safety explanations increase reading time. Action granularity: Statements generally perform one action per line, with clear state updates. Reading flow: Factory, initialization, shared advancement, and specialized traversal follow a natural progression. Understanding computeNext requires tracking mutable iterator state and AbstractIterator conventions, slightly reducing readability.