diff --git a/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java
index e7992f4..a5c6d1d 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java
@@ -195,29 +195,19 @@
   }
 
   @Override
-  public Collection<Target> getFwdDeps(Target target) {
-    return getTargetsFromNodes(getNode(target).getSuccessors());
-  }
-
-  @Override
   public Collection<Target> getFwdDeps(Iterable<Target> targets) {
     Set<Target> result = new HashSet<>();
     for (Target target : targets) {
-      result.addAll(getFwdDeps(target));
+      result.addAll(getTargetsFromNodes(getNode(target).getSuccessors()));
     }
     return result;
   }
 
   @Override
-  public Collection<Target> getReverseDeps(Target target) {
-    return getTargetsFromNodes(getNode(target).getPredecessors());
-  }
-
-  @Override
   public Collection<Target> getReverseDeps(Iterable<Target> targets) {
     Set<Target> result = new HashSet<>();
     for (Target target : targets) {
-      result.addAll(getReverseDeps(target));
+      result.addAll(getTargetsFromNodes(getNode(target).getPredecessors()));
     }
     return result;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
index 00ddd2b..473c69d 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
@@ -19,6 +19,7 @@
 import com.google.common.base.Predicates;
 import com.google.common.base.Supplier;
 import com.google.common.collect.Collections2;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
@@ -126,10 +127,6 @@
     return TransitiveTargetValue.key(value.getLabel());
   }
 
-  private Collection<Target> getRawFwdDeps(Target target) {
-    return makeTargets(graph.getDirectDeps(makeKey(target)));
-  }
-
   private Map<Target, Collection<Target>> makeTargetsMap(Map<SkyKey, Iterable<SkyKey>> input) {
     ImmutableMap.Builder<Target, Collection<Target>> result = ImmutableMap.builder();
 
@@ -143,10 +140,6 @@
     return makeTargetsMap(graph.getDirectDeps(makeKeys(targets)));
   }
 
-  private Collection<Target> getRawReverseDeps(Target target) {
-    return makeTargets(graph.getReverseDeps(makeKey(target)));
-  }
-
   private Map<Target, Collection<Target>> getRawReverseDeps(Iterable<Target> targets) {
     return makeTargetsMap(graph.getReverseDeps(makeKeys(targets)));
   }
@@ -174,11 +167,6 @@
   }
 
   @Override
