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);
this.visitedNodes = Sets.newHashSetWithExpectedSize(graph.nodes().size() + 0x1);
}
@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 well-structured and readable. The class hierarchy is logical, with a clear base class handling shared iteration logic and subclasses for directed/undirected cases. Nesting is moderate—only two levels deep in computeNext methods, which is acceptable. Intent is clearly documented with Javadoc and inline comments explaining non-obvious decisions like null handling and visited-node tracking. Code length is appropriate; comments add necessary context without excessive verbosity. Action granularity is good: most lines perform a single operation, and method calls are isolated. Reading flow is natural, with helper methods like advance() breaking down complex logic. Minor deductions: the Undirected.computeNext method has a slightly tangled flow with the inner while loop and null-safety annotations; the visitedNodes null assignment is explained but still requires careful reading. Overall, this is production-quality, maintainable code from Guava.
Run 2
The code demonstrates clear structure and intent, with well-documented classes and methods. The iterator pattern is implemented logically, separating directed and undirected cases cleanly. Nesting is moderate but controlled, with the main loops in computeNext() methods being flat enough to follow. Variable names are descriptive, and comments explain non-obvious logic like the null visitedNodes convention and the self-loop handling. However, some areas slightly reduce readability: the initial state uses a dummy empty iterator, which is a bit obscure without deep understanding, and the nullability handling with requireNonNull calls, while documented, adds cognitive overhead. The historical comment about '0x1' in set sizing is confusing. Overall, it's concise but could be clearer on initial state setup.
Run 3
The code is highly readable. It has a clear package and import structure, a concise class hierarchy, and well-documented inner classes. The nesting is only two levels deep in the computeNext methods, which keeps the logic flat and easy to follow. Each method has a clear single purpose: `advance` updates iteration state, and `computeNext` returns the next endpoint pair. Comments explain the tricky parts, especially the visited-node logic in `Undirected` and the non-null assumptions. Variable names are descriptive, and one action per line is mostly respected. The class-level javadoc and method-level documentation make the intent obvious without being verbose. Minor deductions for the slightly unusual `0x1` addition in `newHashSetWithExpectedSize` and the reliance on comments for null-safety, but overall this is an excellent example of maintainable code.
Run 1
Code Structure: Well organized into a shared iterator base and separate directed and undirected implementations, with common advancement logic centralized. Nesting: Mostly shallow; the undirected implementation introduces a manageable nested loop and conditional. Clarity of intent: Descriptive names and explanatory comments make edge traversal, duplicate suppression, and self-loop handling clear. Nullable state, adding null to the visited set, and the hexadecimal 0x1 introduce minor cognitive overhead. Code length: Implementation is concise, although the extensive undirected example adds substantial documentation length. Action granularity: Statements generally perform one action per line; iterator advancement within return expressions remains understandable. Reading flow: Initialization, successor processing, node advancement, and termination follow a logical sequence. However, understanding the state invariants requires tracking fields across advance() and computeNext(), slightly reducing immediate readability.
Run 2
Code Structure: Shared traversal logic is cleanly separated from directed and undirected implementations. Nesting: The directed iterator is shallow; the undirected iterator has moderate nesting, but its loops and early returns remain manageable. Clarity of intent: Descriptive names and comments explain traversal invariants, duplicate suppression, and self-loop handling. However, null sentinels, nullable state, and the unexplained hexadecimal 0x1 introduce minor cognitive overhead. Code length: Implementation is concise, although the extensive undirected example adds substantial documentation length. Action granularity: Statements generally perform one action per line, with clear state updates. Reading flow: Factory, initialization, shared advancement, and specialized traversal follow a logical sequence. Understanding computeNext requires tracking state across calls and knowing AbstractIterator's lifecycle, slightly reducing readability.
Run 3
Code Structure: Shared iteration logic is cleanly separated from directed and undirected implementations. Nesting: Directed iteration is shallow; undirected iteration has moderate nesting through two loops and a conditional, but remains manageable. Clarity of intent: Descriptive names and comments explain duplicate avoidance, self-loops, and null-safety invariants. However, adding null to the visited set and clearing it on completion introduce subtle state management. Code length: Implementation is reasonably concise, though the extensive example and repeated null-safety comments increase reading length. Action granularity: Statements generally perform one action per line, with straightforward assignments and returns. Reading flow: Initialization, advancement, and edge production follow a logical progression, although understanding the undirected iterator requires tracking state across calls. Minor distractions include the hexadecimal 0x1 and tightly grouped imports.