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> gra) {
return gra.isDirected() ? new Directed<N>(gra) : new Undirected<N>(gra);
}
private EndpointPairIterator(BaseGraph<N> gra2) {
this.graph = gra2;
this.nodeIterator = gra2.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 adv() {
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> gra3) {
super(gra3);
}
@Override
protected @Nullable EndpointPair<N> compute() {
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> gra4) {
super(gra4);
this.visitedNodes = Sets.newHashSetWithExpectedSize(gra4.nodes().size() + 1);
}
@Override
protected @Nullable EndpointPair<N> compute() {
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 other = successorIterator.next();
if (!visitedNodes.contains(other)) {
// requireNonNull is safe because successorIterator is empty until we set node.
return EndpointPair.unordered(requireNonNull(node), other);
}
}
// 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-organized, with a clear class hierarchy and sensible separation of directed and undirected iteration logic. The use of Javadoc, especially the example in Undirected, enhances clarity. The main readability weaknesses are the repeated null-checks with explanatory comments, the somewhat opaque method names (`adv`, `gra2`/`gra3`), and a moderate level of nesting inside the compute methods. The field declarations and the overall control flow are understandable, but the mixing of state management (advance method) with traversal logic adds minor cognitive overhead. The code is concise for what it does, and each line generally performs a single logical action, but the reliance on comments to justify non-obvious null safety reduces clarity. Overall, it's readable but could be improved with better naming and clearer state management.
Run 2
The code demonstrates good structure with clear inheritance hierarchy, appropriate use of inner classes, and informative Javadoc comments. Nesting is reasonably flat except for the while loops with nested conditionals in compute() methods. Intent is mostly clear, though null-handling logic (requiring requireNonNull with comments) adds complexity and potential confusion. Code length is appropriate, but action granularity varies—some lines combine multiple operations. The field naming (gra2, gra3, gra4) is awkward and reduces readability. The class comments and method documentation aid understanding, but the null-safety reasoning requires careful reading. Overall, the code is maintainable and follows good practices, but could be improved with better parameter naming and simplification of null-handling patterns.
Run 3
The code is well-structured, with clear separation between directed and undirected iteration logic via inner classes. Nesting is moderate — the Undirected.compute method has two levels of loops, but it's manageable and avoids deeper entanglement. Intent is mostly clear: field and method names explain their roles, and comments clarify non-obvious null-safety and algorithmic choices. Code length is reasonable, though the verbose Javadoc for the undirected example adds some bulk. Action granularity is good: most lines perform a single logical operation. Reading flow is natural, aided by thoughtful comments and consistent formatting. Minor deductions for the slightly awkward null handling (e.g., null in visitedNodes) and the need for explanatory comments around it, which could confuse readers unfamiliar with the pattern.
Run 1
Code Structure: Shared traversal state and separate directed/undirected implementations provide logical organization. Nesting: Mostly shallow, although undirected traversal uses nested loops and a conditional. Clarity of intent: Descriptive class and field names plus detailed comments explain traversal, duplicate suppression, and self-loops. However, gra/gra2/gra3/gra4 and adv are vague; calls to advance() do not match adv(), and compute() does not match AbstractIterator's expected computeNext(), disrupting understanding. Code length: Implementation is reasonably concise, though the lengthy example and repeated null-safety comments increase reading time. Action granularity: Statements generally perform one action per line. Reading flow: Initialization, traversal, and termination follow a natural sequence, but naming inconsistencies and nullable state handling require extra mental effort.
Run 2
Code Structure: Shared iterator state and separate directed/undirected implementations provide logical organization. Nesting: Directed traversal is shallow; undirected traversal has moderately nested loops and conditions but remains manageable. Clarity of intent: Descriptive class names and detailed comments explain traversal, duplicate suppression, and self-loops. However, gra/gra2/gra3/gra4 and adv are weak names, and calls to advance() conflict with the declared adv(); compute() also appears inconsistent with AbstractIterator's expected computeNext() override. These inconsistencies interrupt understanding. Code length: Implementation is reasonably concise, though the lengthy example comment adds substantial reading overhead. Action granularity: Statements generally perform one action per line, with conventional constructor and return expressions. Reading flow: Fields, factory, shared helper, and specialized implementations follow a natural sequence, but inconsistent naming and nullable-state bookkeeping require extra attention.
Run 3
Code Structure: Shared iterator state and separate directed/undirected subclasses provide logical organization. Nesting: Directed traversal is shallow; undirected traversal has moderately nested loops and conditions but remains manageable. Clarity of intent: Descriptive class names and detailed comments explain traversal, duplicate suppression, and self-loops. However, gra/gra2/gra3/gra4 and adv are unclear names, and calls to advance() do not match the declared adv() method. The compute() override also obscures the expected AbstractIterator computeNext() contract. Code length: Implementation is reasonably concise, although the extensive undirected example adds substantial reading length. Action granularity: Statements generally perform one action per line, making state changes easy to identify. Reading flow: Factory, shared advancement logic, and specialized traversal follow a natural sequence, but naming inconsistencies and nullable-state bookkeeping interrupt comprehension.