diff --git a/swh/provenance/tests/test_provenance_db.py b/swh/provenance/tests/test_provenance_db.py
--- a/swh/provenance/tests/test_provenance_db.py
+++ b/swh/provenance/tests/test_provenance_db.py
@@ -8,9 +8,9 @@
 import pytest
 
 from swh.model.tests.swh_model_data import TEST_OBJECTS
-from swh.provenance.model import RevisionEntry
+from swh.provenance.model import DirectoryEntry, RevisionEntry
 from swh.provenance.origin import OriginEntry
-from swh.provenance.provenance import origin_add, revision_add
+from swh.provenance.provenance import build_isochrone_graph, origin_add, revision_add
 from swh.provenance.storage.archive import ArchiveStorage
 from swh.provenance.tests.conftest import synthetic_result
 
@@ -78,6 +78,98 @@
         assert provenance.cursor.fetchone()[0] == 13
 
 
+def test_build_isochrone_graph(provenance, storage_and_CMDBTS, archive):
+    dt = datetime.datetime.fromisoformat
+    expected = {
+        # rev_id: (dir_id, maxdate)
+        "35ccb8dd1b53d2d8a5c1375eb513ef2beaa79ae5": (
+            "d8236ebbae712ef1797fbeb206f34ec9a65e73fd",
+            dt("2021-01-04T10:45:58+00:00"),
+        ),
+        "840b91df68e9549c156942ddd5002111efa15604": (
+            "4b825dc642cb6eb9a060e54bf8d69288fbee4904",
+            dt("0001-01-01T00:00:00+00:00"),
+        ),
+        "9e36e095b79e36a3da104ce272989b39cd68aefd": (  # R0000
+            "1bcdd0e9cdcaa3671f65dd6cfdfa3453e7aba409",
+            dt("2021-01-14T17:08:14+00:00"),  # 1610644094,  R0000
+        ),
+        "bfbfcc72ae7fc35d6941386c36280512e6b38440": (  # R0001
+            "afdb9b9c85e390027ae2d8d1bce9bd3b33285965",
+            dt("2021-01-14T17:08:17+00:00"),  # 1610644097,  R0001
+        ),
+        "0a31c9d509783abfd08f9fdfcd3acae20f17dfd0": (  # R0002
+            "46ca2f1d14eebde2fdaee8419c38a901776248fc",
+            dt("2021-01-14T17:08:19+00:00"),  # 1610644099,  R0002
+        ),
+        "ca6ec564c69efd2e5c70fb05486fd3f794765a04": (  # R0003
+            "cff39da31eb27826a6142f52e4ff34af39fdd51d",
+            dt("2021-01-14T17:08:17+00:00"),  # 1610644097,  R0001
+        ),
+        "fc6e10b7d41b1d56a94091134e3683ce91e80d91": (  # R0004
+            "46ca2f1d14eebde2fdaee8419c38a901776248fc",
+            dt("2021-01-14T17:08:19+00:00"),  # 1610644099,  R0002
+        ),
+        "1d1fcf1816a8a2a77f9b1f342ba11d0fe9fd7f17": (  # R0005
+            "7ce3f063b92b184db82b5740d75d4712b0503ac4",
+            dt("2021-01-14T17:08:25+00:00"),  # 1610644105,  R0005
+        ),
+        "9a71f967ae1a125be9b6569cc4eccec0aecabb7c": (  # R0006
+            "20ee5560adac87d74c8c39ffd90563d42253320b",
+            dt("2021-01-14T17:08:25+00:00"),  # 1610644105,  R0005
+        ),
+        "4fde4ea4494a630030a4bda99d03961d9add00c7": (  # R0007
+            "68f13b4a7696c9cdbe275a2616337bcdc64d6f2c",
+            dt("2021-01-14T17:08:25+00:00"),  # 1610644105,  R0005
+        ),
+        "ba00e89d47dc820bb32c783af7123ffc6e58b56d": (  # R0008
+            "ae199791adeb91cf3327c726f85f7456b29008b6",
+            dt("2021-01-14T17:08:25+00:00"),  # 1610644105,  R0005
+        ),
+        "55d4dc9471de6144f935daf3c38878155ca274d5": (  # R0009
+            "c1f209776551d0c88054c7acc549448239f1e9b1",
+            dt("2021-01-14T17:08:33+00:00"),  # 1610644113,  R0009
+        ),
+        "a8939755d0be76cfea136e9e5ebce9bc51c49fef": (  # R0010
+            "b81d69dd9c1b9075dc333b579a5c1fe2f61d98ef",
+            dt("2021-01-14T17:08:36+00:00"),  # 1610644116,  R0010
+        ),
+        "ca1774a07b6e02c1caa7ae678924efa9259ee7c6": (  # R0011
+            "e7577e34b45642a85bf6fc5da70d238e59244408",
+            dt("2021-01-14T17:08:38+00:00"),  # 1610644118,  R0011
+        ),
+        "611fe71d75b6ea151b06e3845c09777acc783d82": (  # R0012
+            "6b951492af140f823c5591586670f7f24f986c2b",
+            dt("2021-01-14T17:08:40+00:00"),  # 1610644120,  R0012
+        ),
+        "4c5551b4969eb2160824494d40b8e1f6187fc01e": (  # R0013
+            "e6c6b65cc6f1b35113eac8105cb981412ef8ffe8",
+            dt("2021-01-14T17:08:42+00:00"),  # 1610644122,  R0013
+        ),
+    }
+
+    storage, data = storage_and_CMDBTS
+    for revision in data["revision"]:
+        reventry = RevisionEntry(
+            id=revision["id"],
+            date=ts2dt(revision["date"]),
+            root=revision["directory"],
+        )
+        root = build_isochrone_graph(
+            archive, provenance, reventry, DirectoryEntry(reventry.root, b"")
+        )
+
+        assert root
+        assert expected[reventry.id.hex()] == (
+            root.entry.id.hex(),
+            root.maxdate,
+        )
+
+        # need to add the revision to the provenance index db, otherwise later
+        # isochrone graph computations won't match
+        revision_add(provenance, archive, [reventry], lower=True, mindepth=1)
+
+
 def test_provenance_content_find_first(provenance, storage_and_CMDBTS, archive):
     storage, data = storage_and_CMDBTS
     for revision in data["revision"]: