Skip to content

Commit 36e3995

Browse files
klueverGoogle Java Core Libraries
authored andcommitted
Validate and invalidate Graphs.transpose(graph).incidentEdges(node) like other graph views.
The transposed `Graph`'s `incidentEdges` returned a raw view without checking `node`, so it accepted absent (or null) nodes, and after `node` was removed its methods threw `IllegalArgumentException` instead of the documented `IllegalStateException`. It now delegates to the original graph's `incidentEdges` (which validates `node` immediately and preserves its iteration order) and wraps the result in the usual invalidatable view. Fixes #8867 Fixes #8868 RELNOTES=`graph`: Fixed `Graphs.transpose(graph).incidentEdges(node)` not rejecting absent nodes and throwing the wrong exception after `node` is removed. PiperOrigin-RevId: 1026654445
1 parent 23ddd04 commit 36e3995

4 files changed

Lines changed: 80 additions & 16 deletions

File tree

‎android/guava-tests/test/com/google/common/graph/GraphsTest.java‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,7 @@
2727
import static org.junit.Assert.assertThrows;
2828

2929
import com.google.common.collect.ImmutableSet;
30+
import java.util.Set;
3031
import org.jspecify.annotations.NullUnmarked;
3132
import org.junit.Test;
3233
import org.junit.runner.RunWith;
@@ -383,6 +384,36 @@ public void transpose_directedGraph() {
383384
AbstractGraphTest.validateGraph(transpose);
384385
}
385386

