diff --git a/src/test/java/com/google/devtools/build/lib/analysis/BuildViewTest.java b/src/test/java/com/google/devtools/build/lib/analysis/BuildViewTest.java
index 75a5f67..f48c02c 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/BuildViewTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/BuildViewTest.java
@@ -53,9 +53,9 @@
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
-import com.google.devtools.build.skyframe.NotifyingGraph.EventType;
-import com.google.devtools.build.skyframe.NotifyingGraph.Listener;
-import com.google.devtools.build.skyframe.NotifyingGraph.Order;
+import com.google.devtools.build.skyframe.NotifyingHelper.EventType;
+import com.google.devtools.build.skyframe.NotifyingHelper.Listener;
+import com.google.devtools.build.skyframe.NotifyingHelper.Order;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.TrackingAwaiter;
 
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestBase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestBase.java
index be2f423..d8acbcf 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestBase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestBase.java
@@ -38,9 +38,9 @@
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
-import com.google.devtools.build.skyframe.DeterministicGraph;
+import com.google.devtools.build.skyframe.DeterministicHelper;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
-import com.google.devtools.build.skyframe.NotifyingGraph.Listener;
+import com.google.devtools.build.skyframe.NotifyingHelper.Listener;
 
 import java.util.ArrayList;
 import java.util.List;