-  public Collection<Target> getFwdDeps(Target target) {
-    return filterFwdDeps(target, getRawFwdDeps(target));
-  }
-
-  @Override
   public Collection<Target> getFwdDeps(Iterable<Target> targets) {
     Set<Target> result = new HashSet<>();
     for (Map.Entry<Target, Collection<Target>> entry : getRawFwdDeps(targets).entrySet()) {
@@ -200,11 +188,6 @@
   }
 
   @Override
-  public Collection<Target> getReverseDeps(Target target) {
-    return filterReverseDeps(target, getRawReverseDeps(target));
-  }
-
-  @Override
   public Collection<Target> getReverseDeps(Iterable<Target> targets) {
     Set<Target> result = new HashSet<>();
     for (Map.Entry<Target, Collection<Target>> entry : getRawReverseDeps(targets).entrySet()) {
@@ -240,7 +223,7 @@
       if (to.equals(current)) {
         return ImmutableSet.copyOf(Digraph.getPathToTreeNode(nodeToParent, to));
       }
-      for (Target dep : getFwdDeps(current)) {
+      for (Target dep : getFwdDeps(ImmutableList.of(current))) {
         if (!nodeToParent.containsKey(dep)) {
           nodeToParent.put(dep, current);
           toVisit.addFirst(dep);
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java
index d2d5f05..4920298 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java
@@ -19,8 +19,9 @@
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
 
+import java.util.ArrayList;
+import java.util.Collection;
 import java.util.HashSet;
-import java.util.LinkedList;
 import java.util.List;
 import java.util.Set;
 
@@ -65,11 +66,11 @@
 
     Set<T> reachableFromX = env.getTransitiveClosure(fromValue);
     Set<T> result = intersection(reachableFromX, toValue);
-    LinkedList<T> worklist = new LinkedList<>(result);
-
-    T n;
-    while ((n = worklist.poll()) != null) {
-      for (T np : env.getReverseDeps(n)) {
+    Collection<T> worklist = result;
+    while (!worklist.isEmpty()) {
+      Collection<T> reverseDeps = env.getReverseDeps(worklist);
+      worklist = new ArrayList<>();
+      for (T np : reverseDeps) {
         if (reachableFromX.contains(np)) {
           if (result.add(np)) {
             worklist.add(np);
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java
index a6d6156..78812cc 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java
@@ -152,15 +152,9 @@
   // be possible to remove it.
   T getOrCreate(T target);
 
-  /** Returns the direct forward dependencies of the specified target. */
-  Collection<T> getFwdDeps(T target);
-
   /** Returns the direct forward dependencies of the specified targets. */
   Collection<T> getFwdDeps(Iterable<T> targets);
 
-  /** Returns the direct reverse dependencies of the specified target. */
-  Collection<T> getReverseDeps(T target);
-
   /** Returns the direct reverse dependencies of the specified targets. */
   Collection<T> getReverseDeps(Iterable<T> targets);
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
index fee4f9c..b88b8903 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
@@ -82,11 +82,6 @@
     return errorInfo == null ? null : errorInfo.getException();
   }
 
-  @Override
-  public Iterable<SkyKey> getDirectDeps(SkyKey key) {
-    return getEntry(key).getDirectDeps();
-  }
-
   private static final Function<NodeEntry, Iterable<SkyKey>> GET_DIRECT_DEPS_FUNCTION =
       new Function<NodeEntry, Iterable<SkyKey>>() {
         @Override
@@ -100,11 +95,6 @@
     return Maps.transformValues(getEntries(keys), GET_DIRECT_DEPS_FUNCTION);
   }
 
-  @Override
-  public Iterable<SkyKey> getReverseDeps(SkyKey key) {
-    return getEntry(key).getReverseDeps();
-  }
-
   private static final Function<NodeEntry, Iterable<SkyKey>> GET_REVERSE_DEPS_FUNCTION =
       new Function<NodeEntry, Iterable<SkyKey>>() {
         @Override
diff --git a/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
index e020a26..be68248 100644
--- a/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
@@ -48,31 +48,20 @@
 
   /**
    * Returns the exception thrown when computing the node with the given key, if any. If the node
-   * was computed successfully, returns null. A node with this key must exist in the graph.
+   * was computed successfully, returns null. A node with this key must exist and be done in the
+   * graph.
    */
   @Nullable Exception getException(SkyKey key);
 
   /**
-   * Returns the direct dependencies of the node with the given key. A node with this key must exist
-   * in the graph.
-   */
-  Iterable<SkyKey> getDirectDeps(SkyKey key);
-
-  /**
-   * Returns a map giving the direct dependencies of the nodes with the given keys. Same semantics
-   * as {@link #getDirectDeps(SkyKey)}.
+   * Returns a map giving the direct dependencies of the nodes with the given keys. A node for each
+   * given key must exist and be done in the graph.
    */
   Map<SkyKey, Iterable<SkyKey>> getDirectDeps(Iterable<SkyKey> keys);
 
-    /**
-     * Returns the reverse dependencies of the node with the given key. A node with this key must
-     * exist in the graph.
-     */
-  Iterable<SkyKey> getReverseDeps(SkyKey key);
-
   /**
-   * Returns a map giving the reverse dependencies of the nodes with the given keys. Same semantics
-   * as {@link #getReverseDeps(SkyKey)}.
+   * Returns a map giving the reverse dependencies of the nodes with the given keys. A node for each
+   * given key must exist and be done in the graph.
    */
   Map<SkyKey, Iterable<SkyKey>> getReverseDeps(Iterable<SkyKey> keys);