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> add(BaseGraph<N> index) {
return index.isDirected() ? new Directed<N>(index) : new Undirected<N>(index);
}
private EndpointPairIterator(BaseGraph<N> cache) {
this.graph = cache;
this.nodeIterator = cache.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 resolve() {
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> score) {
super(score);
}
@Override
protected @Nullable EndpointPair<N> removeScore() {
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> value) {
super(value);
this.visitedNodes = Sets.newHashSetWithExpectedSize(value.nodes().size() + 1);
}
@Override
protected @Nullable EndpointPair<N> readMessage() {
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 finalNode = successorIterator.next();
if (!visitedNodes.contains(finalNode)) {
// requireNonNull is safe because successorIterator is empty until we set node.
return EndpointPair.unordered(requireNonNull(node), finalNode);
}
}
// 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 has a clear class structure and decent documentation, but readability suffers from confusing naming choices that obscure intent. Method and parameter names like 'cache', 'score', 'value', 'removeScore', and 'readMessage' appear to be obfuscated or result from renaming artifacts, which makes the code harder to follow. The logic is mostly linear with shallow nesting, and each line generally performs one action. However, the while(true) loops with early returns and nullable fields add cognitive overhead. The Javadoc for the undirected case is helpful, but the inline comments about null safety are necessary due to the peculiar use of nullable state. Overall, the structure and flow are reasonable, but the unclear naming and slight overuse of comments to explain confusing parts lower the readability score.
Run 2
The code is generally readable with clear class structure, good documentation, and logical separation of concerns. The static factory method `add()` clearly distinguishes directed vs undirected iterators. Javadoc comments explain complex logic, especially the undirected duplicate-avoidance algorithm. However, readability is reduced by some confusing method names like `removeScore()` and `readMessage()` that don't match their actual purpose (likely artifacts from obfuscation). Additionally, the `Undirected` inner class has unnecessary null-checking of `visitedNodes` and mutating it to null creates state complexity. The `while(true)` loops with `resolve()`/`advance()` methods create some nesting and control flow that requires careful reading. Variable names like `cache`, `score`, and `value` for graph parameters are inconsistent and add minor confusion. Overall, the code is well-structured and documented but has naming inconsistencies and slightly convoluted state management that prevent it from being highly readable.
Run 3
This code is hard to follow due to several major readability issues. The most glaring problem is the confusing, renamed methods: 'removeScore()' in Directed should be 'computeNext()', and 'readMessage()' in Undirected likewise overrides computeNext but has an unrelated name. Parameter names like 'score', 'cache', and 'value' are misleading and unrelated to their actual roles (graph or index). The field 'node' being nullable while successorIterator is never null creates inconsistent messaging. The Undirected class relies on a nullable 'visitedNodes' set that is explicitly set to null at the end, requiring requireNonNull calls that obscure control flow. The nested while loops and boolean advance/resolve methods add more cognitive load, and the comments are verbose while not clarifying the unusual method renaming. Overall, the intent is unclear, naming is inconsistent, and the iterator state management makes the logic convoluted.
Run 1
Code Structure: Shared traversal state and separate directed/undirected subclasses provide logical organization. Nesting: Directed traversal is shallow; undirected traversal has moderately nested loops and conditionals. Clarity of intent: Comments explain edge deduplication and null handling, but names such as add, resolve, removeScore, readMessage, and score obscure their roles. Calls to undefined advance() conflict with resolve(), and the overridden methods do not match AbstractIterator's computeNext(), making the intended execution harder to follow. Code length: Implementation is reasonably concise, though the extensive undirected example interrupts scanning. Action granularity: Statements generally perform one action per line, with straightforward state updates. Reading flow: Fields, initialization, traversal helpers, and subclasses follow a natural order, but inconsistent naming and method mismatches disrupt continuity.
Run 2
Code Structure: The shared iterator base and separate directed/undirected implementations provide logical organization. Nesting: The directed implementation is shallow, but the undirected implementation nests loops and conditions three levels deep. Clarity of intent: Documentation explains traversal, duplicate suppression, and self-loops well; however, arbitrary names such as add, resolve, removeScore, readMessage, cache, and score obscure their roles. Calls to undefined advance() and inconsistent override names further disrupt understanding. Code length: Implementation is reasonably concise, although the lengthy example and repeated null-safety explanations add reading overhead. Action granularity: Statements generally perform one action per line, making state updates easy to follow. Reading flow: Traversal and termination follow a sensible sequence, but inconsistent naming and nullable state require extra mental tracking.
Run 3
Code Structure: The shared iterator base and separate directed/undirected subclasses provide logical organization. Nesting: Directed traversal is shallow; undirected traversal adds a nested loop and conditional but remains manageable. Clarity of intent: Graph-related fields and explanatory comments help, but arbitrary names such as add, resolve, removeScore, readMessage, and constructor parameters obscure purpose. Calls to undefined advance() and mismatched AbstractIterator override names disrupt understanding and suggest broken renaming. Code length: Implementation is reasonably concise, although the extensive undirected example and repeated null-safety explanations add reading overhead. Action granularity: Statements generally perform one action per line; the factory ternary is compact and understandable. Reading flow: Fields, factory, constructor, helper, and subclasses follow a natural order, but inconsistent naming forces readers to infer relationships that should be explicit.