@@ -131,7 +131,7 @@
     InMemoryMemoizingEvaluator memoizingEvaluator =
         (InMemoryMemoizingEvaluator) skyframeExecutor.getEvaluatorForTesting();
     memoizingEvaluator.injectGraphTransformerForTesting(
-        DeterministicGraph.makeTransformer(listener, deterministic));
+        DeterministicHelper.makeTransformer(listener, deterministic));
   }
 
   protected void runTestForMultiCpuAnalysisFailure(String badCpu, String goodCpu) throws Exception {
diff --git a/src/test/java/com/google/devtools/build/skyframe/BUILD b/src/test/java/com/google/devtools/build/skyframe/BUILD
index 21b6342..4286728 100644
--- a/src/test/java/com/google/devtools/build/skyframe/BUILD
+++ b/src/test/java/com/google/devtools/build/skyframe/BUILD
@@ -12,7 +12,7 @@
     "TrackingInvalidationReceiver.java",
     "WalkableGraphUtils.java",
     # Truth Subject, SubjectFactory, and Graph files.
-] + glob(["*Subject.java"]) + glob(["*SubjectFactory.java"]) + glob(["*Graph.java"])
+] + glob(["*Subject.java"]) + glob(["*SubjectFactory.java"]) + glob(["*Graph.java"]) + glob(["*Helper.java"])
 
 java_library(
     name = "testutil",
diff --git a/src/test/java/com/google/devtools/build/skyframe/DeterministicGraph.java b/src/test/java/com/google/devtools/build/skyframe/DeterministicGraph.java
deleted file mode 100644
index 85df5c5..0000000
--- a/src/test/java/com/google/devtools/build/skyframe/DeterministicGraph.java
+++ /dev/null
@@ -1,125 +0,0 @@
-// Copyright 2016 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//    http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.skyframe;
-
-import com.google.common.base.Function;
-import com.google.common.collect.Iterables;
-
-import java.util.Collection;
-import java.util.Comparator;
-import java.util.Map;
-import java.util.Set;
-import java.util.TreeMap;
-import java.util.TreeSet;
-
-import javax.annotation.Nullable;
-
-/**
- * {@link NotifyingGraph} that returns reverse deps, temporary direct deps, and the results of
- * batch requests ordered alphabetically by sky key string representation.
- */
-public class DeterministicGraph<TGraph extends ThinNodeQueryableGraph>
-    extends NotifyingGraph<TGraph> {
-  public static final Function<ThinNodeQueryableGraph, ProcessableGraph> MAKE_DETERMINISTIC =
-      new Function<ThinNodeQueryableGraph, ProcessableGraph>() {
-        @Override
-        public ProcessableGraph apply(ThinNodeQueryableGraph queryableGraph) {
-          if (queryableGraph instanceof InMemoryGraph) {
-            return new DeterministicInMemoryGraph((InMemoryGraph) queryableGraph);
-          } else {
-            return new DeterministicGraph<>(queryableGraph);
-          }
-        }
-      };
-
-  public static Function<ThinNodeQueryableGraph, ProcessableGraph> makeTransformer(
-      final Listener listener, boolean deterministic) {
-    if (deterministic) {
-      return new Function<ThinNodeQueryableGraph, ProcessableGraph>() {
-        @Override
-        public ProcessableGraph apply(ThinNodeQueryableGraph queryableGraph) {
-          if (queryableGraph instanceof InMemoryGraph) {
-            return new DeterministicInMemoryGraph((InMemoryGraph) queryableGraph, listener);
-          } else {
-            return new DeterministicGraph<>(queryableGraph, listener);
-          }
-        }
-      };
-    } else {
-      return NotifyingGraph.makeNotifyingTransformer(listener);
-    }
-  }
-
-  private static final Comparator<SkyKey> ALPHABETICAL_SKYKEY_COMPARATOR =
-      new Comparator<SkyKey>() {
-        @Override
-        public int compare(SkyKey o1, SkyKey o2) {
-          return o1.toString().compareTo(o2.toString());
-        }
-      };
-
-  DeterministicGraph(TGraph delegate, Listener listener) {
-    super(delegate, listener);
-  }
-
-  DeterministicGraph(TGraph delegate) {
-    super(delegate, NotifyingGraph.Listener.NULL_LISTENER);
-  }
-
-  @Nullable
-  @Override
-  protected DeterministicValueEntry wrapEntry(SkyKey key, @Nullable ThinNodeEntry entry) {
-    return entry == null ? null : new DeterministicValueEntry(key, entry);
-  }
-
-  private static Map<SkyKey, NodeEntry> makeDeterministic(Map<SkyKey, NodeEntry> map) {
-    Map<SkyKey, NodeEntry> result = new TreeMap<>(ALPHABETICAL_SKYKEY_COMPARATOR);
-    result.putAll(map);
-    return result;
-  }
-
-  @Override
-  public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) {
-    return makeDeterministic(super.getBatch(keys));
-  }
-
-  @Override
-  public Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys) {
-    return makeDeterministic(super.createIfAbsentBatch(keys));
-  }
-
-  /**
-   * This class uses TreeSet to store reverse dependencies of NodeEntry. As a result all values are
-   * lexicographically sorted.
-   */
-  private class DeterministicValueEntry extends NotifyingNodeEntry {
-    private DeterministicValueEntry(SkyKey myKey, ThinNodeEntry delegate) {
-      super(myKey, delegate);
-    }
-
-    @Override
-    public synchronized Collection<SkyKey> getReverseDeps() {
-      TreeSet<SkyKey> result = new TreeSet<>(ALPHABETICAL_SKYKEY_COMPARATOR);
-      Iterables.addAll(result, super.getReverseDeps());
-      return result;
-    }
-
-    @Override
-    public synchronized Set<SkyKey> getInProgressReverseDeps() {
-      TreeSet<SkyKey> result = new TreeSet<>(ALPHABETICAL_SKYKEY_COMPARATOR);
-      result.addAll(super.getInProgressReverseDeps());
-      return result;
-    }
-  }
-}
diff --git a/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java b/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java
new file mode 100644
index 0000000..655333a
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java
@@ -0,0 +1,146 @@
+// Copyright 2016 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.skyframe;
+
+import com.google.common.collect.Iterables;
+
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeMap;
+import java.util.TreeSet;
+
+import javax.annotation.Nullable;
+
+/**
+ * {@link NotifyingHelper} that returns reverse deps, temporary direct deps, and the results of
+ * batch requests ordered alphabetically by sky key string representation.
+ */
+public class DeterministicHelper extends NotifyingHelper {
+  static final MemoizingEvaluator.GraphTransformerForTesting MAKE_DETERMINISTIC =
+      makeTransformer(Listener.NULL_LISTENER, /*deterministic=*/ true);
+
+  public static MemoizingEvaluator.GraphTransformerForTesting makeTransformer(
+      final Listener listener, boolean deterministic) {
+    if (deterministic) {
+      return new MemoizingEvaluator.GraphTransformerForTesting() {
+        @Override
+        public InMemoryGraph transform(InMemoryGraph graph) {
+          return new DeterministicInMemoryGraph(graph, listener);
+        }
+
+        @Override
+        public InvalidatableGraph transform(InvalidatableGraph graph) {
+          return new DeterministicInvalidatableGraph(graph, listener);
+        }
+
+        @Override
+        public ProcessableGraph transform(ProcessableGraph graph) {
+          return new DeterministicProcessableGraph(graph, listener);
+        }
+      };
+    } else {
+      return NotifyingHelper.makeNotifyingTransformer(listener);
+    }
+  }
+
+  private static final Comparator<SkyKey> ALPHABETICAL_SKYKEY_COMPARATOR =
+      new Comparator<SkyKey>() {
+        @Override
+        public int compare(SkyKey o1, SkyKey o2) {
+          return o1.toString().compareTo(o2.toString());
+        }
+      };
+
+  DeterministicHelper(Listener listener) {
+    super(listener);
+  }
+
+  DeterministicHelper() {
+    super(NotifyingHelper.Listener.NULL_LISTENER);
+  }
+
+  @Nullable
+  @Override
+  protected DeterministicValueEntry wrapEntry(SkyKey key, @Nullable ThinNodeEntry entry) {
+    return entry == null ? null : new DeterministicValueEntry(key, entry);
+  }
+
+  private static Map<SkyKey, NodeEntry> makeDeterministic(Map<SkyKey, NodeEntry> map) {
+    Map<SkyKey, NodeEntry> result = new TreeMap<>(ALPHABETICAL_SKYKEY_COMPARATOR);
+    result.putAll(map);
+    return result;
+  }
+
+  private static class DeterministicInvalidatableGraph extends NotifyingInvalidatableGraph {
+    DeterministicInvalidatableGraph(InvalidatableGraph delegate, Listener graphListener) {
+      super(delegate, new DeterministicHelper(graphListener));
+    }
+
+    @Override
+    public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) {
+      return makeDeterministic(super.getBatch(keys));
+    }
+  }
+
+  static class DeterministicProcessableGraph extends NotifyingProcessableGraph {
+    DeterministicProcessableGraph(ProcessableGraph delegate, Listener graphListener) {
+      super(delegate, new DeterministicHelper(graphListener));
+    }
+
+    DeterministicProcessableGraph(ProcessableGraph delegate) {
+      this(delegate, Listener.NULL_LISTENER);
+    }
+
+    @Override
+    public void remove(SkyKey key) {
+      delegate.remove(key);
+    }
+
+    @Override
+    public Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys) {
+      return makeDeterministic(super.createIfAbsentBatch(keys));
+    }
+
+    @Override
+    public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) {
+      return makeDeterministic(super.getBatch(keys));
+    }
+  }
+
+  /**
+   * This class uses TreeSet to store reverse dependencies of NodeEntry. As a result all values are
+   * lexicographically sorted.
+   */
+  private class DeterministicValueEntry extends NotifyingNodeEntry {
+    private DeterministicValueEntry(SkyKey myKey, ThinNodeEntry delegate) {
+      super(myKey, delegate);
+    }
+
+    @Override
+    public synchronized Collection<SkyKey> getReverseDeps() {
+      TreeSet<SkyKey> result = new TreeSet<>(ALPHABETICAL_SKYKEY_COMPARATOR);
+      Iterables.addAll(result, super.getReverseDeps());
+      return result;
+    }
+
+    @Override
+    public synchronized Set<SkyKey> getInProgressReverseDeps() {
+      TreeSet<SkyKey> result = new TreeSet<>(ALPHABETICAL_SKYKEY_COMPARATOR);
+      result.addAll(super.getInProgressReverseDeps());
+      return result;
+    }
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java b/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
index 9e16284..a023383 100644
--- a/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
+++ b/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
@@ -16,32 +16,28 @@
 import java.util.Map;
 
 /**
- * {@link DeterministicGraph} that implements the {@link InMemoryGraph} interface. Sadly, cannot be
- * a {@link NotifyingInMemoryGraph} due to Java's forbidding multiple inheritance.
+ * {@link DeterministicHelper.DeterministicProcessableGraph} that implements the {@link
+ * InMemoryGraph} interface. Sadly, cannot be a {@link NotifyingInMemoryGraph} due to Java's
+ * forbidding multiple inheritance.
  */
-class DeterministicInMemoryGraph extends DeterministicGraph<InMemoryGraph>
+class DeterministicInMemoryGraph extends DeterministicHelper.DeterministicProcessableGraph
     implements InMemoryGraph {
-
-  DeterministicInMemoryGraph(InMemoryGraph delegate, Listener graphListener) {
+  DeterministicInMemoryGraph(InMemoryGraph delegate, NotifyingHelper.Listener graphListener) {
     super(delegate, graphListener);
   }
 
-  DeterministicInMemoryGraph(InMemoryGraph delegate) {
-    super(delegate);
-  }
-
   @Override
   public Map<SkyKey, SkyValue> getValues() {
-    return delegate.getValues();
+    return ((InMemoryGraph) delegate).getValues();
   }
 
   @Override
   public Map<SkyKey, SkyValue> getDoneValues() {
-    return delegate.getDoneValues();
+    return ((InMemoryGraph) delegate).getDoneValues();
   }
 
   @Override
   public Map<SkyKey, NodeEntry> getAllValues() {
-    return delegate.getAllValues();
+    return ((InMemoryGraph) delegate).getAllValues();
   }
 }
diff --git a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
index 1976988..dbc418f 100644
--- a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
@@ -84,8 +84,11 @@
   }
 
   @SuppressWarnings("unused") // Overridden by subclasses.
-  void invalidate(DirtiableGraph graph, EvaluationProgressReceiver invalidationReceiver,
-      SkyKey... keys) throws InterruptedException { throw new UnsupportedOperationException(); }
+  void invalidate(
+      InMemoryGraph graph, EvaluationProgressReceiver invalidationReceiver, SkyKey... keys)
+      throws InterruptedException {
+    throw new UnsupportedOperationException();
+  }
 
   boolean gcExpected() { throw new UnsupportedOperationException(); }
 
@@ -595,8 +598,9 @@
   @RunWith(JUnit4.class)
   public static class DeletingInvalidatorTest extends EagerInvalidatorTest {
     @Override
-    protected void invalidate(DirtiableGraph graph, EvaluationProgressReceiver invalidationReceiver,
-        SkyKey... keys) throws InterruptedException {
+    protected void invalidate(
+        InMemoryGraph graph, EvaluationProgressReceiver invalidationReceiver, SkyKey... keys)
+        throws InterruptedException {
       Iterable<SkyKey> diff = ImmutableList.copyOf(keys);
       DeletingNodeVisitor deletingNodeVisitor =
           EagerInvalidator.createDeletingVisitorIfNeeded(
@@ -665,8 +669,9 @@
   @RunWith(JUnit4.class)
   public static class DirtyingInvalidatorTest extends EagerInvalidatorTest {
     @Override
-    protected void invalidate(DirtiableGraph graph, EvaluationProgressReceiver invalidationReceiver,
-        SkyKey... keys) throws InterruptedException {
+    protected void invalidate(
+        InMemoryGraph graph, EvaluationProgressReceiver invalidationReceiver, SkyKey... keys)
+        throws InterruptedException {
       Iterable<SkyKey> diff = ImmutableList.copyOf(keys);
       DirtyingNodeVisitor dirtyingNodeVisitor =
           EagerInvalidator.createInvalidatingVisitorIfNeeded(
diff --git a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
index 61c9821..ffdad2a 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -51,9 +51,9 @@
 import com.google.devtools.build.skyframe.GraphTester.StringValue;
 import com.google.devtools.build.skyframe.GraphTester.TestFunction;
 import com.google.devtools.build.skyframe.GraphTester.ValueComputer;
-import com.google.devtools.build.skyframe.NotifyingGraph.EventType;
-import com.google.devtools.build.skyframe.NotifyingGraph.Listener;
-import com.google.devtools.build.skyframe.NotifyingGraph.Order;
+import com.google.devtools.build.skyframe.NotifyingHelper.EventType;
+import com.google.devtools.build.skyframe.NotifyingHelper.Listener;
+import com.google.devtools.build.skyframe.NotifyingHelper.Order;
 import com.google.devtools.build.skyframe.SkyFunction.Environment;
 import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
 
@@ -1248,7 +1248,7 @@
     // Mark dep1 changed, so otherTop will be dirty and request re-evaluation of dep1.
     tester.getOrCreate(dep1, /*markAsModified=*/true);
     SkyKey topKey = GraphTester.toSkyKey("top");
-    // Note that since DeterministicGraph alphabetizes reverse deps, it is important that
+    // Note that since DeterministicHelper alphabetizes reverse deps, it is important that
     // "cycle2" comes before "top".
     final SkyKey cycle1Key = GraphTester.toSkyKey("cycle1");
     final SkyKey cycle2Key = GraphTester.toSkyKey("cycle2");
@@ -4013,11 +4013,11 @@
 
   private void injectGraphListenerForTesting(Listener listener, boolean deterministic) {
     tester.evaluator.injectGraphTransformerForTesting(
-        DeterministicGraph.makeTransformer(listener, deterministic));
+        DeterministicHelper.makeTransformer(listener, deterministic));
   }
 
   private void makeGraphDeterministic() {
-    tester.evaluator.injectGraphTransformerForTesting(DeterministicGraph.MAKE_DETERMINISTIC);
+    tester.evaluator.injectGraphTransformerForTesting(DeterministicHelper.MAKE_DETERMINISTIC);
   }
 
   private static final class PassThroughSelected implements ValueComputer {
diff --git a/src/test/java/com/google/devtools/build/skyframe/NotifyingGraph.java b/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
similarity index 72%
rename from src/test/java/com/google/devtools/build/skyframe/NotifyingGraph.java
rename to src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
index 22dbc35..2f973b5 100644
--- a/src/test/java/com/google/devtools/build/skyframe/NotifyingGraph.java
+++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
-import com.google.common.base.Function;
 import com.google.common.base.Joiner;
 import com.google.common.base.MoreObjects;
 import com.google.common.collect.Maps;
@@ -28,36 +27,34 @@
 
 /**
  * Class that allows clients to be notified on each access of the graph. Clients can simply track
- * accesses, or they can block to achieve desired synchronization. Clients should call
- * {@link TrackingAwaiter#INSTANCE#assertNoErrors} at the end of tests in case exceptions were
- * swallowed in async threads.
- *
- * <p>While this class nominally always implements a {@link ProcessableGraph}, it will throw if any
- * of the methods in {@link ProcessableGraph} that are not in {@link ThinNodeQueryableGraph} are
- * called on it and its {@link #delegate} is not a {@link ProcessableGraph}. This lack of type
- * safety is so that a {@code NotifyingGraph} can be returned by {@link #makeNotifyingTransformer}
- * and used in {@link MemoizingEvaluator#injectGraphTransformerForTesting}.
+ * accesses, or they can block to achieve desired synchronization. Clients should call {@link
+ * TrackingAwaiter#INSTANCE#assertNoErrors} at the end of tests in case exceptions were swallowed in
+ * async threads.
  */
-public class NotifyingGraph<TGraph extends ThinNodeQueryableGraph> implements ProcessableGraph {
-  public static Function<ThinNodeQueryableGraph, ProcessableGraph> makeNotifyingTransformer(
+public class NotifyingHelper {
+  public static MemoizingEvaluator.GraphTransformerForTesting makeNotifyingTransformer(
       final Listener listener) {
-    return new Function<ThinNodeQueryableGraph, ProcessableGraph>() {
-      @Nullable
+    return new MemoizingEvaluator.GraphTransformerForTesting() {
       @Override
-      public ProcessableGraph apply(ThinNodeQueryableGraph queryableGraph) {
-        if (queryableGraph instanceof InMemoryGraph) {
-          return new NotifyingInMemoryGraph((InMemoryGraph) queryableGraph, listener);
-        } else {
-          return new NotifyingGraph<>(queryableGraph, listener);
-        }
+      public InMemoryGraph transform(InMemoryGraph graph) {
+        return new NotifyingInMemoryGraph(graph, listener);
+      }
+
+      @Override
+      public InvalidatableGraph transform(InvalidatableGraph graph) {
+        return new NotifyingInvalidatableGraph(graph, listener);
+      }
+
+      @Override
+      public ProcessableGraph transform(ProcessableGraph graph) {
+        return new NotifyingProcessableGraph(graph, listener);
       }
     };
   }
 
-  protected final TGraph delegate;
-  private final Listener graphListener;
+  protected final Listener graphListener;
 
-  private final EntryTransformer<SkyKey, ThinNodeEntry, NodeEntry> wrapEntry =
+  protected final EntryTransformer<SkyKey, ThinNodeEntry, NodeEntry> wrapEntry =
       new EntryTransformer<SkyKey, ThinNodeEntry, NodeEntry>() {
         @Nullable
         @Override
@@ -66,49 +63,75 @@
         }
       };
 
-  NotifyingGraph(TGraph delegate, Listener graphListener) {
-    this.delegate = delegate;
+  NotifyingHelper(Listener graphListener) {
     this.graphListener = new ErrorRecordingDelegatingListener(graphListener);
   }
 
-  private ProcessableGraph getProcessableDelegate() {
-    return (ProcessableGraph) delegate;
-  }
-
-  @Override
-  public void remove(SkyKey key) {
-    getProcessableDelegate().remove(key);
-  }
-
-  @Override
-  public Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys) {
-    for (SkyKey key : keys) {
-      graphListener.accept(key, EventType.CREATE_IF_ABSENT, Order.BEFORE, null);
-    }
-    return Maps.transformEntries(getProcessableDelegate().createIfAbsentBatch(keys), wrapEntry);
-  }
-
-  @Override
-  public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) {
-    if (delegate instanceof ProcessableGraph) {
-      return Maps.transformEntries(getProcessableDelegate().getBatch(keys), wrapEntry);
-    } else {
-      return Maps.transformEntries(delegate.getBatch(keys), wrapEntry);
-    }
-  }
-
-  @Nullable
-  @Override
-  public NodeEntry get(SkyKey key) {
-    return wrapEntry(key, getProcessableDelegate().get(key));
-  }
-
   /** Subclasses should override if they wish to subclass NotifyingNodeEntry. */
   @Nullable
   protected NotifyingNodeEntry wrapEntry(SkyKey key, @Nullable ThinNodeEntry entry) {
     return entry == null ? null : new NotifyingNodeEntry(key, entry);
   }
 
+  static class NotifyingInvalidatableGraph implements InvalidatableGraph {
+    private final InvalidatableGraph delegate;
+    private final NotifyingHelper notifyingHelper;
+
+    NotifyingInvalidatableGraph(InvalidatableGraph delegate, Listener graphListener) {
+      this.notifyingHelper = new NotifyingHelper(graphListener);
+      this.delegate = delegate;
+    }
+
+    NotifyingInvalidatableGraph(InvalidatableGraph delegate, NotifyingHelper helper) {
+      this.notifyingHelper = helper;
+      this.delegate = delegate;
+    }
+
+    @Override
+    public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) {
+      return Maps.transformEntries(delegate.getBatch(keys), notifyingHelper.wrapEntry);
+    }
+  }
+
+  static class NotifyingProcessableGraph implements ProcessableGraph {
+    protected final ProcessableGraph delegate;
+    protected final NotifyingHelper notifyingHelper;
+
+    NotifyingProcessableGraph(ProcessableGraph delegate, Listener graphListener) {
+      this.notifyingHelper = new NotifyingHelper(graphListener);
+      this.delegate = delegate;
+    }
+
+    NotifyingProcessableGraph(ProcessableGraph delegate, NotifyingHelper helper) {
+      this.notifyingHelper = helper;
+      this.delegate = delegate;
+    }
+
+    @Override
+    public void remove(SkyKey key) {
+      delegate.remove(key);
+    }
+
+    @Override
+    public Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys) {
+      for (SkyKey key : keys) {
+        notifyingHelper.graphListener.accept(key, EventType.CREATE_IF_ABSENT, Order.BEFORE, null);
+      }
+      return Maps.transformEntries(delegate.createIfAbsentBatch(keys), notifyingHelper.wrapEntry);
+    }
+
+    @Override
+    public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) {
+      return Maps.transformEntries(delegate.getBatch(keys), notifyingHelper.wrapEntry);
+    }
+
+    @Nullable
+    @Override
+    public NodeEntry get(SkyKey key) {
+      return notifyingHelper.wrapEntry(key, delegate.get(key));
+    }
+  }
+
   /**
    * Graph/value entry events that the receiver can be informed of. When writing tests, feel free to
    * add additional events here if needed.
diff --git a/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java b/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
index 9b90491..752dac7 100644
--- a/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
+++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
@@ -15,24 +15,25 @@
 
 import java.util.Map;
 
-/** {@link NotifyingGraph} that additionally implements the {@link InMemoryGraph} interface. */
-class NotifyingInMemoryGraph extends NotifyingGraph<InMemoryGraph> implements InMemoryGraph {
-  NotifyingInMemoryGraph(InMemoryGraph delegate, Listener graphListener) {
+/** {@link NotifyingHelper} that additionally implements the {@link InMemoryGraph} interface. */
+class NotifyingInMemoryGraph extends NotifyingHelper.NotifyingProcessableGraph
+    implements InMemoryGraph {
+  NotifyingInMemoryGraph(InMemoryGraph delegate, NotifyingHelper.Listener graphListener) {
     super(delegate, graphListener);
   }
 
   @Override
   public Map<SkyKey, SkyValue> getValues() {
-    return delegate.getValues();
+    return ((InMemoryGraph) delegate).getValues();
   }
 
   @Override
   public Map<SkyKey, SkyValue> getDoneValues() {
-    return delegate.getDoneValues();
+    return ((InMemoryGraph) delegate).getDoneValues();
   }
 
   @Override
   public Map<SkyKey, NodeEntry> getAllValues() {
-    return delegate.getAllValues();
+    return ((InMemoryGraph) delegate).getAllValues();
   }
 }
diff --git a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
index 0b3d8fc..56dcfb5 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
@@ -43,9 +43,9 @@
 import com.google.devtools.build.lib.testutil.TestThread;
 import com.google.devtools.build.lib.testutil.TestUtils;
 import com.google.devtools.build.skyframe.GraphTester.StringValue;
-import com.google.devtools.build.skyframe.NotifyingGraph.EventType;
-import com.google.devtools.build.skyframe.NotifyingGraph.Listener;
-import com.google.devtools.build.skyframe.NotifyingGraph.Order;
+import com.google.devtools.build.skyframe.NotifyingHelper.EventType;
+import com.google.devtools.build.skyframe.NotifyingHelper.Listener;
+import com.google.devtools.build.skyframe.NotifyingHelper.Order;
 import com.google.devtools.build.skyframe.ParallelEvaluator.EventFilter;
 import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
 
@@ -1276,7 +1276,7 @@
    * we should detect cycle.
    */
   private void cycleAndErrorInBubbleUp(boolean keepGoing) throws Exception {
-    graph = new DeterministicGraph<>(new InMemoryGraphImpl());
+    graph = new DeterministicHelper.DeterministicProcessableGraph(new InMemoryGraphImpl());
     tester = new GraphTester();
     SkyKey errorKey = GraphTester.toSkyKey("error");
     SkyKey cycleKey = GraphTester.toSkyKey("cycle");
@@ -1323,7 +1323,7 @@
    */
   @Test
   public void cycleAndErrorAndOtherInBubbleUp() throws Exception {
-    graph = new DeterministicGraph<>(new InMemoryGraphImpl());
+    graph = new DeterministicHelper.DeterministicProcessableGraph(new InMemoryGraphImpl());
     tester = new GraphTester();
     SkyKey errorKey = GraphTester.toSkyKey("error");
     SkyKey cycleKey = GraphTester.toSkyKey("cycle");
@@ -1366,7 +1366,7 @@
    * Here, we add an additional top-level key in error, just to mix it up.
    */
   private void cycleAndErrorAndError(boolean keepGoing) throws Exception {
-    graph = new DeterministicGraph<>(new InMemoryGraphImpl());
+    graph = new DeterministicHelper.DeterministicProcessableGraph(new InMemoryGraphImpl());
     tester = new GraphTester();
     SkyKey errorKey = GraphTester.toSkyKey("error");
     SkyKey cycleKey = GraphTester.toSkyKey("cycle");
@@ -1999,7 +1999,7 @@
       }
     });
     graph =
-        new NotifyingGraph<>(
+        new NotifyingHelper.NotifyingProcessableGraph(
             new InMemoryGraphImpl(),
             new Listener() {
               @Override
@@ -2032,7 +2032,7 @@
 
   @Test
   public void cachedErrorsFromKeepGoingUsedOnNoKeepGoing() throws Exception {
-    graph = new DeterministicGraph<>(new InMemoryGraphImpl());
+    graph = new DeterministicHelper.DeterministicProcessableGraph(new InMemoryGraphImpl());
     tester = new GraphTester();
     SkyKey errorKey = GraphTester.toSkyKey("error");
     SkyKey parent1Key = GraphTester.toSkyKey("parent1");
@@ -2052,7 +2052,7 @@
 
   @Test
   public void cachedTopLevelErrorsShouldHaltNoKeepGoingBuildEarly() throws Exception {
-    graph = new DeterministicGraph<>(new InMemoryGraphImpl());
+    graph = new DeterministicHelper.DeterministicProcessableGraph(new InMemoryGraphImpl());
     tester = new GraphTester();
     SkyKey errorKey = GraphTester.toSkyKey("error");
     tester.getOrCreate(errorKey).setHasError(true);
@@ -2082,7 +2082,7 @@
 
   private void runUnhandledTransitiveErrors(boolean keepGoing,
       final boolean explicitlyPropagateError) throws Exception {
-    graph = new DeterministicGraph<>(new InMemoryGraphImpl());
+    graph = new DeterministicHelper.DeterministicProcessableGraph(new InMemoryGraphImpl());
     tester = new GraphTester();
     SkyKey grandparentKey = GraphTester.toSkyKey("grandparent");
     final SkyKey parentKey = GraphTester.toSkyKey("parent");