diff --git a/api/server/src/main/java/org/softwareheritage/graph/Graph.java b/api/server/src/main/java/org/softwareheritage/graph/Graph.java
--- a/api/server/src/main/java/org/softwareheritage/graph/Graph.java
+++ b/api/server/src/main/java/org/softwareheritage/graph/Graph.java
@@ -5,20 +5,24 @@
 import it.unimi.dsi.big.webgraph.BVGraph;
 import it.unimi.dsi.big.webgraph.LazyLongIterator;
 
+import org.softwareheritage.graph.Node;
 import org.softwareheritage.graph.SwhId;
 import org.softwareheritage.graph.backend.NodeIdMap;
+import org.softwareheritage.graph.backend.NodeTypesMap;
 
 public class Graph {
   BVGraph graph;
   BVGraph graphTransposed;
   String path;
   NodeIdMap nodeIdMap;
+  NodeTypesMap nodeTypesMap;
 
   public Graph(String path) throws IOException {
     this.graph = BVGraph.load(path);
     this.graphTransposed = BVGraph.load(path + "-transposed");
     this.path = path;
     this.nodeIdMap = new NodeIdMap(path, getNbNodes());
+    this.nodeTypesMap = new NodeTypesMap(path);
   }
 
   public void cleanUp() throws IOException {
@@ -37,6 +41,10 @@
     return nodeIdMap.getSwhId(nodeId);
   }
 
+  public Node.Type getNodeType(long nodeId) {
+    return nodeTypesMap.getType(nodeId);
+  }
+
   public long getNbNodes() {
     return graph.numNodes();
   }
diff --git a/api/server/src/main/java/org/softwareheritage/graph/Node.java b/api/server/src/main/java/org/softwareheritage/graph/Node.java
--- a/api/server/src/main/java/org/softwareheritage/graph/Node.java
+++ b/api/server/src/main/java/org/softwareheritage/graph/Node.java
@@ -12,6 +12,22 @@
     REV,
     SNP;
 
+    public static Node.Type fromInt(int intType) {
+      switch (intType) {
+        case 0:
+          return CNT;
+        case 1:
+          return DIR;
+        case 2:
+          return REL;
+        case 3:
+          return REV;
+        case 4:
+          return SNP;
+      }
+      return null;
+    }
+
     public static Node.Type fromStr(String strType) {
       return Node.Type.valueOf(strType.toUpperCase());
     }
diff --git a/api/server/src/main/java/org/softwareheritage/graph/backend/NodeTypesMap.java b/api/server/src/main/java/org/softwareheritage/graph/backend/NodeTypesMap.java
new file mode 100644
--- /dev/null
+++ b/api/server/src/main/java/org/softwareheritage/graph/backend/NodeTypesMap.java
@@ -0,0 +1,25 @@
+package org.softwareheritage.graph.backend;
+
+import java.io.IOException;
+
+import it.unimi.dsi.fastutil.io.BinIO;
+import it.unimi.dsi.fastutil.longs.LongBigList;
+
+import org.softwareheritage.graph.Node;
+
+public class NodeTypesMap {
+  LongBigList nodeTypesMap;
+
+  public NodeTypesMap(String graphPath) throws IOException {
+    try {
+      nodeTypesMap = (LongBigList) BinIO.loadObject(graphPath + ".nodeTypesMap");
+    } catch (ClassNotFoundException e) {
+      throw new IllegalArgumentException("The .nodeTypesMap file has unknown class object: " + e);
+    }
+  }
+
+  public Node.Type getType(long nodeId) {
+    long type = nodeTypesMap.getLong(nodeId);
+    return Node.Type.fromInt((int) type);
+  }
+}
diff --git a/api/server/src/main/java/org/softwareheritage/graph/backend/Setup.java b/api/server/src/main/java/org/softwareheritage/graph/backend/Setup.java
--- a/api/server/src/main/java/org/softwareheritage/graph/backend/Setup.java
+++ b/api/server/src/main/java/org/softwareheritage/graph/backend/Setup.java
@@ -9,15 +9,18 @@
 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.backend.NodeIdMap;
+import org.softwareheritage.graph.SwhId;
+import org.softwareheritage.graph.backend.NodeTypesMap;
 
 public class Setup {
   public static void main(String[] args) throws IOException {
@@ -68,18 +71,29 @@
       // nodeToSwhMap needs to write SWH id in order of node id, so use a temporary array
       Object[][] nodeToSwhId = ObjectBigArrays.newBigArray(nbIds);
 
+      // To effectively run edge restriction during graph traversals, we store node id (long) -> SWH
+      // type map. This is represented as a bitmap where each Node.Type uses 3 bits.
+      final int nbBitsPerNodeType = 3;
+      LongArrayBitVector nodeTypesBitVector = LongArrayBitVector.ofLength(nbBitsPerNodeType * nbIds);
+      LongBigList nodeTypesMap = nodeTypesBitVector.asLongBigList(nbBitsPerNodeType);
+
       for (long iNode = 0; iNode < nbIds && swhIdIterator.hasNext(); iNode++) {
-        String swhId = swhIdIterator.next().toString();
-        long mphId = mphMap.getLong(swhId);
+        String strSwhId = swhIdIterator.next().toString();
+        long mphId = mphMap.getLong(strSwhId);
         long nodeId = LongBigArrays.get(bfsMap, mphId);
 
         String paddedNodeId = String.format("%0" + NodeIdMap.NODE_ID_LENGTH + "d", nodeId);
-        String line = swhId + " " + paddedNodeId + "\n";
+        String line = strSwhId + " " + paddedNodeId + "\n";
         swhToNodeMap.write(line);
 
-        ObjectBigArrays.set(nodeToSwhId, nodeId, swhId);
+        ObjectBigArrays.set(nodeToSwhId, nodeId, strSwhId);
+
+        SwhId swhId = new SwhId(strSwhId);
+        nodeTypesMap.set(nodeId, swhId.getType().ordinal());
       }
 
+      BinIO.storeObject(nodeTypesMap, graphPath + ".nodeTypesMap");
+
       for (long iNode = 0; iNode < nbIds; iNode++) {
         String line = ObjectBigArrays.get(nodeToSwhId, iNode).toString() + "\n";
         nodeToSwhMap.write(line);