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> a(BaseGraph<N> a) {
return a.isDirected() ? new Directed<N>(a) : new Undirected<N>(a);
}
private EndpointPairIterator(BaseGraph<N> b) {
this.graph = b;
this.nodeIterator = b.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 b() {
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> c) {
super(c);
}
@Override
protected @Nullable EndpointPair<N> a() {
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> d) {
super(d);
this.visitedNodes = Sets.newHashSetWithExpectedSize(d.nodes().size() + 1);
}
@Override
protected @Nullable EndpointPair<N> a() {
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 e = successorIterator.next();
if (!visitedNodes.contains(e)) {
// requireNonNull is safe because successorIterator is empty until we set node.
return EndpointPair.unordered(requireNonNull(node), e);
}
}
// 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 serious readability issues. Method names like 'a', 'b', 'a()', and 'advance()' are completely uninformative, obscuring intent. Parameters named 'a', 'b', 'c', 'd' are equally poor. The structure mixes public API, internal logic, and nested classes in a way that makes the abstract iterator pattern harder to follow. Deep nesting is moderate but the while(true) loops with nested conditionals add complexity. The extensive comments attempt to clarify behavior but are lengthy and sometimes reference mysterious names ('successorIterator', 'advance'), suggesting code clarity relies too heavily on annotation. Action granularity is acceptable but comprehension is severely hindered by naming and abstract class design. Reading flow is disrupted by poor naming and multi-line comments that feel like they compensate for unclear code.
Run 2
The code is moderately readable but suffers from poor naming and somewhat confusing structure. The class hierarchy is logical, and comments help explain complex logic, but method names like 'a', 'b', and 'a()' (overloaded in subclasses) severely hurt clarity. The use of single-letter parameter names ('a', 'b', 'c', 'd', 'e') obscures intent. Nesting is mostly flat, which is good, but the Undirected iterator's while-true with nested while loops adds complexity. Action granularity is generally reasonable, with one operation per line. The reading flow is disrupted by cryptic names and the need to track state across fields. While the logic is compact, it sacrifices self-documentation for brevity.
Run 3
The code is generally well-structured with clear separation of concerns between the abstract iterator and its directed/undirected implementations. Javadoc comments effectively explain the non-obvious logic, especially in the Undirected case. However, readability is significantly impacted by the use of single-letter method names (a(), b()) and parameter names (a, b, c, d), which obscure intent and force readers to rely on context. The nested while loops create moderate nesting depth, though the logic remains manageable. Action granularity is mostly one operation per line, aiding comprehension. The undirected iterator's visited-node logic is complex but well-documented. Overall, the code would be more readable with descriptive names.
Run 1
Code Structure: Shared iterator state and separate directed/undirected implementations provide logical organization. Nesting: Mostly shallow, though the undirected traversal uses nested loops and a conditional. Clarity of intent: Descriptive fields and detailed comments explain traversal and duplicate suppression, but single-letter methods and parameters obscure meaning. Calls to advance() do not match the declared b() helper, and the a() overrides obscure the expected iterator computation method, making the code harder to follow. Code length: Implementation is reasonably concise, but the lengthy traversal example interrupts scanning. Action granularity: Statements generally perform one action per line. Reading flow: Initialization, traversal, and termination follow a natural sequence, but inconsistent method names and nullable-state handling require extra interpretation.
Run 2
Code Structure: The shared iterator base and separate directed/undirected implementations provide logical organization. Nesting: Directed traversal is shallow; undirected traversal has moderate nesting with two loops and a conditional. Clarity of intent: Descriptive fields and detailed comments explain traversal, duplicate suppression, and self-loops, but single-letter methods and parameters obscure purpose. Calls to advance() do not match the defined b() method, and a() appears to replace AbstractIterator's expected computeNext() override, making the intended execution harder to follow. Code length: Implementation is reasonably concise, though the extensive example adds substantial reading length. Action granularity: Most statements perform one action per line; iterator advancement inside return expressions is compact but slightly less explicit. Reading flow: Early returns and consistent formatting support natural flow, but inconsistent method names interrupt comprehension and force readers to infer missing connections.
Run 3
Code Structure: Directed and undirected iteration are cleanly separated into subclasses, with shared traversal state in the base class. Nesting: Directed traversal is shallow; undirected traversal has moderately nested loops and conditionals but remains manageable. Clarity of intent: Descriptive class and field names and useful comments explain edge traversal, duplicate suppression, and self-loops. However, single-letter methods and variables obscure intent, and calls to advance() do not match the declared b() method; a() also appears inconsistent with AbstractIterator's expected computeNext() override. Code length: Implementation is reasonably concise, though the extensive example adds reading overhead. Action granularity: Most lines perform one clear operation, with conventional inline iterator calls. Reading flow: Traversal follows a logical sequence, but inconsistent naming and nullable-state handling interrupt comprehension and make the code harder to trust.