387+
@Test
388+
public void transpose_directedGraph_incidentEdges_invalidatedByNodeRemoval() {
389+
MutableGraph<Integer> directedGraph = GraphBuilder.directed().build();
390+
directedGraph.putEdge(N1, N2);
391+
Graph<Integer> transpose = transpose(directedGraph);
392+
assertThrows(IllegalArgumentException.class, () -> transpose.incidentEdges(N3));
393+
assertThrows(NullPointerException.class, () -> transpose.incidentEdges(null));
394+
395+
Set<EndpointPair<Integer>> incidentEdges = transpose.incidentEdges(N1);
396+
assertThat(incidentEdges).containsExactly(EndpointPair.ordered(N2, N1));
397+
directedGraph.removeNode(N1);
398+
assertThrows(IllegalStateException.class, incidentEdges::size);
399+
assertThrows(IllegalStateException.class, incidentEdges::iterator);
400+
assertThrows(
401+
IllegalStateException.class, () -> incidentEdges.contains(EndpointPair.ordered(N2, N1)));
402+
int unused = incidentEdges.hashCode(); // doesn't throw
403+
}
404+
405+
@Test
406+
public void transpose_directedGraph_incidentEdges_stableIncidentEdgeOrder() {
407+
MutableGraph<Integer> directedGraph =
408+
GraphBuilder.directed().incidentEdgeOrder(ElementOrder.stable()).build();
409+
directedGraph.putEdge(N2, N1);
410+
directedGraph.putEdge(N1, N3);
411+
412+
assertThat(transpose(directedGraph).incidentEdges(N1))
413+
.containsExactly(EndpointPair.ordered(N1, N2), EndpointPair.ordered(N3, N1))
414+
.inOrder();
415+
}
416+
386417
@Test
387418
public void transpose_undirectedValueGraph() {
388419
MutableValueGraph<Integer, String> undirectedGraph = ValueGraphBuilder.undirected().build();

‎android/guava/src/com/google/common/graph/Graphs.java‎

Lines changed: 9 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -364,14 +364,15 @@ public Set<N> successors(N node) {
364364

365365
@Override
366366
public Set<EndpointPair<N>> incidentEdges(N node) {
367-
return new IncidentEdgeSet<N>(this, node, IncidentEdgeSet.EdgeType.BOTH) {
368-
@Override
369-
public Iterator<EndpointPair<N>> iterator() {
370-
return transform(
371-
delegate().incidentEdges(node).iterator(),
372-
edge -> EndpointPair.of(delegate(), edge.nodeV(), edge.nodeU()));
373-
}
374-
};
367+
Set<EndpointPair<N>> incidentEdges = delegate().incidentEdges(node);
368+
return nodeInvalidatableSet(
369+
new IncidentEdgeSet<N>(this, node, IncidentEdgeSet.EdgeType.BOTH) {
370+
@Override
371+
public Iterator<EndpointPair<N>> iterator() {
372+
return transform(incidentEdges.iterator(), Graphs::transpose);
373+
}
374+
},
375+
node);
375376
}
376377

377378
@Override

‎guava-tests/test/com/google/common/graph/GraphsTest.java‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,7 @@
2727
import static org.junit.Assert.assertThrows;
2828

2929
import com.google.common.collect.ImmutableSet;
30+
import java.util.Set;
3031
import org.jspecify.annotations.NullUnmarked;
3132
import org.junit.Test;
3233
import org.junit.runner.RunWith;
@@ -383,6 +384,36 @@ public void transpose_directedGraph() {
383384
AbstractGraphTest.validateGraph(transpose);
384385
}
385386

387+
@Test
388+
public void transpose_directedGraph_incidentEdges_invalidatedByNodeRemoval() {
389+
MutableGraph<Integer> directedGraph = GraphBuilder.directed().build();
390+
directedGraph.putEdge(N1, N2);
391+
Graph<Integer> transpose = transpose(directedGraph);
392+
assertThrows(IllegalArgumentException.class, () -> transpose.incidentEdges(N3));
393+
assertThrows(NullPointerException.class, () -> transpose.incidentEdges(null));
394+
395+
Set<EndpointPair<Integer>> incidentEdges = transpose.incidentEdges(N1);
396+
assertThat(incidentEdges).containsExactly(EndpointPair.ordered(N2, N1));
397+
directedGraph.removeNode(N1);
398+
assertThrows(IllegalStateException.class, incidentEdges::size);
399+
assertThrows(IllegalStateException.class, incidentEdges::iterator);
400+
assertThrows(
401+
IllegalStateException.class, () -> incidentEdges.contains(EndpointPair.ordered(N2, N1)));
402+
int unused = incidentEdges.hashCode(); // doesn't throw
403+
}
404+
405+
@Test
406+
public void transpose_directedGraph_incidentEdges_stableIncidentEdgeOrder() {
407+
MutableGraph<Integer> directedGraph =
408+
GraphBuilder.directed().incidentEdgeOrder(ElementOrder.stable()).build();
409+
directedGraph.putEdge(N2, N1);
410+
directedGraph.putEdge(N1, N3);
411+
412+
assertThat(transpose(directedGraph).incidentEdges(N1))
413+
.containsExactly(EndpointPair.ordered(N1, N2), EndpointPair.ordered(N3, N1))
414+
.inOrder();
415+
}
416+
386417
@Test
387418
public void transpose_undirectedValueGraph() {
388419
MutableValueGraph<Integer, String> undirectedGraph = ValueGraphBuilder.undirected().build();

‎guava/src/com/google/common/graph/Graphs.java‎

Lines changed: 9 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -365,14 +365,15 @@ public Set<N> successors(N node) {
365365

366366
@Override
367367
public Set<EndpointPair<N>> incidentEdges(N node) {
368-
return new IncidentEdgeSet<N>(this, node, IncidentEdgeSet.EdgeType.BOTH) {
369-
@Override
370-
public Iterator<EndpointPair<N>> iterator() {
371-
return transform(
372-
delegate().incidentEdges(node).iterator(),
373-
edge -> EndpointPair.of(delegate(), edge.nodeV(), edge.nodeU()));
374-
}
375-
};
368+
Set<EndpointPair<N>> incidentEdges = delegate().incidentEdges(node);
369+
return nodeInvalidatableSet(
370+
new IncidentEdgeSet<N>(this, node, IncidentEdgeSet.EdgeType.BOTH) {
371+
@Override
372+
public Iterator<EndpointPair<N>> iterator() {
373+
return transform(incidentEdges.iterator(), Graphs::transpose);
374+
}
375+
},
376+
node);
376377
}
377378

378379
@Override

0 commit comments

Comments
 (0)
⌂ 换网址