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 has clear intent and useful documentation, especially for the undirected algorithm. The class structure is logical, separating directed and undirected iterators. However, readability is hurt by inconsistent and compressed formatting: multiple statements are on single lines, and the `of()` method mixes logic with closing braces. Deeply nested loops with while(true) and inner while loops reduce clarity. The `advance()` method contains a multi-line validation-then-return pattern on one line, and repeated requireNonNull comments add noise. Overall, the code is maintainable but could be much clearer with consistent formatting and simpler control flow.
Run 2
The code has some good documentation and logical class structure, but readability is significantly hampered by inconsistent formatting. Many method declarations, statements, and comments are compressed onto single lines, violating the 'one action per line' principle. Imports are also jumbled together. The deeply nested while loops with embedded comments and requireNonNull calls disrupt the natural reading flow. While the Javadocs for the inner classes are helpful, the overall inconsistent indentation and line breaks make the code visually chaotic and harder to parse than necessary.
Run 3
The code has logical organization with clear class structure and documentation, but readability is severely compromised by poor formatting and line breaks. Multiple statements are crammed onto single lines (e.g., field declarations, static factory methods, constructors, method bodies), violating the 'one action per line' principle and disrupting natural reading flow. While nesting depth is moderate and the intent is reasonably clear from the comments and structure, the inconsistent and compressed formatting makes the code significantly harder to scan and understand. The excessive line-wrapping inside methods like `computeNext()` creates an uneven rhythm, and the variable declarations with inline comments add clutter. Overall, the code's logic is sound but its presentation substantially reduces readability.
Run 1
Code Structure: Logical separation into a shared iterator and directed/undirected implementations is strong, but compressed formatting obscures method and class boundaries. Nesting: Mostly moderate; the undirected implementation adds a nested loop and conditional but remains manageable. Clarity of intent: Descriptive names and detailed comments explain traversal, duplicate suppression, null safety, and self-loops. Code length: Implementation is reasonably concise; the extensive example adds length but clarifies behavior. Action granularity: Multiple imports, declarations, statements, and closing braces share lines, making individual actions harder to distinguish. Reading flow: Inconsistent line breaks, inline comments, and merged method boundaries repeatedly interrupt scanning. Overall, sound organization and documentation are substantially undermined by poor formatting.
Run 2
Code Structure: A shared iterator base with separate directed and undirected implementations provides logical organization, but compressed method and class boundaries obscure it. Nesting: Mostly moderate; the undirected implementation adds a nested loop and conditional, remaining manageable. Clarity of intent: Descriptive names and detailed comments explain traversal, duplicate suppression, null handling, and self-loops well. Code length: Implementation is reasonably concise, though the lengthy example documentation slows scanning. Action granularity: Multiple imports, declarations, statements, and braces share lines, making individual operations harder to distinguish. Reading flow: The conceptual progression is natural, but inconsistent formatting, inline comments, and crowded boundaries repeatedly interrupt reading.
Run 3
Code Structure: The shared iterator base and separate directed/undirected implementations provide logical organization, but merged declarations and braces obscure boundaries. Nesting: Mostly moderate; the undirected implementation adds nested loops and a conditional, increasing reading effort. Clarity of intent: Descriptive names and comments clearly explain iteration, duplicate suppression, null safety, and self-loop handling. Code length: Implementation is reasonably concise, though the extensive example adds scanning overhead. Action granularity: Multiple imports, declarations, assignments, and control-flow statements share lines, making individual actions harder to distinguish. Reading flow: The conceptual progression is sensible, but inconsistent formatting, inline comments, and crowded closing braces repeatedly interrupt it. Strong design and documentation partially compensate for poor presentation.