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() + 1);
}
@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: a shared abstract base handles common iteration logic, while Directed and Undirected subclasses encapsulate their specific behaviors. Methods are short and focused, with one primary action per line in most cases. Comments explain non-obvious decisions, such as null-safety reasoning, the undirected duplicate-avoidance strategy, and self-loop handling. Nesting is shallow, and control flow—particularly the `while (true)` loops with early returns—follows a natural iterator pattern, making intent clear. Minor deductions: some null-handling requires careful reasoning and inline comments; the `visitedNodes` initialization with a size hint is slightly opaque; and a few lines, like `visitedNodes.add(node)` before `advance()`, depend on implicit state, which requires an explanatory comment. Overall, it strikes a strong balance between conciseness and clarity.
Run 2
The code is highly readable with clear structure and intent. It uses a well-organized class hierarchy with a base class and two nested subclasses for directed/undirected cases. Nesting is minimal—though there are several `while` loops and an `if` inside, depth stays manageable. Each method has a single responsibility, and one action is performed per line in most places. The use of comments and Javadocs meaningfully clarifies tricky logic (e.g., null-safety rationale, self-loop handling, duplicate avoidance). Variable names are descriptive. The undirected algorithm's approach is slightly non-obvious, but the thorough explanation and example mitigate confusion. Some minor verbosity—like repeated `requireNonNull(visitedNodes)` and `requireNonNull(node)`—adds safety but also length. Overall, the code is well-crafted for a library context, balancing clarity and conciseness effectively.
Run 3
This code is highly readable. It demonstrates clear structure with logical separation between the abstract base class and directed/undirected implementations. Nesting is minimal, with only a couple of loops and conditionals. The intent of each class and method is well-documented, especially the complex logic in the Undirected inner class. Code length is appropriate for the functionality, and action granularity is generally one action per line. Reading flow is natural, with comments explaining non-obvious decisions. Minor drawbacks include the null assignment pattern for 'visitedNodes' and field initialization quirks, but these are adequately commented.
Run 1
Code Structure: Well organized into a shared iterator base and separate directed/undirected implementations, with advancement logic centralized. Nesting: Mostly shallow; the undirected implementation adds a manageable nested loop and conditional. Clarity of intent: Descriptive names and comments explain traversal, duplicate suppression, self-loops, and null-safety assumptions. The initial null entry in visitedNodes and its later null assignment introduce some cognitive overhead. Code length: Implementation is concise; the lengthy documentation example is useful but increases reading time. Action granularity: Statements generally perform one action per line, with straightforward state updates. Reading flow: Factory, initialization, shared advancement, and specialized traversal follow a natural progression. Stateful iteration and while(true) loops require tracking invariants, but clear termination paths and explanatory comments keep the code highly readable.
Run 2
Code Structure: Well organized into a shared iterator base and separate directed/undirected implementations, with common advancement logic factored out. Nesting: Mostly shallow; the undirected implementation has moderate loop-and-condition nesting that remains manageable. Clarity of intent: Descriptive names and detailed comments explain duplicate suppression, self-loops, and null-safety invariants, though nullable state and adding null to the visited set require extra thought. Code length: Implementation is concise; the lengthy illustrative documentation is useful but increases reading time. Action granularity: Statements generally perform one action per line, with conventional iterator calls embedded in return expressions. Reading flow: Factory, initialization, advancement, and specialized traversal follow a logical progression. Stateful iteration and while(true) loops slightly complicate tracing, but explicit termination checks and comments keep the flow understandable.
Run 3
Code Structure: Shared traversal logic is cleanly separated from directed and undirected implementations. Nesting: Generally shallow, though the undirected iterator uses nested loops and a conditional. Clarity of intent: Descriptive names and detailed comments explain duplicate avoidance, self-loops, and null-safety invariants; nullable state and the initial null entry require extra thought. Code length: Implementation is concise, although the extensive example and repeated safety comments increase reading length. Action granularity: Statements generally perform one action per line, with clear state transitions. Reading flow: Factory, constructor, shared helper, and specialized implementations follow a logical order. Stateful iteration and reliance on AbstractIterator lifecycle conventions slightly reduce immediate readability.