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 highly readable with clear logical organization: an abstract base class encapsulates shared logic, while directed and undirected variants are cleanly separated into subclasses. Nesting is minimal and control flow is straightforward. The intent of each method and field is well-documented with Javadoc and inline comments, including explanations of non-obvious decisions like the use of null in `visitedNodes` and the safety of `requireNonNull`. Code length is appropriate—concise but not overly compact. Action granularity is mostly one action per line, contributing to clarity. The reading flow is natural: fields, constructors, static factory, shared helper, then subclasses. Minor deductions: the inner `while (true)` loops and reliance on state (`node`, `successorIterator`) add slight cognitive load, and the `@Nullable` set with null `visitedNodes` is a bit unusual despite explicit comments. Overall, it is exceptionally well-structured for a graph iterator implementation.
Run 2
The code is well-structured with clear class hierarchy, logical separation of directed and undirected cases, and good documentation. Nesting is minimal—only two levels in computeNext methods. Intent is clear from method names and Javadoc. Actions are appropriately granular, with one operation per line mostly. The reading flow is natural, aided by descriptive comments and a visual example. Minor deductions: the `while (true)` loops with multiple exit points slightly obscure control flow, and the null-handling logic (e.g., clearing `visitedNodes` to null) adds some cognitive overhead despite comments. Overall, highly readable.
Run 3
The code is generally well-structured and readable. It has clear class hierarchy, meaningful names, and helpful Javadoc including a visual example for the undirected case. The state management is mostly clear. However, a few aspects hurt readability: the use of mutable fields (node, successorIterator, visitedNodes) combined with a while(true) loop in computeNext() creates a somewhat non-linear flow. The nullable fields and repeated requireNonNull() calls add cognitive overhead, requiring the reader to carefully track state invariants. The advance() method has a checkState precondition that must be understood in context. Overall, it is reasonably concise but could be clearer with more explicit state handling (e.g., encapsulating the node and successor iterator together) or less reliance on null sentinels. These issues prevent a higher score.
Run 1
Code Structure: Logical organization separates shared iteration state from directed and undirected implementations, with a small factory and reusable advance method. Nesting: Directed traversal is shallow; undirected traversal has moderate nesting through two loops and a conditional, but remains manageable. Clarity of intent: Descriptive names and comments explain duplicate suppression, self-loops, and null-safety invariants. However, adding null to visitedNodes and later clearing the set introduce non-obvious lifecycle details. Code length: Implementation is reasonably concise; the lengthy illustrative documentation adds bulk but helps explain the algorithm. Action granularity: Most lines perform one clear action, with only straightforward expressions combining operations. Reading flow: Methods and subclasses follow a natural progression, although understanding computeNext requires tracking shared mutable state and AbstractIterator lifecycle behavior.
Run 2
Code Structure: Shared traversal logic and separate directed/undirected implementations provide clear organization. Nesting: Mostly shallow, although the undirected iterator combines nested loops and a conditional. Clarity of intent: Descriptive names, invariant comments, and the worked example explain edge enumeration and duplicate prevention well; nullable state and the initial null entry in visitedNodes introduce some cognitive overhead. Code length: Implementation is concise, though the extensive example and repeated null-safety explanations lengthen the presentation. Action granularity: Statements generally perform one action per line, with straightforward state updates. Reading flow: Initialization, traversal, and termination follow a logical sequence, but understanding computeNext requires tracking shared mutable state and the AbstractIterator lifecycle. Overall, the code is highly readable with modest complexity from iterator invariants and null handling.
Run 3
Code Structure: Shared traversal logic is cleanly separated from directed and undirected implementations. Nesting: Generally shallow, although the undirected iterator combines nested loops and a conditional. Clarity of intent: Descriptive names and detailed comments explain duplicate suppression, self-loops, and null-safety invariants; nullable state and initially adding null to the visited set introduce some cognitive overhead. Code length: Implementation is concise, though the extensive example documentation lengthens the listing. Action granularity: Statements generally perform one action per line, with straightforward state updates. Reading flow: Factory, initialization, shared advancement, and specialized iteration follow a logical sequence. Understanding execution requires tracking iterator state across calls and knowing AbstractIterator's lifecycle, slightly reducing readability.