diff --git a/src/com/facebook/buck/android/AndroidBinaryRule.java b/src/com/facebook/buck/android/AndroidBinaryRule.java
index e5a1bc3..595afd2 100644
--- a/src/com/facebook/buck/android/AndroidBinaryRule.java
+++ b/src/com/facebook/buck/android/AndroidBinaryRule.java
@@ -38,7 +38,6 @@
 import com.facebook.buck.rules.Buildable;
 import com.facebook.buck.rules.BuildableContext;
 import com.facebook.buck.rules.BuildableProperties;
-import com.facebook.buck.rules.DependencyGraph;
 import com.facebook.buck.rules.DoNotUseAbstractBuildable;
 import com.facebook.buck.rules.InstallableBuildRule;
 import com.facebook.buck.rules.RuleKey;
@@ -477,11 +476,10 @@
     steps.add(new MkdirAndSymlinkFileStep(getManifest().resolve(context).toString(),
         getAndroidManifestXml()));
 
-    final AndroidTransitiveDependencies transitiveDependencies = findTransitiveDependencies(
-        context.getDependencyGraph());
+    final AndroidTransitiveDependencies transitiveDependencies = findTransitiveDependencies();
 
     final AndroidDexTransitiveDependencies dexTransitiveDependencies =
-        findDexTransitiveDependencies(context.getDependencyGraph());
+        findDexTransitiveDependencies();
 
     // Add the steps for the aapt_package command. This method returns data that the ApkBuilder
     // needs to create a final, unsigned APK.
@@ -866,13 +864,13 @@
     return Optional.of(destination);
   }
 
