diff --git a/api/server/src/main/java/org/softwareheritage/graph/App.java b/api/server/src/main/java/org/softwareheritage/graph/App.java
index 13e8be4..da332a0 100644
--- a/api/server/src/main/java/org/softwareheritage/graph/App.java
+++ b/api/server/src/main/java/org/softwareheritage/graph/App.java
@@ -1,52 +1,51 @@
 package org.softwareheritage.graph;
 
 import java.io.IOException;
 import java.util.Optional;
 
 import io.javalin.Javalin;
 
 import org.softwareheritage.graph.Graph;
 import org.softwareheritage.graph.SwhId;
 import org.softwareheritage.graph.algo.Stats;
 import org.softwareheritage.graph.algo.Visit;
 
 public class App {
   public static void main(String[] args) throws IOException, Exception {
     String path = args[0];
     Graph graph = new Graph(path);
 
     Javalin app = Javalin.create().start(5010);
 
     app.get("/stats/:src_type/:dst_type", ctx -> {
       try {
         String srcType = ctx.pathParam("src_type");
         String dstType = ctx.pathParam("dst_type");
         ctx.json(new Stats(srcType, dstType));
       } catch (IllegalArgumentException e) {
         ctx.status(404);
       } catch (Exception e) {
         ctx.status(400);
         ctx.result(e.toString());
       }
     });
 
     app.get("/visit/:swh_id", ctx -> {
       try {
         SwhId start = new SwhId(ctx.pathParam("swh_id"));
 
         // By default, traversal is a forward DFS using all edges
         String algorithm = Optional.ofNullable(ctx.queryParam("traversal")).orElse("dfs");
         String direction = Optional.ofNullable(ctx.queryParam("direction")).orElse("forward");
         String edges = Optional.ofNullable(ctx.queryParam("edges")).orElse("cnt:dir:rel:rev:snp");
 
-        // TODO: Use transposed graph depending on 'direction'
-        ctx.json(new Visit(graph, start, edges, algorithm));
+        ctx.json(new Visit(graph, start, edges, algorithm, direction));
       } catch (IllegalArgumentException e) {
         ctx.status(400);
         ctx.result(e.toString());
       }
     });
 
     app.error(404, ctx -> { ctx.result("Not found"); });
   }
 }
diff --git a/api/server/src/main/java/org/softwareheritage/graph/Graph.java b/api/server/src/main/java/org/softwareheritage/graph/Graph.java
index 2f1a761..bc4527e 100644
--- a/api/server/src/main/java/org/softwareheritage/graph/Graph.java
+++ b/api/server/src/main/java/org/softwareheritage/graph/Graph.java
@@ -1,47 +1,73 @@
 package org.softwareheritage.graph;
 
 import it.unimi.dsi.big.webgraph.BVGraph;
 import it.unimi.dsi.big.webgraph.LazyLongIterator;
 
 import org.softwareheritage.graph.NodeIdMap;
 import org.softwareheritage.graph.SwhId;
 
 public class Graph {
   BVGraph graph;
+  BVGraph graphTransposed;
   String path;
   NodeIdMap nodeIdMap;
 
   public Graph(String graphPath) throws Exception {
     this.graph = BVGraph.load(graphPath);
+    this.graphTransposed = BVGraph.load(graphPath + "-transposed");
     this.path = graphPath;
     this.nodeIdMap = new NodeIdMap(graphPath);
   }
 
   public String getPath() {
     return path;
   }
 
   public long getNode(SwhId swhId) {
     return nodeIdMap.getNode(swhId);
   }
 
   public SwhId getSwhId(long node) {
     return nodeIdMap.getSwhId(node);
   }
 
   public long getNbNodes() {
     return graph.numNodes();
   }
 
   public long getNbEdges() {
     return graph.numArcs();
   }
 
   public LazyLongIterator successors(long node) {
     return graph.successors(node);
   }
 
   public long outdegree(long node) {
     return graph.outdegree(node);
   }
+
+  public LazyLongIterator predecessors(long node) {
+    return graphTransposed.successors(node);
+  }
+
+  public long indegree(long node) {
+    return graphTransposed.outdegree(node);
+  }
+
+  public long degree(long node, boolean isTransposed) {
+    if (isTransposed) {
+      return indegree(node);
+    } else {
+      return outdegree(node);
+    }
+  }
+
+  public LazyLongIterator neighbors(long node, boolean isTransposed) {
+    if (isTransposed) {
+      return predecessors(node);
+    } else {
+      return successors(node);
+    }
+  }
 }
diff --git a/api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java b/api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java
index 1b1fd49..13c58a5 100644
--- a/api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java
+++ b/api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java
@@ -1,66 +1,69 @@
 package org.softwareheritage.graph.algo;
 
 import java.util.ArrayList;
 import java.util.Stack;
 
 import it.unimi.dsi.big.webgraph.LazyLongIterator;
 import it.unimi.dsi.bits.LongArrayBitVector;
 
 import org.softwareheritage.graph.Graph;
 import org.softwareheritage.graph.SwhId;
 
 public class Visit {
   public class Path extends ArrayList<SwhId> {}
 
   Graph graph;
+  boolean isTransposed;
   String allowedEdges;
   Stack<Long> currentPath;
   ArrayList<Path> paths;
   LongArrayBitVector visited;
 
-  public Visit(Graph graph, SwhId start, String allowedEdges, String algorithm) {
+  public Visit(Graph graph, SwhId start, String allowedEdges, String algorithm, String direction) {
     this.graph = graph;
+    this.isTransposed = (direction == "backward");
     this.allowedEdges = allowedEdges;
     this.paths = new ArrayList<Path>();
     this.currentPath = new Stack<Long>();
     this.visited = LongArrayBitVector.ofLength(graph.getNbNodes());
 
     if (algorithm == "dfs") {
       dfs(graph.getNode(start));
     }
   }
 
   // Allow Jackson JSON to only serialize the 'paths' field
   public ArrayList<Path> getPaths() {
     return paths;
   }
 
-  private void dfs(long current) {
-    visited.set(current);
-    currentPath.push(current);
+  private void dfs(long currentNode) {
+    visited.set(currentNode);
+    currentPath.push(currentNode);
+
+    long degree = graph.degree(currentNode, isTransposed);
+    LazyLongIterator neighbors = graph.neighbors(currentNode, isTransposed);
 
-    long degree = graph.outdegree(current);
     if (degree == 0) {
       Path path = new Path();
       for (long node : currentPath) {
         path.add(graph.getSwhId(node));
       }
       paths.add(path);
     }
 
-    LazyLongIterator successors = graph.successors(current);
     while (degree-- > 0) {
-      long next = successors.nextLong();
-      if (isEdgeAllowed(current, next) && !visited.getBoolean(next)) {
-        dfs(next);
+      long nextNode = neighbors.nextLong();
+      if (isEdgeAllowed(currentNode, nextNode) && !visited.getBoolean(nextNode)) {
+        dfs(nextNode);
       }
     }
 
     currentPath.pop();
   }
 
-  private boolean isEdgeAllowed(long current, long next) {
+  private boolean isEdgeAllowed(long currentNode, long nextNode) {
     // TODO
     return true;
   }
 }