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
@@ -3,6 +3,8 @@
 import java.io.IOException;
 
 import it.unimi.dsi.big.webgraph.BVGraph;
+import it.unimi.dsi.big.webgraph.ImmutableGraph;
+import it.unimi.dsi.big.webgraph.Transform;
 import it.unimi.dsi.lang.FlyweightPrototype;
 import it.unimi.dsi.big.webgraph.LazyLongIterator;
 
@@ -29,7 +31,7 @@
  * @see org.softwareheritage.graph.backend.NodeTypesMap
  */
 
-public class Graph implements FlyweightPrototype<Graph> {
+public class Graph extends ImmutableGraph {
     /** File extension for the SWH PID to long node id map */
     public static final String PID_TO_NODE = ".pid2node.bin";
     /** File extension for the long node id to SWH PID map */
@@ -38,9 +40,9 @@
     public static final String NODE_TO_TYPE = ".node2type.map";
 
     /** Compressed graph stored as a {@link it.unimi.dsi.big.webgraph.BVGraph} */
-    BVGraph graph;
+    ImmutableGraph graph;
     /** Transposed compressed graph (used for backward traversals) */
-    BVGraph graphTransposed;
+    ImmutableGraph graphTransposed;
     /** Path and basename of the compressed graph */
     String path;
     /** Mapping long id &harr; SWH PIDs */
@@ -63,24 +65,35 @@
         // translation between ints and PIDs is happening on the Python side.
         // However, some parts of the code still depend on this, so it's
         // commented out while we decide on what to do with it.
-        this.nodeIdMap = null; // new NodeIdMap(path, getNbNodes());
+        this.nodeIdMap = null; // new NodeIdMap(path, numNodes());
     }
 
     // Protected empty constructor to implement copy()
     protected Graph() { }
 
+    protected Graph(ImmutableGraph graph, ImmutableGraph graphTransposed, String path, NodeIdMap nodeIdMap, NodeTypesMap nodeTypesMap) {
+        this.graph = graph;
+        this.graphTransposed = graphTransposed;
+        this.path = path;
+        this.nodeIdMap = nodeIdMap;
+        this.nodeTypesMap = nodeTypesMap;
+    }
+
     /**
      * Return a flyweight copy of the graph.
      */
     @Override
     public Graph copy() {
-        final Graph ng = new Graph();
-        ng.graph = this.graph.copy();
-        ng.graphTransposed = this.graphTransposed.copy();
-        ng.path = path;
-        ng.nodeIdMap = this.nodeIdMap;
-        ng.nodeTypesMap = this.nodeTypesMap;
-        return ng;
+        return new Graph(this.graph.copy(), this.graphTransposed.copy(), this.path, this.nodeIdMap, this.nodeTypesMap);
+    }
+
+    public Graph transpose() {
+        return new Graph(this.graphTransposed.copy(), this.graph.copy(), this.path, this.nodeIdMap, this.nodeTypesMap);
+    }
+
+    public Graph symmetrize() {
+        ImmutableGraph symmetric = Transform.union(graph, graphTransposed);
+        return new Graph(symmetric, symmetric, this.path, this.nodeIdMap, this.nodeTypesMap);
     }
 
     /**
@@ -132,12 +145,14 @@
         return nodeTypesMap.getType(nodeId);
     }
 
+    public boolean randomAccess() { return graph.randomAccess() && graphTransposed.randomAccess(); }
+
     /**
      * Returns number of nodes in the graph.
      *
      * @return number of nodes in the graph
      */
-    public long getNbNodes() {
+    public long numNodes() {
         return graph.numNodes();
     }
 
@@ -146,7 +161,7 @@
      *
      * @return number of edges in the graph
      */
-    public long getNbEdges() {
+    public long numArcs() {
         return graph.numArcs();
     }
 
@@ -192,36 +207,12 @@
         return graphTransposed.outdegree(nodeId);
     }
 
-    /**
-     * Returns the degree of a node, depending on graph orientation.
-     *
-     * @param nodeId node specified as a long id
-     * @param useTransposed boolean value to use transposed graph
-     * @return degree of a node
-     */
-    public long degree(long nodeId, boolean useTransposed) {
-        return (useTransposed) ? indegree(nodeId) : outdegree(nodeId);
-    }
-
-    /**
-     * Returns the neighbors of a node (as a lazy iterator), depending on graph orientation.
-     *
-     * @param nodeId node specified as a long id
-     * @param useTransposed boolean value to use transposed graph
-     * @return lazy iterator of neighbors of the node, specified as a <a
-     * href="http://webgraph.di.unimi.it/">WebGraph</a> LazyLongIterator
-     */
-    public LazyLongIterator neighbors(long nodeId, boolean useTransposed) {
-        return (useTransposed) ? predecessors(nodeId) : successors(nodeId);
-    }
-
     /**
      * Returns the underlying BVGraph.
      *
-     * @param useTransposed boolean value to use transposed graph
      * @return WebGraph BVGraph
      */
-    public BVGraph getBVGraph(boolean useTransposed) {
-        return (useTransposed) ? this.graphTransposed : this.graph;
+    public ImmutableGraph getGraph() {
+        return this.graph;
     }
 }
diff --git a/java/src/main/java/org/softwareheritage/graph/Neighbors.java b/java/src/main/java/org/softwareheritage/graph/Neighbors.java
--- a/java/src/main/java/org/softwareheritage/graph/Neighbors.java
+++ b/java/src/main/java/org/softwareheritage/graph/Neighbors.java
@@ -19,8 +19,6 @@
 public class Neighbors implements Iterable<Long> {
     /** Graph used to explore neighbors */
     Graph graph;
-    /** Boolean to specify the use of the transposed graph */
-    boolean useTransposed;
     /** Graph edge restriction */
     AllowedEdges edges;
     /** Source node from which neighbors will be listed */
@@ -30,13 +28,11 @@
      * Constructor.
      *
      * @param graph graph used to explore neighbors
-     * @param useTransposed boolean value to use transposed graph
      * @param edges edges allowed to be used in the graph
      * @param srcNodeId source node from where to list neighbors
      */
-    public Neighbors(Graph graph, boolean useTransposed, AllowedEdges edges, long srcNodeId) {
+    public Neighbors(Graph graph, AllowedEdges edges, long srcNodeId) {
         this.graph = graph;
-        this.useTransposed = useTransposed;
         this.edges = edges;
         this.srcNodeId = srcNodeId;
     }
@@ -57,7 +53,7 @@
         long nextNeighborId;
 
         public NeighborsIterator() {
-            this.neighbors = graph.neighbors(srcNodeId, useTransposed);
+            this.neighbors = graph.successors(srcNodeId);
             this.nextNeighborId = -1;
         }
 
diff --git a/java/src/main/java/org/softwareheritage/graph/algo/NodeIdsConsumer.java b/java/src/main/java/org/softwareheritage/graph/algo/NodeIdsConsumer.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/algo/NodeIdsConsumer.java
+++ /dev/null
@@ -1,14 +0,0 @@
-package org.softwareheritage.graph.algo;
-
-import java.util.function.BiConsumer;
-
-public interface NodeIdsConsumer extends BiConsumer {
-
-    /** Callback for returning a (potentially large) list of node identifiers.
-     * The callback will be invoked repeatedly without reallocating the array.
-     * At each invocation the array might contain more than size node
-     * identifiers, but only identifiers located up to position size-1 are to
-     * be considered during that specific invocation.
-     */
-    void accept(long nodeIds[], int size);
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/algo/Traversal.java b/java/src/main/java/org/softwareheritage/graph/algo/Traversal.java
--- a/java/src/main/java/org/softwareheritage/graph/algo/Traversal.java
+++ b/java/src/main/java/org/softwareheritage/graph/algo/Traversal.java
@@ -2,8 +2,6 @@
 
 import java.util.*;
 
-import it.unimi.dsi.bits.LongArrayBitVector;
-
 import org.softwareheritage.graph.AllowedEdges;
 import org.softwareheritage.graph.Endpoint;
 import org.softwareheritage.graph.Graph;
@@ -24,8 +22,6 @@
 public class Traversal {
     /** Graph used in the traversal */
     Graph graph;
-    /** Boolean to specify the use of the transposed graph */
-    boolean useTransposed;
     /** Graph edge restriction */
     AllowedEdges edges;
 
@@ -52,11 +48,13 @@
             throw new IllegalArgumentException("Unknown traversal direction: " + direction);
         }
 
-        this.graph = graph;
-        this.useTransposed = (direction.equals("backward"));
+        if (direction.equals("backward")) {
+            this.graph = graph.transpose();
+        } else {
+            this.graph = graph;
+        }
         this.edges = new AllowedEdges(graph, edgesFmt);
 
-        long nbNodes = graph.getNbNodes();
         this.visited = new HashSet<>();
         this.parentNode = new HashMap<>();
         this.nbEdgesAccessed = 0;
@@ -82,10 +80,10 @@
     }
 
     /**
-     * Push version of {@link leaves}: will fire passed callback for each leaf.
+     * Push version of {@link #leaves} will fire passed callback for each leaf.
      */
     public void leavesVisitor(long srcNodeId, NodeIdConsumer cb) {
-        Stack<Long> stack = new Stack<Long>();
+        Stack<Long> stack = new Stack<>();
         this.nbEdgesAccessed = 0;
 
         stack.push(srcNodeId);
@@ -95,8 +93,8 @@
             long currentNodeId = stack.pop();
 
             long neighborsCnt = 0;
-            nbEdgesAccessed += graph.degree(currentNodeId, useTransposed);
-            for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
+            nbEdgesAccessed += graph.outdegree(currentNodeId);
+            for (long neighborNodeId : new Neighbors(graph, edges, currentNodeId)) {
                 neighborsCnt++;
                 if (!visited.contains(neighborNodeId)) {
                     stack.push(neighborNodeId);
@@ -117,18 +115,18 @@
      * @return list of node ids corresponding to the leaves
      */
     public ArrayList<Long> leaves(long srcNodeId) {
-        ArrayList<Long> nodeIds = new ArrayList<Long>();
-        leavesVisitor(srcNodeId, (nodeId) -> nodeIds.add(nodeId));
+        ArrayList<Long> nodeIds = new ArrayList<>();
+        leavesVisitor(srcNodeId, nodeIds::add);
         return nodeIds;
     }
 
     /**
-     * Push version of {@link neighbors}: will fire passed callback on each
+     * Push version of {@link #neighbors}: will fire passed callback on each
      * neighbor.
      */
     public void neighborsVisitor(long srcNodeId, NodeIdConsumer cb) {
-        this.nbEdgesAccessed = graph.degree(srcNodeId, useTransposed);
-        for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, srcNodeId)) {
+        this.nbEdgesAccessed = graph.outdegree(srcNodeId);
+        for (long neighborNodeId : new Neighbors(graph, edges, srcNodeId)) {
             cb.accept(neighborNodeId);
         }
     }
@@ -140,17 +138,17 @@
      * @return list of node ids corresponding to the neighbors
      */
     public ArrayList<Long> neighbors(long srcNodeId) {
-        ArrayList<Long> nodeIds = new ArrayList<Long>();
-        neighborsVisitor(srcNodeId, (nodeId) -> nodeIds.add(nodeId));
+        ArrayList<Long> nodeIds = new ArrayList<>();
+        neighborsVisitor(srcNodeId, nodeIds::add);
         return nodeIds;
     }
 
     /**
-     * Push version of {@link visitNodes}: will fire passed callback on each
+     * Push version of {@link #visitNodes}: will fire passed callback on each
      * visited node.
      */
     public void visitNodesVisitor(long srcNodeId, NodeIdConsumer nodeCb, EdgeIdConsumer edgeCb) {
-        Stack<Long> stack = new Stack<Long>();
+        Stack<Long> stack = new Stack<>();
         this.nbEdgesAccessed = 0;
 
         stack.push(srcNodeId);
@@ -162,8 +160,8 @@
                 nodeCb.accept(currentNodeId);
             }
 
-            nbEdgesAccessed += graph.degree(currentNodeId, useTransposed);
-            for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
+            nbEdgesAccessed += graph.outdegree(currentNodeId);
+            for (long neighborNodeId : new Neighbors(graph, edges, currentNodeId)) {
                 if (edgeCb != null) {
                     edgeCb.accept(currentNodeId, neighborNodeId);
                 }
@@ -187,17 +185,17 @@
      * @return list of explored node ids
      */
     public ArrayList<Long> visitNodes(long srcNodeId) {
-        ArrayList<Long> nodeIds = new ArrayList<Long>();
-        visitNodesVisitor(srcNodeId, (nodeId) -> nodeIds.add(nodeId));
+        ArrayList<Long> nodeIds = new ArrayList<>();
+        visitNodesVisitor(srcNodeId, nodeIds::add);
         return nodeIds;
     }
 
     /**
-     * Push version of {@link visitPaths}: will fire passed callback on each
+     * Push version of {@link #visitPaths}: will fire passed callback on each
      * discovered (complete) path.
      */
     public void visitPathsVisitor(long srcNodeId, PathConsumer cb) {
-        Stack<Long> currentPath = new Stack<Long>();
+        Stack<Long> currentPath = new Stack<>();
         this.nbEdgesAccessed = 0;
         visitPathsInternalVisitor(srcNodeId, currentPath, cb);
     }
@@ -210,7 +208,7 @@
      */
     public ArrayList<ArrayList<Long>> visitPaths(long srcNodeId) {
         ArrayList<ArrayList<Long>> paths = new ArrayList<>();
-        visitPathsVisitor(srcNodeId, (path) -> paths.add(path));
+        visitPathsVisitor(srcNodeId, paths::add);
         return paths;
     }
 
@@ -220,17 +218,14 @@
         currentPath.push(currentNodeId);
 
         long visitedNeighbors = 0;
-        nbEdgesAccessed += graph.degree(currentNodeId, useTransposed);
-        for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
+        nbEdgesAccessed += graph.outdegree(currentNodeId);
+        for (long neighborNodeId : new Neighbors(graph, edges, currentNodeId)) {
             visitPathsInternalVisitor(neighborNodeId, currentPath, cb);
             visitedNeighbors++;
         }
 
         if (visitedNeighbors == 0) {
-            ArrayList<Long> path = new ArrayList<Long>();
-            for (long nodeId : currentPath) {
-                path.add(nodeId);
-            }
+            ArrayList<Long> path = new ArrayList<>(currentPath);
             cb.accept(path);
         }
 
@@ -246,7 +241,7 @@
      * @return found path as a list of node ids
      */
     public <T> ArrayList<Long> walk(long srcNodeId, T dst, String visitOrder) {
-        long dstNodeId = -1;
+        long dstNodeId;
         if (visitOrder.equals("dfs")) {
             dstNodeId = walkInternalDFS(srcNodeId, dst);
         } else if (visitOrder.equals("bfs")) {
@@ -259,8 +254,7 @@
             throw new IllegalArgumentException("Cannot find destination: " + dst);
         }
 
-        ArrayList<Long> nodeIds = backtracking(srcNodeId, dstNodeId);
-        return nodeIds;
+        return backtracking(srcNodeId, dstNodeId);
     }
 
     /**
@@ -290,7 +284,7 @@
      */
     public <T> ArrayList<Long> randomWalk(long srcNodeId, T dst, int retries) {
         long curNodeId = srcNodeId;
-        ArrayList<Long> path = new ArrayList<Long>();
+        ArrayList<Long> path = new ArrayList<>();
         this.nbEdgesAccessed = 0;
         boolean found;
 
@@ -300,7 +294,7 @@
 
         while (true) {
             path.add(curNodeId);
-            Neighbors neighbors = new Neighbors(graph, useTransposed, edges, curNodeId);
+            Neighbors neighbors = new Neighbors(graph, edges, curNodeId);
             curNodeId = randomPick(neighbors.iterator());
             if (curNodeId < 0) {
                 found = false;
@@ -352,7 +346,7 @@
      * @return final destination node or -1 if no path found
      */
     private <T> long walkInternalDFS(long srcNodeId, T dst) {
-        Stack<Long> stack = new Stack<Long>();
+        Stack<Long> stack = new Stack<>();
         this.nbEdgesAccessed = 0;
 
         stack.push(srcNodeId);
@@ -364,8 +358,8 @@
                 return currentNodeId;
             }
 
-            nbEdgesAccessed += graph.degree(currentNodeId, useTransposed);
-            for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
+            nbEdgesAccessed += graph.outdegree(currentNodeId);
+            for (long neighborNodeId : new Neighbors(graph, edges, currentNodeId)) {
                 if (!visited.contains(neighborNodeId)) {
                     stack.push(neighborNodeId);
                     visited.add(neighborNodeId);
@@ -385,7 +379,7 @@
      * @return final destination node or -1 if no path found
      */
     private <T> long walkInternalBFS(long srcNodeId, T dst) {
-        Queue<Long> queue = new LinkedList<Long>();
+        Queue<Long> queue = new LinkedList<>();
         this.nbEdgesAccessed = 0;
 
         queue.add(srcNodeId);
@@ -397,8 +391,8 @@
                 return currentNodeId;
             }
 
-            nbEdgesAccessed += graph.degree(currentNodeId, useTransposed);
-            for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
+            nbEdgesAccessed += graph.outdegree(currentNodeId);
+            for (long neighborNodeId : new Neighbors(graph, edges, currentNodeId)) {
                 if (!visited.contains(neighborNodeId)) {
                     queue.add(neighborNodeId);
                     visited.add(neighborNodeId);
@@ -437,7 +431,7 @@
      * @return the found path, as a list of node ids
      */
     private ArrayList<Long> backtracking(long srcNodeId, long dstNodeId) {
-        ArrayList<Long> path = new ArrayList<Long>();
+        ArrayList<Long> path = new ArrayList<>();
         long currentNodeId = dstNodeId;
         while (currentNodeId != srcNodeId) {
             path.add(currentNodeId);
@@ -448,6 +442,13 @@
         return path;
     }
 
+    /**
+     * Find a common descendant between two given nodes using two parallel BFS
+     *
+     * @param lhsNode the first node
+     * @param rhsNode the second node
+     * @return the found path, as a list of node ids
+     */
     public Long findCommonDescendant(long lhsNode, long rhsNode) {
         Queue<Long> lhsStack = new ArrayDeque<>();
         Queue<Long> rhsStack = new ArrayDeque<>();
@@ -464,8 +465,8 @@
         while (!lhsStack.isEmpty() || !rhsStack.isEmpty()) {
             if (!lhsStack.isEmpty()) {
                 curNode = lhsStack.poll();
-                nbEdgesAccessed += graph.degree(curNode, useTransposed);
-                for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, curNode)) {
+                nbEdgesAccessed += graph.outdegree(curNode);
+                for (long neighborNodeId : new Neighbors(graph, edges, curNode)) {
                     if (!lhsVisited.contains(neighborNodeId)) {
                         if (rhsVisited.contains(neighborNodeId))
                             return neighborNodeId;
@@ -477,8 +478,8 @@
 
             if (!rhsStack.isEmpty()) {
                 curNode = rhsStack.poll();
-                nbEdgesAccessed += graph.degree(curNode, useTransposed);
-                for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, curNode)) {
+                nbEdgesAccessed += graph.outdegree(curNode);
+                for (long neighborNodeId : new Neighbors(graph, edges, curNode)) {
                     if (!rhsVisited.contains(neighborNodeId)) {
                         if (lhsVisited.contains(neighborNodeId))
                             return neighborNodeId;
diff --git a/java/src/main/java/org/softwareheritage/graph/backend/MapBuilder.java b/java/src/main/java/org/softwareheritage/graph/backend/MapBuilder.java
--- a/java/src/main/java/org/softwareheritage/graph/backend/MapBuilder.java
+++ b/java/src/main/java/org/softwareheritage/graph/backend/MapBuilder.java
@@ -6,6 +6,7 @@
 import java.util.concurrent.*;
 
 import it.unimi.dsi.bits.LongArrayBitVector;
+import it.unimi.dsi.fastutil.BigArrays;
 import it.unimi.dsi.fastutil.Size64;
 import it.unimi.dsi.fastutil.io.BinIO;
 import it.unimi.dsi.fastutil.longs.LongBigArrays;
@@ -146,7 +147,7 @@
                 byte[] swhPIDBin = swhPID.toBytes();
 
                 long mphId = mphMap.getLong(strSwhPID);
-                long nodeId = LongBigArrays.get(bfsMap, mphId);
+                long nodeId = BigArrays.get(bfsMap, mphId);
 
                 pidToNodeMap.write(swhPIDBin, 0, swhPIDBin.length);
                 pidToNodeMap.writeLong(nodeId);
diff --git a/java/src/main/java/org/softwareheritage/graph/backend/Pp.java b/java/src/main/java/org/softwareheritage/graph/backend/Pp.java
--- a/java/src/main/java/org/softwareheritage/graph/backend/Pp.java
+++ b/java/src/main/java/org/softwareheritage/graph/backend/Pp.java
@@ -1,31 +1,12 @@
 package org.softwareheritage.graph.backend;
 
-import java.io.BufferedWriter;
-import java.io.FileInputStream;
-import java.io.FileWriter;
 import java.io.IOException;
-import java.io.InputStream;
-import java.io.InputStreamReader;
-import java.io.Writer;
-import java.util.zip.GZIPInputStream;
-
-import it.unimi.dsi.bits.LongArrayBitVector;
 import it.unimi.dsi.fastutil.Size64;
 import it.unimi.dsi.fastutil.io.BinIO;
-import it.unimi.dsi.fastutil.longs.LongBigArrays;
-import it.unimi.dsi.fastutil.longs.LongBigList;
 import it.unimi.dsi.fastutil.objects.Object2LongFunction;
-import it.unimi.dsi.fastutil.objects.ObjectBigArrays;
-import it.unimi.dsi.io.FastBufferedReader;
-import it.unimi.dsi.io.LineIterator;
-
-import org.softwareheritage.graph.Graph;
-import org.softwareheritage.graph.Node;
-import org.softwareheritage.graph.SwhPID;
-import org.softwareheritage.graph.backend.NodeTypesMap;
 
 public class Pp {
-
+    @SuppressWarnings("unchecked")
     public static void main(String[] args) throws IOException {
 
         Object2LongFunction<String> mphMap = null;
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java b/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java
+++ b/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java
@@ -19,18 +19,16 @@
 
 
 public class BFS {
-    private Graph graph;
-
-    private void load_graph(String graphBasename) throws IOException {
-        System.err.println("Loading graph " + graphBasename + " ...");
-        this.graph = new Graph(graphBasename);
-        System.err.println("Graph loaded.");
-    }
+    private final ImmutableGraph graph;
 
     private final static Logger LOGGER = LoggerFactory.getLogger(BFS.class);
 
+    public BFS(ImmutableGraph graph) {
+        this.graph = graph;
+    }
+
     // Partly inlined from it.unimi.dsi.law.big.graph.BFS
-    private static void bfsperm(final ImmutableGraph graph) throws IOException {
+    private void bfsperm() throws IOException {
         final long n = graph.numNodes();
         // Allow enough memory to behave like in-memory queue
         int bufferSize = (int)Math.min(Arrays.MAX_ARRAY_SIZE & ~0x7, 8L * n);
@@ -47,8 +45,6 @@
         pl.itemsName = "nodes";
         pl.start("Starting breadth-first visit...");
 
-        long pos = 0;
-
         for (long i = 0; i < n; i++) {
             if (visited.getBoolean(i)) continue;
             queue.enqueue(Longs.toByteArray(i));
@@ -101,30 +97,19 @@
         return config;
     }
 
-    public static void main(String[] args) {
+    public static void main(String[] args) throws IOException {
         JSAPResult config = parse_args(args);
         String graphPath = config.getString("graphPath");
         boolean useTransposed = config.getBoolean("useTransposed");
 
-        ProgressLogger logger = new ProgressLogger();
-        long startTime;
-        double totalTime;
-
+        System.err.println("Loading graph " + graphPath + " ...");
+        Graph graph = new Graph(graphPath);
+        System.err.println("Graph loaded.");
 
-        BFS bfs = new BFS();
-        try {
-            bfs.load_graph(graphPath);
-        } catch (IOException e) {
-            System.out.println("Could not load graph: " + e);
-            System.exit(2);
-        }
+        if (useTransposed)
+            graph = graph.transpose();
 
-        logger.start("Parallel BFS visit...");
-        try {
-            BFS.bfsperm(bfs.graph.getBVGraph(useTransposed));
-        } catch (IOException e) {
-            e.printStackTrace();
-        }
-        logger.done();
+        BFS bfs = new BFS(graph);
+        bfs.bfsperm();
     }
 }
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java
+++ b/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java
@@ -161,7 +161,7 @@
     }
 
     /**
-     * Same as {@link timeEndpoint} but without destination or algorithm specified to endpoint call.
+     * Same as {@link #timeEndpoint} but without destination or algorithm specified to endpoint call.
      */
     public void timeEndpoint(String useCaseName, Graph graph, long[] nodeIds,
                              Function<Endpoint.Input, Endpoint.Output> operation) throws IOException {
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/ForkCC.java b/java/src/main/java/org/softwareheritage/graph/benchmark/ForkCC.java
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/ForkCC.java
+++ b/java/src/main/java/org/softwareheritage/graph/benchmark/ForkCC.java
@@ -2,9 +2,7 @@
 
 import com.google.common.primitives.Longs;
 import com.martiansoftware.jsap.*;
-import it.unimi.dsi.big.webgraph.ImmutableGraph;
 import it.unimi.dsi.big.webgraph.LazyLongIterator;
-import it.unimi.dsi.big.webgraph.Transform;
 import it.unimi.dsi.bits.LongArrayBitVector;
 import it.unimi.dsi.fastutil.Arrays;
 import it.unimi.dsi.io.ByteDiskQueue;
@@ -26,7 +24,7 @@
 
     private void load_graph(String graphBasename) throws IOException {
         System.err.println("Loading graph " + graphBasename + " ...");
-        this.graph = new Graph(graphBasename);
+        this.graph = new Graph(graphBasename).symmetrize();
         System.err.println("Graph loaded.");
         this.emptySnapshot = null;
         this.whitelist = null;
@@ -87,7 +85,7 @@
     }
 
 
-    private ArrayList<ArrayList<Long>> compute(final ImmutableGraph graph, ProgressLogger pl) throws IOException {
+    private ArrayList<ArrayList<Long>> compute(ProgressLogger pl) throws IOException {
         final long n = graph.numNodes();
         // Allow enough memory to behave like in-memory queue
         int bufferSize = (int)Math.min(Arrays.MAX_ARRAY_SIZE & ~0x7, 8L * n);
@@ -171,7 +169,7 @@
 
     private void parseWhitelist(String path) {
         System.err.println("Loading whitelist " + path + " ...");
-        this.whitelist = LongArrayBitVector.ofLength(this.graph.getNbNodes());
+        this.whitelist = LongArrayBitVector.ofLength(this.graph.numNodes());
         Scanner scanner = null;
         try {
             scanner = new Scanner(new File(path));
@@ -205,14 +203,9 @@
             forkCc.parseWhitelist(whitelistPath);
         }
 
-        ImmutableGraph symmetric = Transform.union(
-            forkCc.graph.getBVGraph(false),
-            forkCc.graph.getBVGraph(true)
-        );
-
         ProgressLogger logger = new ProgressLogger();
         try {
-            ArrayList<ArrayList<Long>> components = forkCc.compute(symmetric, logger);
+            ArrayList<ArrayList<Long>> components = forkCc.compute(logger);
             printDistribution(components);
             // printLargestComponent(components);
         } catch (IOException e) {
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/ListEmptyOrigins.java b/java/src/main/java/org/softwareheritage/graph/benchmark/ListEmptyOrigins.java
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/ListEmptyOrigins.java
+++ b/java/src/main/java/org/softwareheritage/graph/benchmark/ListEmptyOrigins.java
@@ -85,7 +85,7 @@
             System.out.println("Could not load graph: " + e);
             System.exit(2);
         }
-        ArrayList<Long> badlist = leo.compute(leo.graph.getBVGraph(false));
+        ArrayList<Long> badlist = leo.compute(leo.graph);
         for (Long bad : badlist) {
             System.out.println(bad);
         }
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Random.java b/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Random.java
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Random.java
+++ b/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Random.java
@@ -39,7 +39,7 @@
      * @return an array of random node ids
      */
     public long[] generateNodeIds(Graph graph, int nbNodes) {
-        return random.longs(nbNodes, 0, graph.getNbNodes()).toArray();
+        return random.longs(nbNodes, 0, graph.numNodes()).toArray();
     }
 
     /**
@@ -51,7 +51,7 @@
      * @return an array of random node ids
      */
     public long[] generateNodeIdsOfType(Graph graph, int nbNodes, Node.Type expectedType) {
-        PrimitiveIterator.OfLong nodes = random.longs(0, graph.getNbNodes()).iterator();
+        PrimitiveIterator.OfLong nodes = random.longs(0, graph.numNodes()).iterator();
         long[] nodeIds = new long[nbNodes];
 
         long nextId;
diff --git a/swh/graph/graph.py b/swh/graph/graph.py
--- a/swh/graph/graph.py
+++ b/swh/graph/graph.py
@@ -156,7 +156,7 @@
         return self.java_graph.getPath()
 
     def __len__(self):
-        return self.java_graph.getNbNodes()
+        return self.java_graph.numNodes()
 
     def __getitem__(self, node_id):
         if isinstance(node_id, int):