-  public AndroidTransitiveDependencies findTransitiveDependencies(DependencyGraph graph) {
-    return getTransitiveDependencyGraph().findDependencies(getAndroidResourceDepsInternal(graph));
+  public AndroidTransitiveDependencies findTransitiveDependencies() {
+    return getTransitiveDependencyGraph().findDependencies(getAndroidResourceDepsInternal());
   }
 
-  public AndroidDexTransitiveDependencies findDexTransitiveDependencies(DependencyGraph graph) {
+  public AndroidDexTransitiveDependencies findDexTransitiveDependencies() {
     return getTransitiveDependencyGraph().findDexDependencies(
-        getAndroidResourceDepsInternal(graph),
+        getAndroidResourceDepsInternal(),
         buildRulesToExcludeFromDex);
   }
 
@@ -880,9 +878,8 @@
    * @return a list of {@link HasAndroidResourceDeps}s that should be passed, in order, to {@code aapt}
    *     when generating the {@code R.java} files for this APK.
    */
-  protected ImmutableList<HasAndroidResourceDeps> getAndroidResourceDepsInternal(
-      DependencyGraph graph) {
-    return UberRDotJavaUtil.getAndroidResourceDeps(this, graph);
+  protected ImmutableList<HasAndroidResourceDeps> getAndroidResourceDepsInternal() {
+    return UberRDotJavaUtil.getAndroidResourceDeps(this);
   }
 
   private boolean canSkipAaptResourcePackaging() {
diff --git a/src/com/facebook/buck/android/AndroidInstrumentationApk.java b/src/com/facebook/buck/android/AndroidInstrumentationApk.java
index 356b035..4b791bb 100644
--- a/src/com/facebook/buck/android/AndroidInstrumentationApk.java
+++ b/src/com/facebook/buck/android/AndroidInstrumentationApk.java
@@ -25,7 +25,6 @@
 import com.facebook.buck.rules.BuildRuleParams;
 import com.facebook.buck.rules.BuildRuleResolver;
 import com.facebook.buck.rules.BuildRuleType;
-import com.facebook.buck.rules.DependencyGraph;
 import com.facebook.buck.rules.InstallableBuildRule;
 import com.facebook.buck.rules.RuleKey;
 import com.facebook.buck.rules.SourcePath;
@@ -105,13 +104,12 @@
   }
 
   @Override
-  protected ImmutableList<HasAndroidResourceDeps> getAndroidResourceDepsInternal(
-      DependencyGraph graph) {
+  protected ImmutableList<HasAndroidResourceDeps> getAndroidResourceDepsInternal() {
     // Filter out the AndroidResourceRules that are needed by this APK but not the APK under test.
     ImmutableSet<HasAndroidResourceDeps> originalResources = ImmutableSet.copyOf(
-        UberRDotJavaUtil.getAndroidResourceDeps(apkUnderTest, graph));
+        UberRDotJavaUtil.getAndroidResourceDeps(apkUnderTest));
     ImmutableList<HasAndroidResourceDeps> instrumentationResources =
-        UberRDotJavaUtil.getAndroidResourceDeps(this, graph);
+        UberRDotJavaUtil.getAndroidResourceDeps(this);
 
     // Include all of the instrumentation resources first, in their original order.
     ImmutableList.Builder<HasAndroidResourceDeps> allResources = ImmutableList.builder();
diff --git a/src/com/facebook/buck/android/AndroidManifest.java b/src/com/facebook/buck/android/AndroidManifest.java
index fb7270d..bc85177 100644
--- a/src/com/facebook/buck/android/AndroidManifest.java
+++ b/src/com/facebook/buck/android/AndroidManifest.java
@@ -116,10 +116,9 @@
    * @return a list of {@link AndroidResourceRule}s that should be passed,
    * in order, to {@code aapt} when generating the {@code R.java} files for this APK.
    */
-  private ImmutableList<HasAndroidResourceDeps> getAndroidResourceDeps(
-      DependencyGraph graph) {
+  private ImmutableList<HasAndroidResourceDeps> getAndroidResourceDeps(DependencyGraph graph) {
     BuildRule self = graph.findBuildRuleByTarget(buildTarget);
-    return UberRDotJavaUtil.getAndroidResourceDeps(self, graph);
+    return UberRDotJavaUtil.getAndroidResourceDeps(self);
   }
 
   public static Builder newManifestMergeRuleBuilder(AbstractBuildRuleBuilderParams params) {
diff --git a/src/com/facebook/buck/android/AndroidResourceRule.java b/src/com/facebook/buck/android/AndroidResourceRule.java
index e4a6e58..1e228c9 100644
--- a/src/com/facebook/buck/android/AndroidResourceRule.java
+++ b/src/com/facebook/buck/android/AndroidResourceRule.java
@@ -172,7 +172,7 @@
 
     // Searching through the deps, find any additional res directories to pass to aapt.
     ImmutableList<HasAndroidResourceDeps> androidResourceDeps = UberRDotJavaUtil.getAndroidResourceDeps(
-        this, context.getDependencyGraph());
+        this);
     Set<String> resDirectories = ImmutableSet.copyOf(
         Iterables.transform(androidResourceDeps, GET_RES_FOR_RULE));
 
diff --git a/src/com/facebook/buck/android/UberRDotJavaUtil.java b/src/com/facebook/buck/android/UberRDotJavaUtil.java
index ebf81c1..a725aa3 100644
--- a/src/com/facebook/buck/android/UberRDotJavaUtil.java
+++ b/src/com/facebook/buck/android/UberRDotJavaUtil.java
@@ -16,6 +16,9 @@
 
 package com.facebook.buck.android;
 
+import com.facebook.buck.graph.DefaultImmutableDirectedAcyclicGraph;
+import com.facebook.buck.graph.ImmutableDirectedAcyclicGraph;
+import com.facebook.buck.graph.MutableDirectedGraph;
 import com.facebook.buck.graph.TopologicalSort;
 import com.facebook.buck.java.JavacInMemoryStep;
 import com.facebook.buck.java.JavacOptions;
@@ -24,7 +27,6 @@
 import com.facebook.buck.rules.BuildDependencies;
 import com.facebook.buck.rules.BuildRule;
 import com.facebook.buck.rules.BuildRuleType;
-import com.facebook.buck.rules.DependencyGraph;
 import com.facebook.buck.step.Step;
 import com.facebook.buck.step.fs.MakeCleanDirectoryStep;
 import com.facebook.buck.step.fs.WriteFileStep;
@@ -39,6 +41,8 @@
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 
+import java.util.Collection;
+import java.util.Collections;
 import java.util.Iterator;
 import java.util.Map;
 import java.util.Set;
@@ -122,13 +126,55 @@
   /**
    * Finds the transitive set of {@code rule}'s {@link AndroidResourceRule} dependencies with
    * non-null {@code res} directories, which can also include {@code rule} itself.
-   * This set will be returned as an {@link ImmutableList} with the rules topologically sorted as
-   * determined by {@code graph}. Rules will be ordered from least dependent to most dependent.
+   * This set will be returned as an {@link ImmutableList} with the rules topologically sorted.
+   * Rules will be ordered from least dependent to most dependent.
+   */
+  public static ImmutableList<HasAndroidResourceDeps> getAndroidResourceDeps(BuildRule rule) {
+    return getAndroidResourceDeps(Collections.singleton(rule));
+  }
+
+  /**
+   * Finds the transitive set of {@code rules}' {@link AndroidResourceRule} dependencies with
+   * non-null {@code res} directories, which can also include any of the {@code rules} themselves.
+   * This set will be returned as an {@link ImmutableList} with the rules topologically sorted.
+   * Rules will be ordered from least dependent to most dependent.
    */
   public static ImmutableList<HasAndroidResourceDeps> getAndroidResourceDeps(
-      BuildRule rule,
-      DependencyGraph graph) {
-    final Set<HasAndroidResourceDeps> allAndroidResourceRules = findAllAndroidResourceDeps(rule);
+      Collection<BuildRule> rules) {
+    // This visitor finds all AndroidResourceRules that are reachable from the specified rules via
+    // rules with types in the TRAVERSABLE_TYPES collection. It also builds up the dependency graph
+    // that was traversed to find the AndroidResourceRules.
+    final MutableDirectedGraph<BuildRule> mutableGraph = new MutableDirectedGraph<>();
+    final ImmutableSet.Builder<HasAndroidResourceDeps> androidResources = ImmutableSet.builder();
+    AbstractDependencyVisitor visitor = new AbstractDependencyVisitor(rules) {
+
+      @Override
+      public ImmutableSet<BuildRule> visit(BuildRule rule) {
+        mutableGraph.addNode(rule);
+
+        if (rule instanceof HasAndroidResourceDeps) {
+          HasAndroidResourceDeps androidResourceRule = (HasAndroidResourceDeps)rule;
+          if (androidResourceRule.getRes() != null) {
+            androidResources.add(androidResourceRule);
+          }
+        }
+
+        // Only certain types of rules should be considered as part of this traversal.
+        BuildRuleType type = rule.getType();
+        ImmutableSet<BuildRule> depsToVisit = maybeVisitAllDeps(rule,
+            TRAVERSABLE_TYPES.contains(type));
+        for (BuildRule dep : depsToVisit) {
+          mutableGraph.addEdge(rule, dep);
+        }
+        return depsToVisit;
+      }
+
+    };
+    visitor.start();
+
+    final Set<HasAndroidResourceDeps> allAndroidResourceRules = androidResources.build();
+    final ImmutableDirectedAcyclicGraph<BuildRule> graph =
+        new DefaultImmutableDirectedAcyclicGraph<>(mutableGraph);
 
     // Now that we have the transitive set of AndroidResourceRules, we need to return them in
     // topologically sorted order. This is critical because the order in which -S flags are passed
@@ -160,30 +206,6 @@
         }
       };
 
-  private static ImmutableSet<HasAndroidResourceDeps> findAllAndroidResourceDeps(BuildRule buildRule) {
-    final ImmutableSet.Builder<HasAndroidResourceDeps> androidResources = ImmutableSet.builder();
-    AbstractDependencyVisitor visitor = new AbstractDependencyVisitor(buildRule) {
-
-      @Override
-      public ImmutableSet<BuildRule> visit(BuildRule rule) {
-        if (rule instanceof HasAndroidResourceDeps) {
-          HasAndroidResourceDeps androidResourceRule = (HasAndroidResourceDeps)rule;
-          if (androidResourceRule.getRes() != null) {
-            androidResources.add(androidResourceRule);
-          }
-        }
-
-        // Only certain types of rules should be considered as part of this traversal.
-        BuildRuleType type = rule.getType();
-        return maybeVisitAllDeps(rule, TRAVERSABLE_TYPES.contains(type));
-      }
-
-    };
-    visitor.start();
-
-    return androidResources.build();
-  }
-
   /**
    * Aggregate information about a list of {@link AndroidResourceRule}s.
    */
diff --git a/src/com/facebook/buck/command/Project.java b/src/com/facebook/buck/command/Project.java
index a6c2e90..2f88689 100644
--- a/src/com/facebook/buck/command/Project.java
+++ b/src/com/facebook/buck/command/Project.java
@@ -350,7 +350,7 @@
       if (srcRule instanceof AndroidBinaryRule) {
         AndroidBinaryRule androidBinary = (AndroidBinaryRule)srcRule;
         AndroidDexTransitiveDependencies binaryDexTransitiveDependencies =
-            androidBinary.findDexTransitiveDependencies(dependencyGraph);
+            androidBinary.findDexTransitiveDependencies();
         noDxJarsBuilder.addAll(binaryDexTransitiveDependencies.noDxClasspathEntries);
       }
 
@@ -360,7 +360,7 @@
     ImmutableSet<String> noDxJars = noDxJarsBuilder.build();
 
     // Update module dependencies to apply scope="PROVIDED", where appropriate.
-    markNoDxJarsAsProvided(modules, noDxJars, dependencyGraph);
+    markNoDxJarsAsProvided(modules, noDxJars);
 
     return modules;
   }
@@ -664,10 +664,7 @@
    * to the android_binary that <em>does not</em> list the library in its {@code no_dx} list.
    */
   @VisibleForTesting
-  static void markNoDxJarsAsProvided(
-      List<Module> modules,
-      Set<String> noDxJars,
-        DependencyGraph dependencyGraph) {
+  static void markNoDxJarsAsProvided(List<Module> modules, Set<String> noDxJars) {
   Map<String, String> intelliJLibraryNameToJarPath = Maps.newHashMap();
     for (String jarPath : noDxJars) {
       String libraryName = getIntellijNameForBinaryJar(jarPath);
@@ -683,7 +680,7 @@
       if (module.srcRule instanceof AndroidBinaryRule) {
         AndroidBinaryRule androidBinaryRule = (AndroidBinaryRule)module.srcRule;
         AndroidDexTransitiveDependencies dexTransitiveDependencies =
-            androidBinaryRule.findDexTransitiveDependencies(dependencyGraph);
+            androidBinaryRule.findDexTransitiveDependencies();
         classpathEntriesToDex = Sets.newHashSet(Sets.intersection(noDxJars,
             dexTransitiveDependencies.classpathEntriesToDex));
       } else {
diff --git a/src/com/facebook/buck/java/DefaultJavaLibraryRule.java b/src/com/facebook/buck/java/DefaultJavaLibraryRule.java
index b9c9fee..952f695 100644
--- a/src/com/facebook/buck/java/DefaultJavaLibraryRule.java
+++ b/src/com/facebook/buck/java/DefaultJavaLibraryRule.java
@@ -518,8 +518,7 @@
 
     // If this rule depends on AndroidResourceRules, then we need to generate the R.java files that
     // this rule needs in order to be able to compile itself.
-    androidResourceDeps = UberRDotJavaUtil.getAndroidResourceDeps(this,
-        context.getDependencyGraph());
+    androidResourceDeps = UberRDotJavaUtil.getAndroidResourceDeps(this);
     boolean dependsOnAndroidResourceRules = !androidResourceDeps.isEmpty();
     if (dependsOnAndroidResourceRules) {
       UberRDotJavaUtil.createDummyRDotJavaFiles(androidResourceDeps, buildTarget, commands);
diff --git a/src/com/facebook/buck/java/JavaTestRule.java b/src/com/facebook/buck/java/JavaTestRule.java
index dc091d8..76efdb3 100644
--- a/src/com/facebook/buck/java/JavaTestRule.java
+++ b/src/com/facebook/buck/java/JavaTestRule.java
@@ -153,8 +153,7 @@
 
     // androidResourceDeps will be null if this test is re-run without being rebuilt.
     if (androidResourceDeps == null) {
-      androidResourceDeps = UberRDotJavaUtil.getAndroidResourceDeps(this,
-          buildContext.getDependencyGraph());
+      androidResourceDeps = UberRDotJavaUtil.getAndroidResourceDeps(this);
     }
 
     ImmutableList.Builder<Step> steps = ImmutableList.builder();
diff --git a/test/com/facebook/buck/android/AndroidBinaryRuleTest.java b/test/com/facebook/buck/android/AndroidBinaryRuleTest.java
index 26277f4..ed8849f 100644
--- a/test/com/facebook/buck/android/AndroidBinaryRuleTest.java
+++ b/test/com/facebook/buck/android/AndroidBinaryRuleTest.java
@@ -36,7 +36,6 @@
 import com.facebook.buck.rules.BuildContext;
 import com.facebook.buck.rules.BuildRule;
 import com.facebook.buck.rules.BuildRuleResolver;
-import com.facebook.buck.rules.DependencyGraph;
 import com.facebook.buck.rules.FakeAbstractBuildRuleBuilderParams;
 import com.facebook.buck.rules.FileSourcePath;
 import com.facebook.buck.rules.SourcePath;
@@ -45,7 +44,6 @@
 import com.facebook.buck.step.fs.MakeCleanDirectoryStep;
 import com.facebook.buck.step.fs.MkdirAndSymlinkFileStep;
 import com.facebook.buck.testutil.MoreAsserts;
-import com.facebook.buck.testutil.RuleMap;
 import com.facebook.buck.util.DirectoryTraversal;
 import com.facebook.buck.util.DirectoryTraverser;
 import com.facebook.buck.util.MorePaths;
@@ -104,11 +102,10 @@
         .setKeystore(addKeystoreRule(ruleResolver))
         .setPackageType("debug"));
 
-    DependencyGraph graph = RuleMap.createGraphFromBuildRules(ruleResolver);
     AndroidTransitiveDependencies transitiveDependencies =
-        androidBinary.findTransitiveDependencies(graph);
+        androidBinary.findTransitiveDependencies();
     AndroidDexTransitiveDependencies dexTransitiveDependencies =
-        androidBinary.findDexTransitiveDependencies(graph);
+        androidBinary.findDexTransitiveDependencies();
     ImmutableList.Builder<Step> commands = ImmutableList.builder();
 
     BuildContext context = createMock(BuildContext.class);
diff --git a/test/com/facebook/buck/android/AndroidResourceRuleTest.java b/test/com/facebook/buck/android/AndroidResourceRuleTest.java
index 2480d94..2a95529 100644
--- a/test/com/facebook/buck/android/AndroidResourceRuleTest.java
+++ b/test/com/facebook/buck/android/AndroidResourceRuleTest.java
@@ -25,12 +25,10 @@
 import com.facebook.buck.rules.BuildRule;
 import com.facebook.buck.rules.BuildRuleParams;
 import com.facebook.buck.rules.BuildRuleResolver;
-import com.facebook.buck.rules.DependencyGraph;
 import com.facebook.buck.rules.FakeAbstractBuildRuleBuilderParams;
 import com.facebook.buck.rules.FakeBuildRuleParams;
 import com.facebook.buck.rules.FileSourcePath;
 import com.facebook.buck.testutil.MoreAsserts;
-import com.facebook.buck.testutil.RuleMap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSortedSet;
 
@@ -125,8 +123,7 @@
         .addDep(BuildTargetFactory.newInstance("//:c"))
         .addDep(BuildTargetFactory.newInstance("//:d")));
 
-    DependencyGraph graph = RuleMap.createGraphFromBuildRules(ruleResolver);
-    ImmutableList<HasAndroidResourceDeps> deps = UberRDotJavaUtil.getAndroidResourceDeps(a, graph);
+    ImmutableList<HasAndroidResourceDeps> deps = UberRDotJavaUtil.getAndroidResourceDeps(a);
 
     // Note that a topological sort for a DAG is not guaranteed to be unique. In this particular
     // case, there are two possible valid outcomes.
@@ -157,8 +154,7 @@
         .addDep(BuildTargetFactory.newInstance("//:a"))
         .addDep(BuildTargetFactory.newInstance("//:c")));
 
-    DependencyGraph graph2 = RuleMap.createGraphFromBuildRules(ruleResolver);
-    ImmutableList<HasAndroidResourceDeps> deps2 = UberRDotJavaUtil.getAndroidResourceDeps(e, graph2);
+    ImmutableList<HasAndroidResourceDeps> deps2 = UberRDotJavaUtil.getAndroidResourceDeps(e);
     assertTrue(
         String.format(
             "Topological sort %s should be either %s or %s", deps, validResult1, validResult2),
diff --git a/test/com/facebook/buck/android/AndroidTransitiveDependencyGraphTest.java b/test/com/facebook/buck/android/AndroidTransitiveDependencyGraphTest.java
index 799f08c..54a8539 100644
--- a/test/com/facebook/buck/android/AndroidTransitiveDependencyGraphTest.java
+++ b/test/com/facebook/buck/android/AndroidTransitiveDependencyGraphTest.java
@@ -26,10 +26,8 @@
 import com.facebook.buck.model.BuildTargetPattern;
 import com.facebook.buck.rules.BuildRule;
 import com.facebook.buck.rules.BuildRuleResolver;
-import com.facebook.buck.rules.DependencyGraph;
 import com.facebook.buck.rules.FakeAbstractBuildRuleBuilderParams;
 import com.facebook.buck.rules.FileSourcePath;
-import com.facebook.buck.testutil.RuleMap;
 import com.facebook.buck.util.BuckConstant;
 import com.google.common.collect.ImmutableSet;
 
@@ -107,10 +105,9 @@
         .setKeystore(keystoreTarget));
 
     // Verify that the correct transitive dependencies are found.
-    DependencyGraph graph = RuleMap.createGraphFromBuildRules(ruleResolver);
-    AndroidTransitiveDependencies transitiveDeps = binaryRule.findTransitiveDependencies(graph);
+    AndroidTransitiveDependencies transitiveDeps = binaryRule.findTransitiveDependencies();
     AndroidDexTransitiveDependencies dexTransitiveDeps =
-    		binaryRule.findDexTransitiveDependencies(graph);
+    		binaryRule.findDexTransitiveDependencies();
     assertEquals(
         "Because guava was passed to no_dx, it should not be in the classpathEntriesToDex list",
         ImmutableSet.of("third_party/jsr-305/jsr305.jar"),
@@ -188,9 +185,8 @@
         .setKeystore(keystoreTarget)
         .addClasspathDep(androidLibraryTarget));
 
-    DependencyGraph dependencyGraph = RuleMap.createGraphFromBuildRules(ruleResolver);
     AndroidDexTransitiveDependencies androidTransitiveDeps = androidBinaryRule
-        .findDexTransitiveDependencies(dependencyGraph);
+        .findDexTransitiveDependencies();
     assertEquals(
         "Classpath entries should include facebook/base but not keystore/base.",
         ImmutableSet.of(BuckConstant.GEN_DIR + "/java/com/facebook/base/lib__base__output/base.jar"),
diff --git a/test/com/facebook/buck/java/DefaultJavaLibraryRuleTest.java b/test/com/facebook/buck/java/DefaultJavaLibraryRuleTest.java
index 44ec6e5..9681815 100644
--- a/test/com/facebook/buck/java/DefaultJavaLibraryRuleTest.java
+++ b/test/com/facebook/buck/java/DefaultJavaLibraryRuleTest.java
@@ -461,10 +461,7 @@
         .addSrc("java/src/com/libtwo/Foo.java")
         .addDep(BuildTargetFactory.newInstance("//:libone")));
 
-    DependencyGraph graph = RuleMap.createGraphFromBuildRules(ruleResolver);
-
     BuildContext buildContext = EasyMock.createMock(BuildContext.class);
-    expect(buildContext.getDependencyGraph()).andReturn(graph);
     expect(buildContext.getBuildDependencies()).andReturn(BuildDependencies.FIRST_ORDER_ONLY)
         .times(2);
     JavaPackageFinder javaPackageFinder = EasyMock.createMock(JavaPackageFinder.class);