diff --git a/api/client/swh/graph/client.py b/api/client/swh/graph/client.py --- a/api/client/swh/graph/client.py +++ b/api/client/swh/graph/client.py @@ -30,6 +30,13 @@ # Web API endpoints + def leaves(self, src, edges="*", direction="forward"): + return self.get('leaves/{}'.format(src), + params={ + 'edges': edges, + 'direction': direction + }) + def stats(self): return self.get('stats') diff --git a/api/server/src/main/java/org/softwareheritage/graph/App.java b/api/server/src/main/java/org/softwareheritage/graph/App.java --- a/api/server/src/main/java/org/softwareheritage/graph/App.java +++ b/api/server/src/main/java/org/softwareheritage/graph/App.java @@ -12,6 +12,7 @@ import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.SwhId; +import org.softwareheritage.graph.algo.Leaves; import org.softwareheritage.graph.algo.Stats; import org.softwareheritage.graph.algo.Visit; import org.softwareheritage.graph.algo.Walk; @@ -41,6 +42,7 @@ Javalin app = Javalin.create().start(5009); app.before("/stats/*", ctx -> { checkQueryStrings(ctx, ""); }); + app.before("/leaves/*", ctx -> { checkQueryStrings(ctx, "direction|edges"); }); app.before("/visit/*", ctx -> { checkQueryStrings(ctx, "direction|edges"); }); app.before("/walk/*", ctx -> { checkQueryStrings(ctx, "direction|edges|traversal"); }); @@ -49,6 +51,15 @@ // Graph traversal endpoints // By default the traversal is a forward DFS using all edges + app.get("/leaves/:src", ctx -> { + SwhId src = new SwhId(ctx.pathParam("src")); + String direction = ctx.queryParam("direction", "forward"); + String edgesFmt = ctx.queryParam("edges", "*"); + + Leaves leaves = new Leaves(graph, src, edgesFmt, direction); + ctx.json(leaves.getLeaves()); + }); + app.get("/visit/:src", ctx -> { SwhId src = new SwhId(ctx.pathParam("src")); String direction = ctx.queryParam("direction", "forward"); diff --git a/api/server/src/main/java/org/softwareheritage/graph/algo/Leaves.java b/api/server/src/main/java/org/softwareheritage/graph/algo/Leaves.java new file mode 100644 --- /dev/null +++ b/api/server/src/main/java/org/softwareheritage/graph/algo/Leaves.java @@ -0,0 +1,64 @@ +package org.softwareheritage.graph.algo; + +import java.util.ArrayList; + +import it.unimi.dsi.big.webgraph.LazyLongIterator; +import it.unimi.dsi.bits.LongArrayBitVector; + +import org.softwareheritage.graph.AllowedEdges; +import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.Node; +import org.softwareheritage.graph.SwhId; + +public class Leaves { + Graph graph; + boolean useTransposed; + AllowedEdges edges; + + ArrayList leaves; + LongArrayBitVector visited; + + public Leaves(Graph graph, SwhId src, String edgesFmt, String direction) { + if (!direction.matches("forward|backward")) { + throw new IllegalArgumentException("Unknown traversal direction: " + direction); + } + + this.graph = graph; + this.useTransposed = (direction.equals("backward")); + this.edges = new AllowedEdges(edgesFmt); + this.leaves = new ArrayList(); + this.visited = LongArrayBitVector.ofLength(graph.getNbNodes()); + + long nodeId = graph.getNodeId(src); + dfs(nodeId); + } + + public ArrayList getLeaves() { + return leaves; + } + + private void dfs(long currentNodeId) { + visited.set(currentNodeId); + SwhId currentSwhId = graph.getSwhId(currentNodeId); + + long degree = graph.degree(currentNodeId, useTransposed); + LazyLongIterator neighbors = graph.neighbors(currentNodeId, useTransposed); + long neighborsCnt = 0; + + while (degree-- > 0) { + long neighborNodeId = neighbors.nextLong(); + Node.Type currentNodeType = currentSwhId.getType(); + Node.Type neighborNodeType = graph.getSwhId(neighborNodeId).getType(); + if (edges.isAllowed(currentNodeType, neighborNodeType)) { + neighborsCnt++; + if (!visited.getBoolean(neighborNodeId)) { + dfs(neighborNodeId); + } + } + } + + if (neighborsCnt == 0) { + leaves.add(currentSwhId); + } + } +} diff --git a/api/server/src/test/java/org/softwareheritage/graph/LeavesTest.java b/api/server/src/test/java/org/softwareheritage/graph/LeavesTest.java new file mode 100644 --- /dev/null +++ b/api/server/src/test/java/org/softwareheritage/graph/LeavesTest.java @@ -0,0 +1,103 @@ +package org.softwareheritage.graph; + +import java.util.ArrayList; + +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.GraphTest; +import org.softwareheritage.graph.SwhId; +import org.softwareheritage.graph.algo.Leaves; + +public class LeavesTest extends GraphTest { + @Test + public void forwardFromSnp() { + Graph graph = getGraph(); + SwhId src = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); + Leaves leaves = new Leaves(graph, src, "*", "forward"); + + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000004")); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000005")); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007")); + + assertEquals(expectedLeaves, leaves.getLeaves()); + } + + @Test + public void forwardFromRel() { + Graph graph = getGraph(); + SwhId src = new SwhId("swh:1:rel:0000000000000000000000000000000000000019"); + Leaves leaves = new Leaves(graph, src, "*", "forward"); + + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000015")); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000014")); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000004")); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000005")); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007")); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000011")); + + assertEquals(expectedLeaves, leaves.getLeaves()); + } + + @Test + public void backwardFromLeaf() { + Graph graph = getGraph(); + + SwhId src1 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000015"); + Leaves leaves1 = new Leaves(graph, src1, "*", "backward"); + ArrayList expectedLeaves1 = new ArrayList<>(); + expectedLeaves1.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000019")); + assertEquals(expectedLeaves1, leaves1.getLeaves()); + + SwhId src2 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000004"); + Leaves leaves2 = new Leaves(graph, src2, "*", "backward"); + ArrayList expectedLeaves2 = new ArrayList<>(); + expectedLeaves2.add(new SwhId("swh:1:snp:0000000000000000000000000000000000000020")); + expectedLeaves2.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000019")); + assertEquals(expectedLeaves2, leaves2.getLeaves()); + } + + @Test + public void forwardRevToRevOnly() { + Graph graph = getGraph(); + SwhId src = new SwhId("swh:1:rev:0000000000000000000000000000000000000018"); + Leaves leaves = new Leaves(graph, src, "rev:rev", "forward"); + + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000003")); + + assertEquals(expectedLeaves, leaves.getLeaves()); + } + + @Test + public void forwardDirToAll() { + Graph graph = getGraph(); + SwhId src = new SwhId("swh:1:dir:0000000000000000000000000000000000000008"); + Leaves leaves = new Leaves(graph, src, "dir:*", "forward"); + + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000004")); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000005")); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007")); + + assertEquals(expectedLeaves, leaves.getLeaves()); + } + + @Test + public void backwardCntToDirDirToDir() { + Graph graph = getGraph(); + SwhId src = new SwhId("swh:1:cnt:0000000000000000000000000000000000000005"); + Leaves leaves = new Leaves(graph, src, "cnt:dir,dir:dir", "backward"); + + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000012")); + + assertEquals(expectedLeaves, leaves.getLeaves()); + } +} diff --git a/docs/api.rst b/docs/api.rst --- a/docs/api.rst +++ b/docs/api.rst @@ -30,6 +30,36 @@ nodes, or from directories nodes. - ``"*:rel"`` node types allowing all edges to releases. +Leaves +------ + +.. http:get:: /graph/leaves/:src + + Performs a graph traversal and returns the leaves of the subgraph rooted at + the specified source node. + + :param string src: source node specified as a SWH PID + + :query string edges: edges types the traversal can follow; default to + ``"*"`` + :query string direction: direction in which graph edges will be followed; + can be either ``forward`` or ``backward``, default to ``forward`` + + :statuscode 200: success + :statuscode 400: invalid query string provided + :statuscode 404: starting node cannot be found + + .. sourcecode:: http + + HTTP/1.1 200 OK + Content-Type: application/json + + [ + "swh:1:cnt:669ac7c32292798644b21dbb5a0dc657125f444d", + "swh:1:cnt:da4cb28febe66172a9fdf1a235525ae6c00cde1d", + ... + ] + Walk ----