diff --git a/java/src/main/java/org/softwareheritage/graph/AllowedEdges.java b/java/src/main/java/org/softwareheritage/graph/AllowedEdges.java
--- a/java/src/main/java/org/softwareheritage/graph/AllowedEdges.java
+++ b/java/src/main/java/org/softwareheritage/graph/AllowedEdges.java
@@ -20,19 +20,14 @@
      * this array is set to null for early bypass.
      */
     public boolean[][] restrictedTo;
-    /** Graph on which edge restriction is performed */
-    Graph graph;
 
     /**
      * Constructor.
      *
-     * @param graph the graph on which to perform edge restriction
      * @param edgesFmt a formatted string describing <a
      * href="https://docs.softwareheritage.org/devel/swh-graph/api.html#terminology">allowed edges</a>
      */
-    public AllowedEdges(Graph graph, String edgesFmt) {
-        this.graph = graph;
-
+    public AllowedEdges(String edgesFmt) {
         int nbNodeTypes = Node.Type.values().length;
         this.restrictedTo = new boolean[nbNodeTypes][nbNodeTypes];
         // Special values (null, empty, "*")
@@ -66,23 +61,13 @@
     /**
      * Checks if a given edge can be followed during graph traversal.
      *
-     * @param srcNodeId edge source node
-     * @param dstNodeId edge destination node
+     * @param srcType edge source type
+     * @param dstType edge destination type
      * @return true if allowed and false otherwise
      */
-    public boolean isAllowed(long srcNodeId, long dstNodeId) {
-        Node.Type srcType = graph.getNodeType(srcNodeId);
-        Node.Type dstType = graph.getNodeType(dstNodeId);
-        return restrictedTo[srcType.ordinal()][dstType.ordinal()];
-    }
-
-    /**
-     * Works like {@link AllowedEdges#isAllowed(long, long)} but with node types directly instead of
-     * node ids.
-     *
-     * @see AllowedEdges#isAllowed(long, long)
-     */
     public boolean isAllowed(Node.Type srcType, Node.Type dstType) {
+        if (restrictedTo == null)
+            return true;
         return restrictedTo[srcType.ordinal()][dstType.ordinal()];
     }
 }
diff --git a/java/src/main/java/org/softwareheritage/graph/Graph.java b/java/src/main/java/org/softwareheritage/graph/Graph.java
--- a/java/src/main/java/org/softwareheritage/graph/Graph.java
+++ b/java/src/main/java/org/softwareheritage/graph/Graph.java
@@ -9,6 +9,8 @@
 
 import java.io.IOException;
 
+import static it.unimi.dsi.big.webgraph.ImmutableGraph.*;
+
 /**
  * Main class storing the compressed graph and node id mappings.
  * <p>
@@ -53,8 +55,8 @@
      */
     public Graph(String path) throws IOException {
         this.path = path;
-        this.graph = BVGraph.loadMapped(path);
-        this.graphTransposed = BVGraph.loadMapped(path + "-transposed");
+        this.graph = loadMapped(path);
+        this.graphTransposed = loadMapped(path + "-transposed");
         this.nodeTypesMap = new NodeTypesMap(path);
         this.nodeIdMap = new NodeIdMap(path, numNodes());
     }
@@ -149,12 +151,13 @@
             return this.successors(nodeId);
         } else {
             LazyLongIterator allSuccessors = this.successors(nodeId);
+            Graph thisGraph = this;
             return new LazyLongIterator() {
                 @Override
                 public long nextLong() {
                     long neighbor;
                     while ((neighbor = allSuccessors.nextLong()) != -1) {
-                        if (allowedEdges.isAllowed(nodeId, neighbor)) {
+                        if (allowedEdges.isAllowed(thisGraph.getNodeType(nodeId), thisGraph.getNodeType(neighbor))) {
                             return neighbor;
                         }
                     }
diff --git a/java/src/main/java/org/softwareheritage/graph/Traversal.java b/java/src/main/java/org/softwareheritage/graph/Traversal.java
--- a/java/src/main/java/org/softwareheritage/graph/Traversal.java
+++ b/java/src/main/java/org/softwareheritage/graph/Traversal.java
@@ -51,7 +51,7 @@
         } else {
             this.graph = graph;
         }
-        this.edges = new AllowedEdges(graph, edgesFmt);
+        this.edges = new AllowedEdges(edgesFmt);
 
         this.visited = new HashSet<>();
         this.parentNode = new HashMap<>();
diff --git a/java/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java b/java/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java
--- a/java/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java
+++ b/java/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java
@@ -5,12 +5,9 @@
 import org.junit.Test;
 import org.junit.Assert;
 
-import org.softwareheritage.graph.AllowedEdges;
-import org.softwareheritage.graph.GraphTest;
-import org.softwareheritage.graph.Node;
 
 public class AllowedEdgesTest extends GraphTest {
-    class EdgeType {
+    static class EdgeType {
         Node.Type src;
         Node.Type dst;
 
@@ -43,15 +40,14 @@
                     }
                 }
 
-                Assert.assertTrue("Edge type: " + src + " -> " + dst, isAllowed == isExpected);
+                Assert.assertEquals("Edge type: " + src + " -> " + dst, isAllowed, isExpected);
             }
         }
     }
 
     @Test
     public void dirToDirDirToCntEdges() {
-        Graph graph = getGraph();
-        AllowedEdges edges = new AllowedEdges(graph, "dir:dir,dir:cnt");
+        AllowedEdges edges = new AllowedEdges("dir:dir,dir:cnt");
         ArrayList<EdgeType> expected = new ArrayList<>();
         expected.add(new EdgeType(Node.Type.DIR, Node.Type.DIR));
         expected.add(new EdgeType(Node.Type.DIR, Node.Type.CNT));
@@ -60,8 +56,7 @@
 
     @Test
     public void relToRevRevToRevRevToDirEdges() {
-        Graph graph = getGraph();
-        AllowedEdges edges = new AllowedEdges(graph, "rel:rev,rev:rev,rev:dir");
+        AllowedEdges edges = new AllowedEdges("rel:rev,rev:rev,rev:dir");
         ArrayList<EdgeType> expected = new ArrayList<>();
         expected.add(new EdgeType(Node.Type.REL, Node.Type.REV));
         expected.add(new EdgeType(Node.Type.REV, Node.Type.REV));
@@ -71,8 +66,7 @@
 
     @Test
     public void revToAllDirToDirEdges() {
-        Graph graph = getGraph();
-        AllowedEdges edges = new AllowedEdges(graph, "rev:*,dir:dir");
+        AllowedEdges edges = new AllowedEdges("rev:*,dir:dir");
         ArrayList<EdgeType> expected = new ArrayList<>();
         for (Node.Type dst : Node.Type.values()) {
             expected.add(new EdgeType(Node.Type.REV, dst));
@@ -83,8 +77,7 @@
 
     @Test
     public void allToCntEdges() {
-        Graph graph = getGraph();
-        AllowedEdges edges = new AllowedEdges(graph, "*:cnt");
+        AllowedEdges edges = new AllowedEdges("*:cnt");
         ArrayList<EdgeType> expected = new ArrayList<>();
         for (Node.Type src : Node.Type.values()) {
             expected.add(new EdgeType(src, Node.Type.CNT));
@@ -94,8 +87,7 @@
 
     @Test
     public void allEdges() {
-        Graph graph = getGraph();
-        AllowedEdges edges = new AllowedEdges(graph, "*:*");
+        AllowedEdges edges = new AllowedEdges("*:*");
         ArrayList<EdgeType> expected = new ArrayList<>();
         for (Node.Type src : Node.Type.values()) {
             for (Node.Type dst : Node.Type.values()) {
@@ -105,15 +97,14 @@
         assertEdgeRestriction(edges, expected);
 
         // Special null value used to quickly bypass edge check when no restriction
-        AllowedEdges edges2 = new AllowedEdges(graph, "*");
+        AllowedEdges edges2 = new AllowedEdges("*");
         Assert.assertNull(edges2.restrictedTo);
     }
 
     @Test
     public void noEdges() {
-        Graph graph = getGraph();
-        AllowedEdges edges = new AllowedEdges(graph, "");
-        AllowedEdges edges2 = new AllowedEdges(graph, null);
+        AllowedEdges edges = new AllowedEdges("");
+        AllowedEdges edges2 = new AllowedEdges(null);
         ArrayList<EdgeType> expected = new ArrayList<>();
         assertEdgeRestriction(edges, expected);
         assertEdgeRestriction(edges2, expected);