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 a clear class hierarchy and separation of concerns. The abstract base class handles common logic while Directed and Undirected subclasses implement specific traversal behavior. Nesting is minimal and manageable. Javadoc comments explain non-obvious behavior, especially the undirected deduplication logic with a helpful diagram. Variable names are descriptive and intent is generally clear. However, readability is slightly reduced by the use of nullable fields and the requirement for `requireNonNull` checks scattered throughout, which adds cognitive overhead. The `while (true)` loops with multiple exit points are acceptable but require careful reading. The undirected traversal's use of a visited set containing `null` as a sentinel is noted but still requires mental effort. Overall, this is professional-quality code with good structure and documentation.
Run 3
The code is highly readable with clear structure and intent. The class hierarchy separates directed and undirected graph traversal logic cleanly, and the Javadoc (especially the undirected case diagram) effectively explains the algorithm's behavior. Nesting is minimal with only one level of loop depth in computeNext methods. Variable names are descriptive, and action granularity is appropriate with one primary action per line. The state management pattern (node/successorIterator fields with advance() helper) is well-documented with helpful comments explaining null safety assumptions. Minor readability impacts: the `while (true)` loops with multiple return points require careful reading, and the null-setting of visitedNodes at the end adds slight complexity. These are offset by strong documentation and clear separation of concerns.
Run 1
Code Structure: Well organized into a shared iterator base and separate directed/undirected implementations, with traversal advancement centralized. Nesting: Generally shallow, although the undirected implementation has nested loops and a conditional that require closer attention. Clarity of intent: Descriptive names and useful comments explain duplicate suppression, self-loops, and null-safety invariants. However, adding null to visitedNodes and clearing the set on completion introduce subtle state conventions. Code length: Implementation is concise; the lengthy undirected example helps understanding but adds substantial reading overhead. Action granularity: Most lines perform one clear action, with only straightforward combined expressions. Reading flow: Factory, initialization, advancement, and specialized traversal follow a logical sequence. Stateful iteration and reliance on AbstractIterator lifecycle behavior slightly reduce immediate readability.
Run 2
Code Structure: Shared traversal logic is cleanly separated from directed and undirected implementations. Nesting: Mostly shallow, although undirected traversal uses nested loops and a conditional. Clarity of intent: Descriptive names, documented invariants, and the duplicate-filtering example explain behavior well; nullable state and initially adding null to the visited set introduce minor cognitive overhead. Code length: Implementation is concise, though the extensive example and repeated null-safety explanations lengthen reading. Action granularity: Statements generally perform one action per line, with straightforward state updates. Reading flow: Factory, constructor, shared advancement, and specialized iterators follow a logical order. Understanding iteration requires tracking state across advance() and computeNext(), but comments make that manageable.
Run 3
Code Structure: Well organized into a shared iterator base and separate directed and undirected implementations, with advancement logic centralized. Nesting: Mostly shallow, though the undirected implementation has nested loops and a conditional. Clarity of intent: Descriptive names and helpful comments explain duplicate suppression, self-loops, and null-safety invariants; nullable state and the initial null entry in visitedNodes require extra attention. Code length: Implementation is concise, although the extensive graph example makes the listing longer. Action granularity: Statements generally perform one action per line, with only straightforward composed expressions. Reading flow: Factory, initialization, advancement, and specialized iteration follow a natural progression. Understanding the stateful iteration still requires tracking interactions among node, successorIterator, and visitedNodes.