fix behavior of Graph/ValueGraph views for a node when that node is removed from the graph

ineuwirth · Google Java Core Libraries · commit 950799691c4e · 2023-10-06T11:33:58.000-07:00
RELNOTES=fix behavior of Graph/ValueGraph views for a node when that node is removed from the graph
PiperOrigin-RevId: 571390607
diff --git a/android/guava-tests/test/com/google/common/graph/AbstractGraphTest.java b/android/guava-tests/test/com/google/common/graph/AbstractGraphTest.java
@@ -385,10 +385,13 @@ public void removeNode_nodeNotPresent() {
   public void removeNode_queryAfterRemoval() {
     assume().that(graphIsMutable()).isTrue();
 
-    addNode(N1);
-    @SuppressWarnings("unused")
-    Set<Integer> unused = graph.adjacentNodes(N1); // ensure cache (if any) is populated
+    putEdge(N1, N2);
+    putEdge(N2, N1);
+    Set<Integer> n1AdjacentNodes = graph.adjacentNodes(N1);
+    Set<Integer> n2AdjacentNodes = graph.adjacentNodes(N2);
     assertThat(graphAsMutableGraph.removeNode(N1)).isTrue();
+    assertThat(n1AdjacentNodes).isEmpty();
+    assertThat(n2AdjacentNodes).isEmpty();
     IllegalArgumentException e =
         assertThrows(IllegalArgumentException.class, () -> graph.adjacentNodes(N1));
     assertNodeNotInGraphErrorMessage(e);
diff --git a/android/guava-tests/test/com/google/common/graph/AbstractNetworkTest.java b/android/guava-tests/test/com/google/common/graph/AbstractNetworkTest.java
@@ -670,11 +670,12 @@ public void removeNode_nodeNotPresent() {
   public void removeNode_queryAfterRemoval() {
     assume().that(graphIsMutable()).isTrue();
 
-    addNode(N1);
-    @SuppressWarnings("unused")
-    Set<Integer> unused =
-        networkAsMutableNetwork.adjacentNodes(N1); // ensure cache (if any) is populated
+    addEdge(N1, N2, E12);
+    Set<Integer> n1AdjacentNodes = networkAsMutableNetwork.adjacentNodes(N1);
+    Set<Integer> n2AdjacentNodes = networkAsMutableNetwork.adjacentNodes(N2);
     assertTrue(networkAsMutableNetwork.removeNode(N1));
+    assertThat(n1AdjacentNodes).isEmpty();
+    assertThat(n2AdjacentNodes).isEmpty();
     IllegalArgumentException e =
         assertThrows(
             IllegalArgumentException.class, () -> networkAsMutableNetwork.adjacentNodes(N1));
diff --git a/android/guava/src/com/google/common/graph/StandardMutableValueGraph.java b/android/guava/src/com/google/common/graph/StandardMutableValueGraph.java
@@ -24,6 +24,7 @@
 import static com.google.common.graph.Graphs.checkPositive;
 import static java.util.Objects.requireNonNull;
 
+import com.google.common.collect.ImmutableList;
 import com.google.errorprone.annotations.CanIgnoreReturnValue;
 import javax.annotation.CheckForNull;
 
@@ -136,17 +137,21 @@ public boolean removeNode(N node) {
       }
     }
 
-    for (N successor : connections.successors()) {
+    for (N successor : ImmutableList.copyOf(connections.successors())) {
       // requireNonNull is safe because the node is a successor.
       requireNonNull(nodeConnections.getWithoutCaching(successor)).removePredecessor(node);
+      requireNonNull(connections.removeSuccessor(successor));
       --edgeCount;
     }
     if (isDirected()) { // In undirected graphs, the successor and predecessor sets are equal.
-      for (N predecessor : connections.predecessors()) {
+      // Since views are returned, we need to copy the predecessors that will be removed.
+      // Thus we avoid modifying the underlying view while iterating over it.
+      for (N predecessor : ImmutableList.copyOf(connections.predecessors())) {
         // requireNonNull is safe because the node is a predecessor.
         checkState(
             requireNonNull(nodeConnections.getWithoutCaching(predecessor)).removeSuccessor(node)
                 != null);
+        connections.removePredecessor(predecessor);
         --edgeCount;
       }
     }
diff --git a/guava-tests/test/com/google/common/graph/AbstractGraphTest.java b/guava-tests/test/com/google/common/graph/AbstractGraphTest.java
@@ -385,10 +385,13 @@ public void removeNode_nodeNotPresent() {
   public void removeNode_queryAfterRemoval() {
     assume().that(graphIsMutable()).isTrue();
 
-    addNode(N1);
-    @SuppressWarnings("unused")
-    Set<Integer> unused = graph.adjacentNodes(N1); // ensure cache (if any) is populated
+    putEdge(N1, N2);
+    putEdge(N2, N1);
+    Set<Integer> n1AdjacentNodes = graph.adjacentNodes(N1);
+    Set<Integer> n2AdjacentNodes = graph.adjacentNodes(N2);
     assertThat(graphAsMutableGraph.removeNode(N1)).isTrue();
+    assertThat(n1AdjacentNodes).isEmpty();
+    assertThat(n2AdjacentNodes).isEmpty();
     IllegalArgumentException e =
         assertThrows(IllegalArgumentException.class, () -> graph.adjacentNodes(N1));
     assertNodeNotInGraphErrorMessage(e);
diff --git a/guava-tests/test/com/google/common/graph/AbstractNetworkTest.java b/guava-tests/test/com/google/common/graph/AbstractNetworkTest.java
@@ -677,11 +677,12 @@ public void removeNode_nodeNotPresent() {
   public void removeNode_queryAfterRemoval() {
     assume().that(graphIsMutable()).isTrue();
 
-    addNode(N1);
-    @SuppressWarnings("unused")
-    Set<Integer> unused =
-        networkAsMutableNetwork.adjacentNodes(N1); // ensure cache (if any) is populated
+    addEdge(N1, N2, E12);
+    Set<Integer> n1AdjacentNodes = networkAsMutableNetwork.adjacentNodes(N1);
+    Set<Integer> n2AdjacentNodes = networkAsMutableNetwork.adjacentNodes(N2);
     assertTrue(networkAsMutableNetwork.removeNode(N1));
+    assertThat(n1AdjacentNodes).isEmpty();
+    assertThat(n2AdjacentNodes).isEmpty();
     IllegalArgumentException e =
         assertThrows(
             IllegalArgumentException.class, () -> networkAsMutableNetwork.adjacentNodes(N1));
diff --git a/guava/src/com/google/common/graph/StandardMutableValueGraph.java b/guava/src/com/google/common/graph/StandardMutableValueGraph.java
@@ -24,6 +24,7 @@
 import static com.google.common.graph.Graphs.checkPositive;
 import static java.util.Objects.requireNonNull;
 
+import com.google.common.collect.ImmutableList;
 import com.google.errorprone.annotations.CanIgnoreReturnValue;
 import javax.annotation.CheckForNull;
 
@@ -136,17 +137,21 @@ public boolean removeNode(N node) {
       }
     }
 
-    for (N successor : connections.successors()) {
+    for (N successor : ImmutableList.copyOf(connections.successors())) {
       // requireNonNull is safe because the node is a successor.
       requireNonNull(nodeConnections.getWithoutCaching(successor)).removePredecessor(node);
+      requireNonNull(connections.removeSuccessor(successor));
       --edgeCount;
     }
     if (isDirected()) { // In undirected graphs, the successor and predecessor sets are equal.
-      for (N predecessor : connections.predecessors()) {
+      // Since views are returned, we need to copy the predecessors that will be removed.
+      // Thus we avoid modifying the underlying view while iterating over it.
+      for (N predecessor : ImmutableList.copyOf(connections.predecessors())) {
         // requireNonNull is safe because the node is a predecessor.
         checkState(
             requireNonNull(nodeConnections.getWithoutCaching(predecessor)).removeSuccessor(node)
                 != null);
+        connections.removePredecessor(predecessor);
         --edgeCount;
       }
     }

Original file line number	Diff line number	Diff line change
`@@ -24,6 +24,7 @@`
`24`	`24`	`import static com.google.common.graph.Graphs.checkPositive;`
`25`	`25`	`import static java.util.Objects.requireNonNull;`
`26`	`26`
	`27`	`+import com.google.common.collect.ImmutableList;`
`27`	`28`	`import com.google.errorprone.annotations.CanIgnoreReturnValue;`
`28`	`29`	`import javax.annotation.CheckForNull;`
`29`	`30`
`@@ -136,17 +137,21 @@ public boolean removeNode(N node) {`
`136`	`137`	`}`
`137`	`138`	`}`
`138`	`139`
`139`		`- for (N successor : connections.successors()) {`
	`140`	`+ for (N successor : ImmutableList.copyOf(connections.successors())) {`
`140`	`141`	`// requireNonNull is safe because the node is a successor.`
`141`	`142`	`requireNonNull(nodeConnections.getWithoutCaching(successor)).removePredecessor(node);`
	`143`	`+ requireNonNull(connections.removeSuccessor(successor));`
`142`	`144`	`--edgeCount;`
`143`	`145`	`}`
`144`	`146`	`if (isDirected()) { // In undirected graphs, the successor and predecessor sets are equal.`
`145`		`- for (N predecessor : connections.predecessors()) {`
	`147`	`+ // Since views are returned, we need to copy the predecessors that will be removed.`
	`148`	`+ // Thus we avoid modifying the underlying view while iterating over it.`
	`149`	`+ for (N predecessor : ImmutableList.copyOf(connections.predecessors())) {`
`146`	`150`	`// requireNonNull is safe because the node is a predecessor.`
`147`	`151`	`checkState(`
`148`	`152`	`requireNonNull(nodeConnections.getWithoutCaching(predecessor)).removeSuccessor(node)`
`149`	`153`	`!= null);`
	`154`	`+ connections.removePredecessor(predecessor);`
`150`	`155`	`--edgeCount;`
`151`	`156`	`}`
`152`	`157`	`}`